/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 16:56:25,574 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 16:56:25,575 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 16:56:25,602 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 16:56:25,603 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 16:56:25,608 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 16:56:25,609 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 16:56:25,611 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 16:56:25,613 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 16:56:25,614 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 16:56:25,615 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 16:56:25,616 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 16:56:25,616 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 16:56:25,617 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 16:56:25,618 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 16:56:25,624 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 16:56:25,625 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 16:56:25,625 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 16:56:25,627 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 16:56:25,629 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 16:56:25,631 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 16:56:25,632 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 16:56:25,633 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 16:56:25,634 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 16:56:25,635 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 16:56:25,638 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 16:56:25,638 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 16:56:25,638 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 16:56:25,639 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 16:56:25,639 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 16:56:25,640 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 16:56:25,641 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 16:56:25,641 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 16:56:25,642 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 16:56:25,642 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 16:56:25,643 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 16:56:25,643 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 16:56:25,644 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 16:56:25,644 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 16:56:25,644 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 16:56:25,645 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 16:56:25,647 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 16:56:25,648 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-03-20 16:56:25,660 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 16:56:25,660 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 16:56:25,663 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 16:56:25,663 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 16:56:25,663 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 16:56:25,663 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 16:56:25,663 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 16:56:25,663 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 16:56:25,663 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 16:56:25,664 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 16:56:25,664 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 16:56:25,665 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 16:56:25,665 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 16:56:25,666 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 16:56:25,666 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 16:56:25,666 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 16:56:25,666 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 16:56:25,666 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 16:56:25,666 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-03-20 16:56:25,666 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-20 16:56:25,930 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 16:56:25,951 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 16:56:25,953 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 16:56:25,954 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 16:56:25,955 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 16:56:25,956 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c [2022-03-20 16:56:26,027 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/030f5bc78/c49799acf9cd4c159c076e991701ecaf/FLAGc1b6990be [2022-03-20 16:56:26,430 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 16:56:26,430 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c [2022-03-20 16:56:26,437 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/030f5bc78/c49799acf9cd4c159c076e991701ecaf/FLAGc1b6990be [2022-03-20 16:56:26,834 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/030f5bc78/c49799acf9cd4c159c076e991701ecaf [2022-03-20 16:56:26,836 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 16:56:26,837 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 16:56:26,838 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 16:56:26,838 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 16:56:26,842 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 16:56:26,843 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 04:56:26" (1/1) ... [2022-03-20 16:56:26,844 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3a9d7304 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:26, skipping insertion in model container [2022-03-20 16:56:26,845 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 04:56:26" (1/1) ... [2022-03-20 16:56:26,852 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 16:56:26,869 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 16:56:27,008 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c[458,471] [2022-03-20 16:56:27,026 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 16:56:27,033 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 16:56:27,044 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c[458,471] [2022-03-20 16:56:27,051 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 16:56:27,062 INFO L208 MainTranslator]: Completed translation [2022-03-20 16:56:27,063 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27 WrapperNode [2022-03-20 16:56:27,063 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 16:56:27,064 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 16:56:27,064 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 16:56:27,064 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 16:56:27,074 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,074 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,079 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,080 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,084 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,087 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,088 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,090 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 16:56:27,091 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 16:56:27,091 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 16:56:27,091 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 16:56:27,092 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (1/1) ... [2022-03-20 16:56:27,098 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 16:56:27,107 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:27,121 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-20 16:56:27,124 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-20 16:56:27,155 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 16:56:27,156 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 16:56:27,156 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 16:56:27,156 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 16:56:27,156 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 16:56:27,156 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 16:56:27,157 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 16:56:27,157 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 16:56:27,157 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 16:56:27,157 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 16:56:27,158 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-03-20 16:56:27,158 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 16:56:27,159 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 16:56:27,159 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 16:56:27,159 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 16:56:27,159 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 16:56:27,159 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 16:56:27,160 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 16:56:27,160 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 16:56:27,160 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 16:56:27,221 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 16:56:27,224 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 16:56:27,398 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 16:56:27,413 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 16:56:27,413 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-20 16:56:27,414 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 04:56:27 BoogieIcfgContainer [2022-03-20 16:56:27,415 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 16:56:27,416 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 16:56:27,416 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 16:56:27,419 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 16:56:27,420 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 04:56:26" (1/3) ... [2022-03-20 16:56:27,420 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fe9f241 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 04:56:27, skipping insertion in model container [2022-03-20 16:56:27,420 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 04:56:27" (2/3) ... [2022-03-20 16:56:27,421 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fe9f241 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 04:56:27, skipping insertion in model container [2022-03-20 16:56:27,421 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 04:56:27" (3/3) ... [2022-03-20 16:56:27,422 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll_unwindbound10.c [2022-03-20 16:56:27,431 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 16:56:27,431 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 16:56:27,509 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 16:56:27,520 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-20 16:56:27,520 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 16:56:27,538 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 16:56:27,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 16:56:27,553 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:27,554 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:27,555 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:27,562 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:27,562 INFO L85 PathProgramCache]: Analyzing trace with hash 21872251, now seen corresponding path program 1 times [2022-03-20 16:56:27,577 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:27,578 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1596209205] [2022-03-20 16:56:27,589 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 16:56:27,590 INFO L85 PathProgramCache]: Analyzing trace with hash 21872251, now seen corresponding path program 2 times [2022-03-20 16:56:27,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:27,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1201314474] [2022-03-20 16:56:27,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:27,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:27,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 16:56:27,790 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 16:56:27,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 16:56:27,825 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 16:56:27,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 16:56:27,834 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 16:56:27,834 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:27,835 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1201314474] [2022-03-20 16:56:27,840 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1201314474] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:27,840 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:27,840 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 16:56:27,843 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:27,844 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1596209205] [2022-03-20 16:56:27,844 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1596209205] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:27,844 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:27,844 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 16:56:27,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1074066862] [2022-03-20 16:56:27,845 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:27,849 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 16:56:27,849 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:27,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 16:56:27,881 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 16:56:27,883 INFO L87 Difference]: Start difference. First operand has 29 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 16:56:27,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:27,999 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2022-03-20 16:56:28,002 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 16:56:28,004 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-20 16:56:28,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:28,016 INFO L225 Difference]: With dead ends: 50 [2022-03-20 16:56:28,016 INFO L226 Difference]: Without dead ends: 25 [2022-03-20 16:56:28,023 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 16:56:28,030 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:28,032 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 34 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:28,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2022-03-20 16:56:28,072 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 24. [2022-03-20 16:56:28,073 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-20 16:56:28,076 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2022-03-20 16:56:28,078 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 17 [2022-03-20 16:56:28,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:28,078 INFO L478 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2022-03-20 16:56:28,078 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 16:56:28,079 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2022-03-20 16:56:28,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-20 16:56:28,080 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:28,080 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:28,081 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 16:56:28,081 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:28,082 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:28,083 INFO L85 PathProgramCache]: Analyzing trace with hash -119968982, now seen corresponding path program 1 times [2022-03-20 16:56:28,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:28,083 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [620689520] [2022-03-20 16:56:28,092 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 16:56:28,092 INFO L85 PathProgramCache]: Analyzing trace with hash -119968982, now seen corresponding path program 2 times [2022-03-20 16:56:28,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:28,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1239315631] [2022-03-20 16:56:28,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:28,094 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:28,115 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:28,116 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1752764431] [2022-03-20 16:56:28,116 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:28,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:28,116 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:28,118 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:28,119 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 16:56:28,183 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-03-20 16:56:28,183 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:28,186 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-20 16:56:28,190 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:28,322 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 16:56:28,323 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 16:56:28,323 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:28,323 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1239315631] [2022-03-20 16:56:28,323 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:28,323 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1752764431] [2022-03-20 16:56:28,325 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1752764431] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:28,325 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:28,325 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-20 16:56:28,327 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:28,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [620689520] [2022-03-20 16:56:28,328 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [620689520] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:28,328 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:28,329 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-20 16:56:28,332 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [873105911] [2022-03-20 16:56:28,333 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:28,334 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-20 16:56:28,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:28,335 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-20 16:56:28,335 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-20 16:56:28,336 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 16:56:28,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:28,350 INFO L93 Difference]: Finished difference Result 34 states and 38 transitions. [2022-03-20 16:56:28,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-20 16:56:28,350 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-03-20 16:56:28,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:28,351 INFO L225 Difference]: With dead ends: 34 [2022-03-20 16:56:28,351 INFO L226 Difference]: Without dead ends: 26 [2022-03-20 16:56:28,352 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-20 16:56:28,353 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:28,354 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 63 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:28,354 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-03-20 16:56:28,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-03-20 16:56:28,365 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-20 16:56:28,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-03-20 16:56:28,368 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 18 [2022-03-20 16:56:28,368 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:28,368 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-03-20 16:56:28,368 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 16:56:28,369 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-03-20 16:56:28,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-20 16:56:28,369 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:28,370 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:28,395 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-20 16:56:28,595 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:28,595 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:28,596 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:28,596 INFO L85 PathProgramCache]: Analyzing trace with hash -118181522, now seen corresponding path program 1 times [2022-03-20 16:56:28,596 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:28,596 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [786980235] [2022-03-20 16:56:28,597 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 16:56:28,597 INFO L85 PathProgramCache]: Analyzing trace with hash -118181522, now seen corresponding path program 2 times [2022-03-20 16:56:28,597 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:28,597 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1088216385] [2022-03-20 16:56:28,598 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:28,598 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:28,625 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:28,626 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [338143172] [2022-03-20 16:56:28,626 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:28,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:28,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:28,634 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:28,635 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 16:56:28,671 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-03-20 16:56:28,671 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:28,672 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 16:56:28,674 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:28,740 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 16:56:28,740 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 16:56:28,740 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:28,740 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1088216385] [2022-03-20 16:56:28,741 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:28,741 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [338143172] [2022-03-20 16:56:28,741 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [338143172] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:28,741 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:28,741 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 16:56:28,742 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:28,742 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [786980235] [2022-03-20 16:56:28,742 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [786980235] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:28,742 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:28,742 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 16:56:28,742 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [451739300] [2022-03-20 16:56:28,743 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:28,743 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 16:56:28,743 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:28,744 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 16:56:28,744 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 16:56:28,744 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 16:56:28,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:28,815 INFO L93 Difference]: Finished difference Result 36 states and 41 transitions. [2022-03-20 16:56:28,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 16:56:28,815 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-03-20 16:56:28,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:28,816 INFO L225 Difference]: With dead ends: 36 [2022-03-20 16:56:28,816 INFO L226 Difference]: Without dead ends: 32 [2022-03-20 16:56:28,817 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 16:56:28,818 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:28,819 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 94 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:28,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-03-20 16:56:28,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-03-20 16:56:28,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 20 states have (on average 1.15) internal successors, (23), 21 states have internal predecessors, (23), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 16:56:28,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2022-03-20 16:56:28,828 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 18 [2022-03-20 16:56:28,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:28,828 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2022-03-20 16:56:28,828 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 16:56:28,829 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2022-03-20 16:56:28,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-03-20 16:56:28,829 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:28,830 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:28,857 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:29,057 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-20 16:56:29,058 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:29,058 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:29,059 INFO L85 PathProgramCache]: Analyzing trace with hash -1364840471, now seen corresponding path program 1 times [2022-03-20 16:56:29,059 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:29,059 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1382630674] [2022-03-20 16:56:29,079 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:29,079 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:29,079 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:29,079 INFO L85 PathProgramCache]: Analyzing trace with hash -1364840471, now seen corresponding path program 2 times [2022-03-20 16:56:29,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:29,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [605770202] [2022-03-20 16:56:29,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:29,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:29,109 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:29,109 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1429603627] [2022-03-20 16:56:29,111 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:29,111 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:29,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:29,113 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:29,114 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 16:56:29,353 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:29,353 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:29,355 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 16:56:29,357 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:29,439 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 16:56:29,439 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:29,528 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 16:56:29,529 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:29,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [605770202] [2022-03-20 16:56:29,529 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:29,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1429603627] [2022-03-20 16:56:29,529 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1429603627] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:29,530 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:29,530 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-20 16:56:29,530 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:29,530 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1382630674] [2022-03-20 16:56:29,531 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1382630674] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:29,531 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:29,531 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 16:56:29,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1523052619] [2022-03-20 16:56:29,531 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:29,531 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 16:56:29,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:29,532 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 16:56:29,532 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-20 16:56:29,533 INFO L87 Difference]: Start difference. First operand 32 states and 35 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-20 16:56:29,575 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:29,575 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-03-20 16:56:29,575 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 16:56:29,576 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2022-03-20 16:56:29,576 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:29,577 INFO L225 Difference]: With dead ends: 42 [2022-03-20 16:56:29,577 INFO L226 Difference]: Without dead ends: 34 [2022-03-20 16:56:29,577 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-03-20 16:56:29,578 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:29,579 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 69 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:29,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-03-20 16:56:29,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-03-20 16:56:29,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 16:56:29,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2022-03-20 16:56:29,586 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 26 [2022-03-20 16:56:29,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:29,587 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2022-03-20 16:56:29,587 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-20 16:56:29,587 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2022-03-20 16:56:29,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-03-20 16:56:29,589 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:29,590 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:29,600 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:29,796 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:29,796 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:29,797 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:29,797 INFO L85 PathProgramCache]: Analyzing trace with hash -1363053011, now seen corresponding path program 1 times [2022-03-20 16:56:29,797 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:29,797 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1295040707] [2022-03-20 16:56:29,804 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:29,804 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:29,804 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:29,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1363053011, now seen corresponding path program 2 times [2022-03-20 16:56:29,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:29,805 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1213214068] [2022-03-20 16:56:29,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:29,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:29,816 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:29,817 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [585227952] [2022-03-20 16:56:29,817 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:29,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:29,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:29,819 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:29,820 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 16:56:29,872 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:29,872 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:29,873 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 16:56:29,875 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:30,004 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 16:56:30,004 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:30,407 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-20 16:56:30,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:30,411 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1213214068] [2022-03-20 16:56:30,411 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:30,411 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [585227952] [2022-03-20 16:56:30,411 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [585227952] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:30,412 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:30,412 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 16:56:30,412 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:30,412 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1295040707] [2022-03-20 16:56:30,412 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1295040707] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:30,412 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:30,412 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 16:56:30,413 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1875320885] [2022-03-20 16:56:30,413 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:30,413 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 16:56:30,413 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:30,414 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 16:56:30,414 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 16:56:30,414 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 16:56:30,465 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:30,465 INFO L93 Difference]: Finished difference Result 40 states and 42 transitions. [2022-03-20 16:56:30,465 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 16:56:30,465 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 26 [2022-03-20 16:56:30,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:30,466 INFO L225 Difference]: With dead ends: 40 [2022-03-20 16:56:30,466 INFO L226 Difference]: Without dead ends: 36 [2022-03-20 16:56:30,467 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 16:56:30,467 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 7 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:30,468 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 79 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:30,468 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-20 16:56:30,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-03-20 16:56:30,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 24 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 16:56:30,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 38 transitions. [2022-03-20 16:56:30,477 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 38 transitions. Word has length 26 [2022-03-20 16:56:30,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:30,477 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 38 transitions. [2022-03-20 16:56:30,477 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 16:56:30,478 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 38 transitions. [2022-03-20 16:56:30,478 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-03-20 16:56:30,478 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:30,479 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:30,511 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:30,704 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:30,704 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:30,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:30,705 INFO L85 PathProgramCache]: Analyzing trace with hash -1559147673, now seen corresponding path program 1 times [2022-03-20 16:56:30,705 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:30,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [42505233] [2022-03-20 16:56:30,709 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:30,709 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:30,709 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:30,709 INFO L85 PathProgramCache]: Analyzing trace with hash -1559147673, now seen corresponding path program 2 times [2022-03-20 16:56:30,710 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:30,710 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [896640877] [2022-03-20 16:56:30,710 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:30,710 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:30,719 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:30,724 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1598493244] [2022-03-20 16:56:30,724 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:30,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:30,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:30,726 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:30,728 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 16:56:30,771 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:30,772 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:30,773 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 16:56:30,775 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:31,000 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 16:56:31,001 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:31,201 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:31,201 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [896640877] [2022-03-20 16:56:31,201 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:31,202 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1598493244] [2022-03-20 16:56:31,202 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1598493244] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:31,202 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:31,202 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-20 16:56:31,202 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:31,202 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [42505233] [2022-03-20 16:56:31,202 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [42505233] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:31,203 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:31,203 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-20 16:56:31,203 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [118529927] [2022-03-20 16:56:31,203 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:31,203 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 16:56:31,203 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:31,204 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 16:56:31,204 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 16:56:31,204 INFO L87 Difference]: Start difference. First operand 36 states and 38 transitions. Second operand has 7 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-03-20 16:56:31,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:31,280 INFO L93 Difference]: Finished difference Result 44 states and 48 transitions. [2022-03-20 16:56:31,281 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 16:56:31,281 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 37 [2022-03-20 16:56:31,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:31,284 INFO L225 Difference]: With dead ends: 44 [2022-03-20 16:56:31,284 INFO L226 Difference]: Without dead ends: 38 [2022-03-20 16:56:31,285 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 46 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-03-20 16:56:31,287 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 2 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 159 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:31,287 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 159 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:31,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-03-20 16:56:31,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-03-20 16:56:31,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 25 states have (on average 1.08) internal successors, (27), 25 states have internal predecessors, (27), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 16:56:31,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 41 transitions. [2022-03-20 16:56:31,305 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 41 transitions. Word has length 37 [2022-03-20 16:56:31,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:31,307 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 41 transitions. [2022-03-20 16:56:31,307 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-03-20 16:56:31,307 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 41 transitions. [2022-03-20 16:56:31,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-03-20 16:56:31,309 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:31,309 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:31,339 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:31,537 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:31,537 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:31,538 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:31,538 INFO L85 PathProgramCache]: Analyzing trace with hash -951509150, now seen corresponding path program 1 times [2022-03-20 16:56:31,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:31,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [153886867] [2022-03-20 16:56:31,542 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:31,542 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:31,542 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:31,542 INFO L85 PathProgramCache]: Analyzing trace with hash -951509150, now seen corresponding path program 2 times [2022-03-20 16:56:31,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:31,542 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1112487624] [2022-03-20 16:56:31,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:31,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:31,552 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:31,552 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [178342437] [2022-03-20 16:56:31,552 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:31,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:31,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:31,554 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:31,555 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 16:56:31,600 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:31,600 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:31,601 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-20 16:56:31,607 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:31,711 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:31,712 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:31,833 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 16:56:31,833 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:31,833 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1112487624] [2022-03-20 16:56:31,833 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:31,833 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [178342437] [2022-03-20 16:56:31,834 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [178342437] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:31,834 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:31,834 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-03-20 16:56:31,834 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:31,834 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [153886867] [2022-03-20 16:56:31,834 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [153886867] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:31,834 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:31,834 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 16:56:31,834 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843210839] [2022-03-20 16:56:31,835 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:31,835 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 16:56:31,835 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:31,836 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 16:56:31,836 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-03-20 16:56:31,836 INFO L87 Difference]: Start difference. First operand 38 states and 41 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 16:56:31,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:31,885 INFO L93 Difference]: Finished difference Result 54 states and 56 transitions. [2022-03-20 16:56:31,885 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 16:56:31,885 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Word has length 39 [2022-03-20 16:56:31,886 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:31,886 INFO L225 Difference]: With dead ends: 54 [2022-03-20 16:56:31,886 INFO L226 Difference]: Without dead ends: 44 [2022-03-20 16:56:31,886 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2022-03-20 16:56:31,887 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 6 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:31,887 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 93 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:31,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-20 16:56:31,896 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2022-03-20 16:56:31,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 30 states have internal predecessors, (32), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 16:56:31,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 46 transitions. [2022-03-20 16:56:31,897 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 46 transitions. Word has length 39 [2022-03-20 16:56:31,897 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:31,897 INFO L478 AbstractCegarLoop]: Abstraction has 44 states and 46 transitions. [2022-03-20 16:56:31,897 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 16:56:31,897 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 46 transitions. [2022-03-20 16:56:31,898 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-20 16:56:31,898 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:31,898 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:31,926 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:32,114 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:32,115 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:32,115 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:32,115 INFO L85 PathProgramCache]: Analyzing trace with hash 1537538120, now seen corresponding path program 3 times [2022-03-20 16:56:32,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:32,115 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1856224553] [2022-03-20 16:56:32,119 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:32,119 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:32,119 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:32,120 INFO L85 PathProgramCache]: Analyzing trace with hash 1537538120, now seen corresponding path program 4 times [2022-03-20 16:56:32,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:32,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46123388] [2022-03-20 16:56:32,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:32,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:32,128 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:32,128 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2391062] [2022-03-20 16:56:32,129 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 16:56:32,129 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:32,129 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:32,130 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:32,131 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 16:56:32,175 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 16:56:32,175 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:32,176 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 16:56:32,180 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:32,367 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 16:56:32,368 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:32,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:32,507 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46123388] [2022-03-20 16:56:32,507 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:32,507 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2391062] [2022-03-20 16:56:32,507 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2391062] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:32,508 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:32,508 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-03-20 16:56:32,508 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:32,508 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1856224553] [2022-03-20 16:56:32,508 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1856224553] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:32,508 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:32,508 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 16:56:32,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [256619376] [2022-03-20 16:56:32,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:32,509 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 16:56:32,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:32,509 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 16:56:32,509 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-20 16:56:32,509 INFO L87 Difference]: Start difference. First operand 44 states and 46 transitions. Second operand has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-03-20 16:56:32,601 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:32,601 INFO L93 Difference]: Finished difference Result 52 states and 56 transitions. [2022-03-20 16:56:32,601 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 16:56:32,602 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 45 [2022-03-20 16:56:32,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:32,604 INFO L225 Difference]: With dead ends: 52 [2022-03-20 16:56:32,604 INFO L226 Difference]: Without dead ends: 46 [2022-03-20 16:56:32,605 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 53 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-03-20 16:56:32,605 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 2 mSDsluCounter, 171 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 206 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:32,605 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 206 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:32,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-03-20 16:56:32,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2022-03-20 16:56:32,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 9 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 16:56:32,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 49 transitions. [2022-03-20 16:56:32,635 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 49 transitions. Word has length 45 [2022-03-20 16:56:32,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:32,635 INFO L478 AbstractCegarLoop]: Abstraction has 46 states and 49 transitions. [2022-03-20 16:56:32,635 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-03-20 16:56:32,635 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 49 transitions. [2022-03-20 16:56:32,637 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 16:56:32,638 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:32,638 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:32,663 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:32,859 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:32,860 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:32,860 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:32,860 INFO L85 PathProgramCache]: Analyzing trace with hash -1448798205, now seen corresponding path program 3 times [2022-03-20 16:56:32,860 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:32,860 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [72592821] [2022-03-20 16:56:32,864 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:32,864 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:32,864 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:32,864 INFO L85 PathProgramCache]: Analyzing trace with hash -1448798205, now seen corresponding path program 4 times [2022-03-20 16:56:32,865 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:32,865 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1426946514] [2022-03-20 16:56:32,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:32,865 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:32,874 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:32,874 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [808193330] [2022-03-20 16:56:32,874 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 16:56:32,874 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:32,875 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:32,876 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:32,877 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 16:56:32,924 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 16:56:32,924 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:32,926 INFO L263 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 16:56:32,929 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:33,037 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 18 proven. 30 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:33,037 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:33,176 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 8 proven. 18 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 16:56:33,176 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:33,177 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1426946514] [2022-03-20 16:56:33,177 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:33,177 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [808193330] [2022-03-20 16:56:33,177 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [808193330] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:33,177 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:33,177 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-03-20 16:56:33,177 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:33,178 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [72592821] [2022-03-20 16:56:33,178 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [72592821] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:33,178 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:33,178 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-20 16:56:33,178 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [694463363] [2022-03-20 16:56:33,178 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:33,178 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 16:56:33,179 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:33,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 16:56:33,179 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2022-03-20 16:56:33,179 INFO L87 Difference]: Start difference. First operand 46 states and 49 transitions. Second operand has 7 states, 7 states have (on average 4.571428571428571) internal successors, (32), 6 states have internal predecessors, (32), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 16:56:33,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:33,243 INFO L93 Difference]: Finished difference Result 62 states and 64 transitions. [2022-03-20 16:56:33,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 16:56:33,243 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.571428571428571) internal successors, (32), 6 states have internal predecessors, (32), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) Word has length 47 [2022-03-20 16:56:33,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:33,244 INFO L225 Difference]: With dead ends: 62 [2022-03-20 16:56:33,244 INFO L226 Difference]: Without dead ends: 52 [2022-03-20 16:56:33,245 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=83, Invalid=127, Unknown=0, NotChecked=0, Total=210 [2022-03-20 16:56:33,245 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:33,245 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 90 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:33,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-20 16:56:33,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-03-20 16:56:33,253 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 36 states have (on average 1.0555555555555556) internal successors, (38), 36 states have internal predecessors, (38), 9 states have call successors, (9), 8 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 16:56:33,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 54 transitions. [2022-03-20 16:56:33,254 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 54 transitions. Word has length 47 [2022-03-20 16:56:33,254 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:33,254 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 54 transitions. [2022-03-20 16:56:33,255 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.571428571428571) internal successors, (32), 6 states have internal predecessors, (32), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 16:56:33,255 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 54 transitions. [2022-03-20 16:56:33,255 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-03-20 16:56:33,255 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:33,255 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:33,283 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:33,471 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-03-20 16:56:33,472 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:33,472 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:33,472 INFO L85 PathProgramCache]: Analyzing trace with hash 468857897, now seen corresponding path program 5 times [2022-03-20 16:56:33,472 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:33,472 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [951014508] [2022-03-20 16:56:33,475 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:33,476 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:33,476 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:33,476 INFO L85 PathProgramCache]: Analyzing trace with hash 468857897, now seen corresponding path program 6 times [2022-03-20 16:56:33,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:33,476 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1252841813] [2022-03-20 16:56:33,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:33,477 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:33,495 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:33,496 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1996370378] [2022-03-20 16:56:33,496 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 16:56:33,496 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:33,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:33,499 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:33,506 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-20 16:56:40,191 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-20 16:56:40,191 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:40,195 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 20 conjunts are in the unsatisfiable core [2022-03-20 16:56:40,197 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:40,449 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 10 proven. 24 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 16:56:40,449 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:40,621 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:40,621 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1252841813] [2022-03-20 16:56:40,621 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:40,622 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1996370378] [2022-03-20 16:56:40,622 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1996370378] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:40,622 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:40,622 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 16:56:40,622 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:40,622 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [951014508] [2022-03-20 16:56:40,622 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [951014508] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:40,622 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:40,623 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 16:56:40,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [90603230] [2022-03-20 16:56:40,623 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:40,623 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 16:56:40,623 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:40,624 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 16:56:40,624 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 16:56:40,624 INFO L87 Difference]: Start difference. First operand 52 states and 54 transitions. Second operand has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-03-20 16:56:40,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:40,719 INFO L93 Difference]: Finished difference Result 60 states and 64 transitions. [2022-03-20 16:56:40,720 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 16:56:40,720 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 53 [2022-03-20 16:56:40,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:40,721 INFO L225 Difference]: With dead ends: 60 [2022-03-20 16:56:40,721 INFO L226 Difference]: Without dead ends: 54 [2022-03-20 16:56:40,721 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:40,722 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 2 mSDsluCounter, 220 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 259 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:40,722 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 259 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:40,723 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-03-20 16:56:40,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-03-20 16:56:40,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 37 states have (on average 1.054054054054054) internal successors, (39), 37 states have internal predecessors, (39), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 16:56:40,731 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 57 transitions. [2022-03-20 16:56:40,732 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 57 transitions. Word has length 53 [2022-03-20 16:56:40,732 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:40,732 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 57 transitions. [2022-03-20 16:56:40,732 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-03-20 16:56:40,732 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 57 transitions. [2022-03-20 16:56:40,733 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-20 16:56:40,733 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:40,733 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:40,743 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:40,933 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-20 16:56:40,934 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:40,934 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:40,934 INFO L85 PathProgramCache]: Analyzing trace with hash -1953308764, now seen corresponding path program 5 times [2022-03-20 16:56:40,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:40,934 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1318360870] [2022-03-20 16:56:40,937 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:40,937 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:40,938 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:40,938 INFO L85 PathProgramCache]: Analyzing trace with hash -1953308764, now seen corresponding path program 6 times [2022-03-20 16:56:40,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:40,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [375227852] [2022-03-20 16:56:40,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:40,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:40,946 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:40,947 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1741803179] [2022-03-20 16:56:40,947 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 16:56:40,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:40,947 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:40,948 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:40,973 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 16:56:41,382 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2022-03-20 16:56:41,382 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:41,384 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 16:56:41,385 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:41,512 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:41,512 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:41,664 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 16:56:41,664 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:41,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [375227852] [2022-03-20 16:56:41,665 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:41,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1741803179] [2022-03-20 16:56:41,665 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1741803179] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:41,665 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:41,665 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-03-20 16:56:41,665 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:41,666 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1318360870] [2022-03-20 16:56:41,666 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1318360870] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:41,666 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:41,666 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 16:56:41,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1917008574] [2022-03-20 16:56:41,668 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:41,668 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 16:56:41,668 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:41,669 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 16:56:41,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:41,669 INFO L87 Difference]: Start difference. First operand 54 states and 57 transitions. Second operand has 8 states, 8 states have (on average 4.75) internal successors, (38), 7 states have internal predecessors, (38), 7 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 16:56:41,738 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:41,739 INFO L93 Difference]: Finished difference Result 70 states and 72 transitions. [2022-03-20 16:56:41,739 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 16:56:41,739 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.75) internal successors, (38), 7 states have internal predecessors, (38), 7 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Word has length 55 [2022-03-20 16:56:41,739 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:41,740 INFO L225 Difference]: With dead ends: 70 [2022-03-20 16:56:41,740 INFO L226 Difference]: Without dead ends: 60 [2022-03-20 16:56:41,741 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=123, Invalid=183, Unknown=0, NotChecked=0, Total=306 [2022-03-20 16:56:41,741 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 12 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:41,741 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 105 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:41,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-03-20 16:56:41,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2022-03-20 16:56:41,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 42 states have (on average 1.0476190476190477) internal successors, (44), 42 states have internal predecessors, (44), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 16:56:41,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 62 transitions. [2022-03-20 16:56:41,752 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 62 transitions. Word has length 55 [2022-03-20 16:56:41,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:41,753 INFO L478 AbstractCegarLoop]: Abstraction has 60 states and 62 transitions. [2022-03-20 16:56:41,753 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.75) internal successors, (38), 7 states have internal predecessors, (38), 7 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 16:56:41,753 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 62 transitions. [2022-03-20 16:56:41,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-03-20 16:56:41,754 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:41,755 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:41,763 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-03-20 16:56:41,961 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 16:56:41,961 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:41,962 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:41,962 INFO L85 PathProgramCache]: Analyzing trace with hash 1425669898, now seen corresponding path program 7 times [2022-03-20 16:56:41,963 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:41,963 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1450719346] [2022-03-20 16:56:41,969 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:41,969 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:41,970 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:41,970 INFO L85 PathProgramCache]: Analyzing trace with hash 1425669898, now seen corresponding path program 8 times [2022-03-20 16:56:41,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:41,970 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [841979874] [2022-03-20 16:56:41,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:41,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:41,978 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:41,979 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [680181241] [2022-03-20 16:56:41,979 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:41,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:41,979 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:41,980 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:42,003 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 16:56:42,636 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:42,636 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:42,637 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 16:56:42,639 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:42,941 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-20 16:56:42,941 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:43,400 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:43,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [841979874] [2022-03-20 16:56:43,400 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:43,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [680181241] [2022-03-20 16:56:43,400 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [680181241] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:43,400 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:43,400 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-20 16:56:43,401 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:43,401 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1450719346] [2022-03-20 16:56:43,401 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1450719346] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:43,401 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:43,401 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-03-20 16:56:43,401 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [583251123] [2022-03-20 16:56:43,401 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:43,402 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 16:56:43,402 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:43,402 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 16:56:43,402 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=188, Unknown=0, NotChecked=0, Total=240 [2022-03-20 16:56:43,402 INFO L87 Difference]: Start difference. First operand 60 states and 62 transitions. Second operand has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-03-20 16:56:43,528 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:43,528 INFO L93 Difference]: Finished difference Result 68 states and 72 transitions. [2022-03-20 16:56:43,529 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 16:56:43,529 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 61 [2022-03-20 16:56:43,529 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:43,530 INFO L225 Difference]: With dead ends: 68 [2022-03-20 16:56:43,530 INFO L226 Difference]: Without dead ends: 62 [2022-03-20 16:56:43,530 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 88 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=62, Invalid=244, Unknown=0, NotChecked=0, Total=306 [2022-03-20 16:56:43,531 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 2 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 326 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:43,531 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 326 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:43,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2022-03-20 16:56:43,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2022-03-20 16:56:43,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 43 states have (on average 1.0465116279069768) internal successors, (45), 43 states have internal predecessors, (45), 11 states have call successors, (11), 9 states have call predecessors, (11), 7 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 16:56:43,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 65 transitions. [2022-03-20 16:56:43,540 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 65 transitions. Word has length 61 [2022-03-20 16:56:43,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:43,541 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 65 transitions. [2022-03-20 16:56:43,541 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-03-20 16:56:43,541 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 65 transitions. [2022-03-20 16:56:43,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-03-20 16:56:43,542 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:43,542 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:43,551 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:43,747 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-20 16:56:43,748 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:43,748 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:43,748 INFO L85 PathProgramCache]: Analyzing trace with hash -1579977147, now seen corresponding path program 7 times [2022-03-20 16:56:43,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:43,748 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1238358440] [2022-03-20 16:56:43,752 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:43,752 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:43,752 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:43,752 INFO L85 PathProgramCache]: Analyzing trace with hash -1579977147, now seen corresponding path program 8 times [2022-03-20 16:56:43,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:43,752 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1610344625] [2022-03-20 16:56:43,752 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:43,753 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:43,761 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:43,761 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1777602251] [2022-03-20 16:56:43,761 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:43,761 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:43,761 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:43,763 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:43,768 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 16:56:43,816 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:43,816 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:43,817 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 15 conjunts are in the unsatisfiable core [2022-03-20 16:56:43,819 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:43,979 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 30 proven. 90 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:43,979 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:44,149 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 12 proven. 50 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-20 16:56:44,149 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:44,149 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1610344625] [2022-03-20 16:56:44,149 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:44,149 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1777602251] [2022-03-20 16:56:44,149 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1777602251] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:44,149 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:44,150 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-03-20 16:56:44,150 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:44,150 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1238358440] [2022-03-20 16:56:44,150 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1238358440] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:44,150 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:44,150 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 16:56:44,150 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [579420390] [2022-03-20 16:56:44,150 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:44,151 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 16:56:44,151 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:44,152 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 16:56:44,152 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:44,152 INFO L87 Difference]: Start difference. First operand 62 states and 65 transitions. Second operand has 9 states, 9 states have (on average 4.888888888888889) internal successors, (44), 8 states have internal predecessors, (44), 8 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 16:56:44,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:44,234 INFO L93 Difference]: Finished difference Result 78 states and 80 transitions. [2022-03-20 16:56:44,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 16:56:44,234 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.888888888888889) internal successors, (44), 8 states have internal predecessors, (44), 8 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Word has length 63 [2022-03-20 16:56:44,234 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:44,236 INFO L225 Difference]: With dead ends: 78 [2022-03-20 16:56:44,237 INFO L226 Difference]: Without dead ends: 68 [2022-03-20 16:56:44,237 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=136, Invalid=206, Unknown=0, NotChecked=0, Total=342 [2022-03-20 16:56:44,238 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:44,238 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 111 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:44,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2022-03-20 16:56:44,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 68. [2022-03-20 16:56:44,247 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 48 states have (on average 1.0416666666666667) internal successors, (50), 48 states have internal predecessors, (50), 11 states have call successors, (11), 10 states have call predecessors, (11), 8 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 16:56:44,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 70 transitions. [2022-03-20 16:56:44,248 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 70 transitions. Word has length 63 [2022-03-20 16:56:44,248 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:44,248 INFO L478 AbstractCegarLoop]: Abstraction has 68 states and 70 transitions. [2022-03-20 16:56:44,248 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.888888888888889) internal successors, (44), 8 states have internal predecessors, (44), 8 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 16:56:44,248 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 70 transitions. [2022-03-20 16:56:44,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-03-20 16:56:44,249 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:44,249 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:44,275 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:44,463 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 16:56:44,463 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:44,464 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:44,464 INFO L85 PathProgramCache]: Analyzing trace with hash -423798549, now seen corresponding path program 9 times [2022-03-20 16:56:44,464 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:44,464 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1739561316] [2022-03-20 16:56:44,467 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:44,467 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:44,467 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:44,467 INFO L85 PathProgramCache]: Analyzing trace with hash -423798549, now seen corresponding path program 10 times [2022-03-20 16:56:44,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:44,467 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [171148676] [2022-03-20 16:56:44,467 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:44,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:44,476 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:44,476 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [96350574] [2022-03-20 16:56:44,476 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 16:56:44,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:44,477 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:44,478 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:44,479 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-20 16:56:44,524 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 16:56:44,524 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:44,526 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-20 16:56:44,527 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:44,764 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 14 proven. 60 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-20 16:56:44,764 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:44,908 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:44,908 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [171148676] [2022-03-20 16:56:44,908 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:44,908 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [96350574] [2022-03-20 16:56:44,908 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [96350574] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:44,908 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:44,908 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-20 16:56:44,908 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:44,908 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1739561316] [2022-03-20 16:56:44,909 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1739561316] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:44,909 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:44,909 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 16:56:44,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1473473539] [2022-03-20 16:56:44,909 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:44,909 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 16:56:44,909 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:44,909 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 16:56:44,909 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:44,910 INFO L87 Difference]: Start difference. First operand 68 states and 70 transitions. Second operand has 11 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2022-03-20 16:56:45,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:45,057 INFO L93 Difference]: Finished difference Result 76 states and 80 transitions. [2022-03-20 16:56:45,057 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 16:56:45,058 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) Word has length 69 [2022-03-20 16:56:45,058 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:45,058 INFO L225 Difference]: With dead ends: 76 [2022-03-20 16:56:45,058 INFO L226 Difference]: Without dead ends: 70 [2022-03-20 16:56:45,059 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 74 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-03-20 16:56:45,059 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 2 mSDsluCounter, 336 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 383 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:45,059 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 383 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:45,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-03-20 16:56:45,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2022-03-20 16:56:45,077 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 49 states have (on average 1.0408163265306123) internal successors, (51), 49 states have internal predecessors, (51), 12 states have call successors, (12), 10 states have call predecessors, (12), 8 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 16:56:45,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 73 transitions. [2022-03-20 16:56:45,077 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 73 transitions. Word has length 69 [2022-03-20 16:56:45,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:45,078 INFO L478 AbstractCegarLoop]: Abstraction has 70 states and 73 transitions. [2022-03-20 16:56:45,078 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2022-03-20 16:56:45,078 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 73 transitions. [2022-03-20 16:56:45,078 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2022-03-20 16:56:45,079 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:45,079 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:45,107 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:45,303 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 16:56:45,304 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:45,304 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:45,304 INFO L85 PathProgramCache]: Analyzing trace with hash -802694170, now seen corresponding path program 9 times [2022-03-20 16:56:45,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:45,304 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1783553516] [2022-03-20 16:56:45,307 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:45,307 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:45,307 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:45,307 INFO L85 PathProgramCache]: Analyzing trace with hash -802694170, now seen corresponding path program 10 times [2022-03-20 16:56:45,307 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:45,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [763126071] [2022-03-20 16:56:45,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:45,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:45,316 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:45,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1527394353] [2022-03-20 16:56:45,316 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 16:56:45,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:45,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:45,328 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:45,330 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-20 16:56:45,384 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 16:56:45,384 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:45,385 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 17 conjunts are in the unsatisfiable core [2022-03-20 16:56:45,387 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:45,562 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 36 proven. 132 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:45,563 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:45,737 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 14 proven. 72 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-20 16:56:45,737 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:45,737 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [763126071] [2022-03-20 16:56:45,737 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:45,737 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1527394353] [2022-03-20 16:56:45,737 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1527394353] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:45,737 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:45,737 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2022-03-20 16:56:45,738 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:45,738 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1783553516] [2022-03-20 16:56:45,738 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1783553516] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:45,738 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:45,738 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-03-20 16:56:45,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [497931014] [2022-03-20 16:56:45,738 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:45,738 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 16:56:45,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:45,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 16:56:45,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:45,739 INFO L87 Difference]: Start difference. First operand 70 states and 73 transitions. Second operand has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 16:56:45,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:45,845 INFO L93 Difference]: Finished difference Result 86 states and 88 transitions. [2022-03-20 16:56:45,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 16:56:45,845 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) Word has length 71 [2022-03-20 16:56:45,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:45,846 INFO L225 Difference]: With dead ends: 86 [2022-03-20 16:56:45,846 INFO L226 Difference]: Without dead ends: 76 [2022-03-20 16:56:45,847 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 128 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=149, Invalid=231, Unknown=0, NotChecked=0, Total=380 [2022-03-20 16:56:45,847 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:45,848 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 135 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 16:56:45,848 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-03-20 16:56:45,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 76. [2022-03-20 16:56:45,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 54 states have (on average 1.037037037037037) internal successors, (56), 54 states have internal predecessors, (56), 12 states have call successors, (12), 11 states have call predecessors, (12), 9 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 16:56:45,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 78 transitions. [2022-03-20 16:56:45,857 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 78 transitions. Word has length 71 [2022-03-20 16:56:45,857 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:45,857 INFO L478 AbstractCegarLoop]: Abstraction has 76 states and 78 transitions. [2022-03-20 16:56:45,857 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 16:56:45,857 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 78 transitions. [2022-03-20 16:56:45,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2022-03-20 16:56:45,858 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:45,858 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:45,888 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:46,071 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:46,071 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:46,072 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:46,072 INFO L85 PathProgramCache]: Analyzing trace with hash 540885452, now seen corresponding path program 11 times [2022-03-20 16:56:46,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:46,072 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [522899538] [2022-03-20 16:56:46,075 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:46,075 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:46,075 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:46,075 INFO L85 PathProgramCache]: Analyzing trace with hash 540885452, now seen corresponding path program 12 times [2022-03-20 16:56:46,075 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:46,076 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [466347504] [2022-03-20 16:56:46,076 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:46,076 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:46,083 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:46,084 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2043894172] [2022-03-20 16:56:46,084 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 16:56:46,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:46,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:46,085 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:46,087 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-20 16:56:51,548 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-03-20 16:56:51,548 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:51,564 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 33 conjunts are in the unsatisfiable core [2022-03-20 16:56:51,566 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:51,908 INFO L134 CoverageAnalysis]: Checked inductivity of 212 backedges. 16 proven. 84 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 16:56:51,908 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:52,349 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:52,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [466347504] [2022-03-20 16:56:52,350 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:52,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2043894172] [2022-03-20 16:56:52,350 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2043894172] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:52,350 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:52,350 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-03-20 16:56:52,350 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:52,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [522899538] [2022-03-20 16:56:52,350 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [522899538] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:52,350 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:52,350 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-03-20 16:56:52,350 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1183398582] [2022-03-20 16:56:52,350 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:52,351 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 16:56:52,351 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:52,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 16:56:52,351 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=270, Unknown=0, NotChecked=0, Total=342 [2022-03-20 16:56:52,352 INFO L87 Difference]: Start difference. First operand 76 states and 78 transitions. Second operand has 12 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 9 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-03-20 16:56:52,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:52,543 INFO L93 Difference]: Finished difference Result 84 states and 88 transitions. [2022-03-20 16:56:52,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 16:56:52,543 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 9 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) Word has length 77 [2022-03-20 16:56:52,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:52,544 INFO L225 Difference]: With dead ends: 84 [2022-03-20 16:56:52,544 INFO L226 Difference]: Without dead ends: 78 [2022-03-20 16:56:52,545 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 109 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2022-03-20 16:56:52,545 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 2 mSDsluCounter, 403 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 454 SdHoareTripleChecker+Invalid, 175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:52,545 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 454 Invalid, 175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:52,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2022-03-20 16:56:52,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 78. [2022-03-20 16:56:52,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 55 states have (on average 1.0363636363636364) internal successors, (57), 55 states have internal predecessors, (57), 13 states have call successors, (13), 11 states have call predecessors, (13), 9 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 16:56:52,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 81 transitions. [2022-03-20 16:56:52,564 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 81 transitions. Word has length 77 [2022-03-20 16:56:52,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:52,564 INFO L478 AbstractCegarLoop]: Abstraction has 78 states and 81 transitions. [2022-03-20 16:56:52,564 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 9 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-03-20 16:56:52,565 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 81 transitions. [2022-03-20 16:56:52,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-03-20 16:56:52,565 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:52,565 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:52,576 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:52,766 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-20 16:56:52,766 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:52,766 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:52,766 INFO L85 PathProgramCache]: Analyzing trace with hash -1454305145, now seen corresponding path program 11 times [2022-03-20 16:56:52,766 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:52,766 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1760301255] [2022-03-20 16:56:52,768 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:52,769 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:52,769 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:52,769 INFO L85 PathProgramCache]: Analyzing trace with hash -1454305145, now seen corresponding path program 12 times [2022-03-20 16:56:52,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:52,769 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1212563499] [2022-03-20 16:56:52,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:52,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:52,778 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:52,778 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1228887687] [2022-03-20 16:56:52,778 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 16:56:52,778 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:52,778 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:52,780 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:52,799 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-20 16:56:53,017 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2022-03-20 16:56:53,017 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:53,019 INFO L263 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-20 16:56:53,021 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:53,217 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 42 proven. 182 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:53,217 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:53,381 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 16 proven. 98 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 16:56:53,381 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:53,381 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1212563499] [2022-03-20 16:56:53,381 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:53,381 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1228887687] [2022-03-20 16:56:53,381 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1228887687] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:53,381 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:53,381 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 14 [2022-03-20 16:56:53,382 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:53,382 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1760301255] [2022-03-20 16:56:53,382 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1760301255] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:53,382 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:53,382 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 16:56:53,382 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [958528333] [2022-03-20 16:56:53,382 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:53,382 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 16:56:53,382 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:53,383 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 16:56:53,383 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:53,383 INFO L87 Difference]: Start difference. First operand 78 states and 81 transitions. Second operand has 11 states, 11 states have (on average 5.090909090909091) internal successors, (56), 10 states have internal predecessors, (56), 10 states have call successors, (12), 10 states have call predecessors, (12), 9 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 16:56:53,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:53,506 INFO L93 Difference]: Finished difference Result 94 states and 96 transitions. [2022-03-20 16:56:53,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-03-20 16:56:53,507 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 5.090909090909091) internal successors, (56), 10 states have internal predecessors, (56), 10 states have call successors, (12), 10 states have call predecessors, (12), 9 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) Word has length 79 [2022-03-20 16:56:53,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:53,508 INFO L225 Difference]: With dead ends: 94 [2022-03-20 16:56:53,508 INFO L226 Difference]: Without dead ends: 84 [2022-03-20 16:56:53,509 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 144 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=162, Invalid=258, Unknown=0, NotChecked=0, Total=420 [2022-03-20 16:56:53,509 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 24 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:53,509 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 105 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:53,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-03-20 16:56:53,520 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2022-03-20 16:56:53,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 60 states have (on average 1.0333333333333334) internal successors, (62), 60 states have internal predecessors, (62), 13 states have call successors, (13), 12 states have call predecessors, (13), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 16:56:53,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 86 transitions. [2022-03-20 16:56:53,521 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 86 transitions. Word has length 79 [2022-03-20 16:56:53,521 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:53,521 INFO L478 AbstractCegarLoop]: Abstraction has 84 states and 86 transitions. [2022-03-20 16:56:53,521 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 5.090909090909091) internal successors, (56), 10 states have internal predecessors, (56), 10 states have call successors, (12), 10 states have call predecessors, (12), 9 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 16:56:53,521 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 86 transitions. [2022-03-20 16:56:53,522 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-03-20 16:56:53,522 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:53,522 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:53,528 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:53,728 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-20 16:56:53,728 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:53,729 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:53,729 INFO L85 PathProgramCache]: Analyzing trace with hash -1082476115, now seen corresponding path program 13 times [2022-03-20 16:56:53,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:53,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1057535124] [2022-03-20 16:56:53,731 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:53,731 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:53,731 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:53,731 INFO L85 PathProgramCache]: Analyzing trace with hash -1082476115, now seen corresponding path program 14 times [2022-03-20 16:56:53,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:53,732 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [474911574] [2022-03-20 16:56:53,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:53,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:53,749 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:53,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1131507615] [2022-03-20 16:56:53,749 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:53,749 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:53,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:53,752 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:53,762 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-20 16:56:54,965 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:54,965 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:54,967 INFO L263 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-20 16:56:54,969 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:55,275 INFO L134 CoverageAnalysis]: Checked inductivity of 274 backedges. 18 proven. 112 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-03-20 16:56:55,275 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:55,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:55,415 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [474911574] [2022-03-20 16:56:55,415 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:55,415 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1131507615] [2022-03-20 16:56:55,415 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1131507615] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:55,415 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:55,415 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-20 16:56:55,415 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:55,416 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1057535124] [2022-03-20 16:56:55,416 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1057535124] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:55,416 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:55,416 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-03-20 16:56:55,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [491642583] [2022-03-20 16:56:55,416 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:55,416 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 16:56:55,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:55,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 16:56:55,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-03-20 16:56:55,417 INFO L87 Difference]: Start difference. First operand 84 states and 86 transitions. Second operand has 13 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2022-03-20 16:56:55,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:55,614 INFO L93 Difference]: Finished difference Result 92 states and 96 transitions. [2022-03-20 16:56:55,614 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 16:56:55,614 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) Word has length 85 [2022-03-20 16:56:55,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:55,615 INFO L225 Difference]: With dead ends: 92 [2022-03-20 16:56:55,615 INFO L226 Difference]: Without dead ends: 86 [2022-03-20 16:56:55,616 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 88 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-03-20 16:56:55,616 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 2 mSDsluCounter, 486 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 542 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:55,616 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 542 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 213 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 16:56:55,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2022-03-20 16:56:55,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2022-03-20 16:56:55,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 61 states have (on average 1.0327868852459017) internal successors, (63), 61 states have internal predecessors, (63), 14 states have call successors, (14), 12 states have call predecessors, (14), 10 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 16:56:55,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 89 transitions. [2022-03-20 16:56:55,633 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 89 transitions. Word has length 85 [2022-03-20 16:56:55,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:55,634 INFO L478 AbstractCegarLoop]: Abstraction has 86 states and 89 transitions. [2022-03-20 16:56:55,634 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2022-03-20 16:56:55,634 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 89 transitions. [2022-03-20 16:56:55,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-03-20 16:56:55,634 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:55,634 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:55,642 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:55,835 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-20 16:56:55,835 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:55,835 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:55,836 INFO L85 PathProgramCache]: Analyzing trace with hash 1863324712, now seen corresponding path program 13 times [2022-03-20 16:56:55,836 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:55,836 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [56388086] [2022-03-20 16:56:55,838 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:55,838 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:55,838 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:55,838 INFO L85 PathProgramCache]: Analyzing trace with hash 1863324712, now seen corresponding path program 14 times [2022-03-20 16:56:55,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:55,838 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [596698462] [2022-03-20 16:56:55,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:55,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:55,856 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:55,856 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [301590383] [2022-03-20 16:56:55,856 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 16:56:55,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:55,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:55,857 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:55,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-03-20 16:56:55,918 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 16:56:55,918 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:55,920 INFO L263 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 21 conjunts are in the unsatisfiable core [2022-03-20 16:56:55,923 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:56,104 INFO L134 CoverageAnalysis]: Checked inductivity of 290 backedges. 48 proven. 240 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:56,104 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:56,267 INFO L134 CoverageAnalysis]: Checked inductivity of 290 backedges. 18 proven. 128 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-03-20 16:56:56,267 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:56,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [596698462] [2022-03-20 16:56:56,267 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:56,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [301590383] [2022-03-20 16:56:56,268 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [301590383] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:56,268 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:56,268 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 14 [2022-03-20 16:56:56,268 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:56,268 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [56388086] [2022-03-20 16:56:56,268 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [56388086] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:56,268 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:56,268 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-03-20 16:56:56,268 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1945558101] [2022-03-20 16:56:56,269 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:56,269 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 16:56:56,269 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:56,269 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 16:56:56,269 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-20 16:56:56,270 INFO L87 Difference]: Start difference. First operand 86 states and 89 transitions. Second operand has 12 states, 12 states have (on average 5.166666666666667) internal successors, (62), 11 states have internal predecessors, (62), 11 states have call successors, (13), 11 states have call predecessors, (13), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 16:56:56,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:56,410 INFO L93 Difference]: Finished difference Result 102 states and 104 transitions. [2022-03-20 16:56:56,410 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-03-20 16:56:56,410 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 5.166666666666667) internal successors, (62), 11 states have internal predecessors, (62), 11 states have call successors, (13), 11 states have call predecessors, (13), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Word has length 87 [2022-03-20 16:56:56,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:56,411 INFO L225 Difference]: With dead ends: 102 [2022-03-20 16:56:56,411 INFO L226 Difference]: Without dead ends: 92 [2022-03-20 16:56:56,412 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 181 GetRequests, 160 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=175, Invalid=287, Unknown=0, NotChecked=0, Total=462 [2022-03-20 16:56:56,412 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:56,412 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 138 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:56,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-03-20 16:56:56,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2022-03-20 16:56:56,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 66 states have (on average 1.0303030303030303) internal successors, (68), 66 states have internal predecessors, (68), 14 states have call successors, (14), 13 states have call predecessors, (14), 11 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 16:56:56,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 94 transitions. [2022-03-20 16:56:56,424 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 94 transitions. Word has length 87 [2022-03-20 16:56:56,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:56,424 INFO L478 AbstractCegarLoop]: Abstraction has 92 states and 94 transitions. [2022-03-20 16:56:56,424 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 5.166666666666667) internal successors, (62), 11 states have internal predecessors, (62), 11 states have call successors, (13), 11 states have call predecessors, (13), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 16:56:56,425 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 94 transitions. [2022-03-20 16:56:56,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-03-20 16:56:56,425 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:56,425 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:56,454 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:56,639 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:56,639 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:56,640 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:56,640 INFO L85 PathProgramCache]: Analyzing trace with hash -243875698, now seen corresponding path program 15 times [2022-03-20 16:56:56,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:56,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [515302317] [2022-03-20 16:56:56,642 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:56,642 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:56,642 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:56,642 INFO L85 PathProgramCache]: Analyzing trace with hash -243875698, now seen corresponding path program 16 times [2022-03-20 16:56:56,642 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:56,642 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [693460801] [2022-03-20 16:56:56,642 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:56,642 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:56,650 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:56,650 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [60172488] [2022-03-20 16:56:56,650 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 16:56:56,650 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:56,650 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:56,652 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:56,677 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-03-20 16:56:56,711 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 16:56:56,712 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:56,713 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-20 16:56:56,715 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:57,057 INFO L134 CoverageAnalysis]: Checked inductivity of 344 backedges. 20 proven. 144 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-03-20 16:56:57,057 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:57,265 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:57,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [693460801] [2022-03-20 16:56:57,265 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:57,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [60172488] [2022-03-20 16:56:57,266 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [60172488] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:56:57,266 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:56:57,266 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-03-20 16:56:57,266 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:57,266 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [515302317] [2022-03-20 16:56:57,266 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [515302317] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:57,266 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:57,266 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-03-20 16:56:57,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [299470782] [2022-03-20 16:56:57,266 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:57,267 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 16:56:57,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:57,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 16:56:57,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-03-20 16:56:57,267 INFO L87 Difference]: Start difference. First operand 92 states and 94 transitions. Second operand has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 13 states have internal predecessors, (40), 11 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2022-03-20 16:56:57,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:57,479 INFO L93 Difference]: Finished difference Result 100 states and 104 transitions. [2022-03-20 16:56:57,479 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 16:56:57,480 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 13 states have internal predecessors, (40), 11 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) Word has length 93 [2022-03-20 16:56:57,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:57,480 INFO L225 Difference]: With dead ends: 100 [2022-03-20 16:56:57,480 INFO L226 Difference]: Without dead ends: 94 [2022-03-20 16:56:57,481 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 95 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-03-20 16:56:57,481 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 2 mSDsluCounter, 566 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 626 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:57,482 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 626 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 256 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 16:56:57,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2022-03-20 16:56:57,493 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 94. [2022-03-20 16:56:57,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 67 states have (on average 1.0298507462686568) internal successors, (69), 67 states have internal predecessors, (69), 15 states have call successors, (15), 13 states have call predecessors, (15), 11 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 16:56:57,494 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 97 transitions. [2022-03-20 16:56:57,494 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 97 transitions. Word has length 93 [2022-03-20 16:56:57,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:57,495 INFO L478 AbstractCegarLoop]: Abstraction has 94 states and 97 transitions. [2022-03-20 16:56:57,495 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 13 states have internal predecessors, (40), 11 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2022-03-20 16:56:57,495 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 97 transitions. [2022-03-20 16:56:57,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-03-20 16:56:57,496 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:57,496 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:57,522 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:57,719 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:57,720 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:57,720 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:57,720 INFO L85 PathProgramCache]: Analyzing trace with hash 304473801, now seen corresponding path program 15 times [2022-03-20 16:56:57,720 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:57,720 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1750486585] [2022-03-20 16:56:57,722 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:57,722 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:57,722 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:57,722 INFO L85 PathProgramCache]: Analyzing trace with hash 304473801, now seen corresponding path program 16 times [2022-03-20 16:56:57,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:57,722 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303672286] [2022-03-20 16:56:57,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:57,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:57,730 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:57,730 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [669063179] [2022-03-20 16:56:57,730 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 16:56:57,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:57,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:57,732 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:57,737 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-03-20 16:56:57,798 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 16:56:57,798 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:56:57,800 INFO L263 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-20 16:56:57,802 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:56:58,030 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 54 proven. 306 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 16:56:58,031 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:56:58,239 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 20 proven. 162 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-03-20 16:56:58,239 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:56:58,239 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1303672286] [2022-03-20 16:56:58,240 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:56:58,240 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [669063179] [2022-03-20 16:56:58,240 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [669063179] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 16:56:58,240 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 16:56:58,240 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2022-03-20 16:56:58,240 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:56:58,240 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1750486585] [2022-03-20 16:56:58,240 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1750486585] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:56:58,240 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:56:58,240 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-03-20 16:56:58,240 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1244847784] [2022-03-20 16:56:58,241 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:56:58,241 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 16:56:58,241 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:58,241 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 16:56:58,241 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=88, Unknown=0, NotChecked=0, Total=156 [2022-03-20 16:56:58,242 INFO L87 Difference]: Start difference. First operand 94 states and 97 transitions. Second operand has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 12 states have call successors, (14), 12 states have call predecessors, (14), 11 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 16:56:58,395 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:56:58,395 INFO L93 Difference]: Finished difference Result 110 states and 112 transitions. [2022-03-20 16:56:58,396 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-20 16:56:58,396 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 12 states have call successors, (14), 12 states have call predecessors, (14), 11 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) Word has length 95 [2022-03-20 16:56:58,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:56:58,400 INFO L225 Difference]: With dead ends: 110 [2022-03-20 16:56:58,400 INFO L226 Difference]: Without dead ends: 100 [2022-03-20 16:56:58,403 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 198 GetRequests, 177 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=176, Invalid=286, Unknown=0, NotChecked=0, Total=462 [2022-03-20 16:56:58,404 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 12 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 16:56:58,405 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 135 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 16:56:58,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2022-03-20 16:56:58,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 100. [2022-03-20 16:56:58,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 72 states have (on average 1.0277777777777777) internal successors, (74), 72 states have internal predecessors, (74), 15 states have call successors, (15), 14 states have call predecessors, (15), 12 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 16:56:58,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 102 transitions. [2022-03-20 16:56:58,423 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 102 transitions. Word has length 95 [2022-03-20 16:56:58,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:56:58,424 INFO L478 AbstractCegarLoop]: Abstraction has 100 states and 102 transitions. [2022-03-20 16:56:58,424 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 12 states have call successors, (14), 12 states have call predecessors, (14), 11 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 16:56:58,424 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 102 transitions. [2022-03-20 16:56:58,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2022-03-20 16:56:58,425 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:56:58,425 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:56:58,455 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-03-20 16:56:58,639 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2022-03-20 16:56:58,639 INFO L403 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:56:58,640 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:56:58,640 INFO L85 PathProgramCache]: Analyzing trace with hash 1379030639, now seen corresponding path program 17 times [2022-03-20 16:56:58,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:56:58,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [230032229] [2022-03-20 16:56:58,643 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:56:58,643 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:56:58,643 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:56:58,643 INFO L85 PathProgramCache]: Analyzing trace with hash 1379030639, now seen corresponding path program 18 times [2022-03-20 16:56:58,643 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:56:58,643 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1002095179] [2022-03-20 16:56:58,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:56:58,644 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:56:58,654 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:56:58,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [507102] [2022-03-20 16:56:58,655 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 16:56:58,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:56:58,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:56:58,656 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:56:58,671 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-03-20 16:59:10,823 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-03-20 16:59:10,823 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 16:59:10,893 INFO L263 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-20 16:59:10,895 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 16:59:11,309 INFO L134 CoverageAnalysis]: Checked inductivity of 422 backedges. 22 proven. 180 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-03-20 16:59:11,309 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 16:59:11,995 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 16:59:11,995 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1002095179] [2022-03-20 16:59:11,996 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 16:59:11,996 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [507102] [2022-03-20 16:59:11,996 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [507102] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 16:59:11,996 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 16:59:11,996 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-03-20 16:59:11,996 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 16:59:11,996 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [230032229] [2022-03-20 16:59:11,996 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [230032229] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 16:59:11,996 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 16:59:11,997 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-03-20 16:59:11,997 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1157020751] [2022-03-20 16:59:11,997 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 16:59:11,997 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 16:59:11,997 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 16:59:11,997 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 16:59:11,998 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=474, Unknown=0, NotChecked=0, Total=600 [2022-03-20 16:59:11,998 INFO L87 Difference]: Start difference. First operand 100 states and 102 transitions. Second operand has 15 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2022-03-20 16:59:12,261 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 16:59:12,261 INFO L93 Difference]: Finished difference Result 108 states and 112 transitions. [2022-03-20 16:59:12,262 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 16:59:12,262 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) Word has length 101 [2022-03-20 16:59:12,262 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 16:59:12,263 INFO L225 Difference]: With dead ends: 108 [2022-03-20 16:59:12,263 INFO L226 Difference]: Without dead ends: 102 [2022-03-20 16:59:12,263 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 151 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=136, Invalid=566, Unknown=0, NotChecked=0, Total=702 [2022-03-20 16:59:12,264 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 2 mSDsluCounter, 652 mSDsCounter, 0 mSdLazyCounter, 303 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 716 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 303 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 16:59:12,264 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 716 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 303 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 16:59:12,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-03-20 16:59:12,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-03-20 16:59:12,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 73 states have (on average 1.0273972602739727) internal successors, (75), 73 states have internal predecessors, (75), 16 states have call successors, (16), 14 states have call predecessors, (16), 12 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 16:59:12,277 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 105 transitions. [2022-03-20 16:59:12,277 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 105 transitions. Word has length 101 [2022-03-20 16:59:12,278 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 16:59:12,278 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 105 transitions. [2022-03-20 16:59:12,278 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2022-03-20 16:59:12,278 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 105 transitions. [2022-03-20 16:59:12,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-03-20 16:59:12,279 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 16:59:12,279 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 16:59:12,329 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-03-20 16:59:12,495 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2022-03-20 16:59:12,495 INFO L403 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 16:59:12,496 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 16:59:12,496 INFO L85 PathProgramCache]: Analyzing trace with hash 844335210, now seen corresponding path program 17 times [2022-03-20 16:59:12,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 16:59:12,496 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2063275408] [2022-03-20 16:59:12,499 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-20 16:59:12,499 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-03-20 16:59:12,499 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-03-20 16:59:12,499 INFO L85 PathProgramCache]: Analyzing trace with hash 844335210, now seen corresponding path program 18 times [2022-03-20 16:59:12,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 16:59:12,499 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1794321203] [2022-03-20 16:59:12,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 16:59:12,499 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 16:59:12,506 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 16:59:12,507 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1140545065] [2022-03-20 16:59:12,507 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 16:59:12,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 16:59:12,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 16:59:12,508 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 16:59:12,509 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-03-20 16:59:13,142 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2022-03-20 16:59:13,142 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-03-20 16:59:13,142 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders.