./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_10-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-simple/fibo_10-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 16:05:03,258 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 16:05:03,324 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-09 16:05:03,331 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 16:05:03,331 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 16:05:03,371 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 16:05:03,373 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 16:05:03,373 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 16:05:03,374 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 16:05:03,375 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 16:05:03,376 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 16:05:03,377 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 16:05:03,377 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 16:05:03,377 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 16:05:03,378 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 16:05:03,380 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 16:05:03,380 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 16:05:03,380 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 16:05:03,380 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 16:05:03,381 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 16:05:03,381 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 16:05:03,382 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 16:05:03,383 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 16:05:03,383 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 16:05:03,383 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 16:05:03,384 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 16:05:03,384 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 16:05:03,384 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 16:05:03,384 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 16:05:03,385 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 16:05:03,385 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 16:05:03,385 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 16:05:03,386 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 16:05:03,386 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 16:05:03,386 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 16:05:03,386 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 16:05:03,387 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 16:05:03,387 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 16:05:03,388 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 16:05:03,388 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR 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.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 [2024-11-09 16:05:03,668 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 16:05:03,698 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 16:05:03,700 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 16:05:03,702 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 16:05:03,704 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 16:05:03,706 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-11-09 16:05:05,191 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 16:05:05,377 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 16:05:05,377 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-11-09 16:05:05,383 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5e2c2a210/1984345ff692454db5190f7a24e7039b/FLAG629bbb423 [2024-11-09 16:05:05,397 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5e2c2a210/1984345ff692454db5190f7a24e7039b [2024-11-09 16:05:05,399 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 16:05:05,401 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 16:05:05,402 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 16:05:05,402 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 16:05:05,409 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 16:05:05,410 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,411 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@660d6c4a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05, skipping insertion in model container [2024-11-09 16:05:05,411 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,426 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 16:05:05,598 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:05:05,611 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 16:05:05,626 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:05:05,642 INFO L204 MainTranslator]: Completed translation [2024-11-09 16:05:05,643 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05 WrapperNode [2024-11-09 16:05:05,643 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 16:05:05,644 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 16:05:05,644 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 16:05:05,644 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 16:05:05,652 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,659 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,676 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-09 16:05:05,677 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 16:05:05,677 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 16:05:05,678 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 16:05:05,678 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 16:05:05,687 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,687 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,689 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,697 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 16:05:05,698 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,698 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,701 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,704 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,705 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,705 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,707 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 16:05:05,707 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 16:05:05,708 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 16:05:05,708 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 16:05:05,708 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (1/1) ... [2024-11-09 16:05:05,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,751 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:05,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-09 16:05:05,807 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 16:05:05,808 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 16:05:05,808 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 16:05:05,808 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 16:05:05,808 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-09 16:05:05,808 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-09 16:05:05,869 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 16:05:05,871 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 16:05:05,989 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 16:05:05,991 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 16:05:06,003 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 16:05:06,004 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 16:05:06,005 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:06 BoogieIcfgContainer [2024-11-09 16:05:06,005 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 16:05:06,006 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 16:05:06,007 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 16:05:06,011 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 16:05:06,011 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:06,011 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 04:05:05" (1/3) ... [2024-11-09 16:05:06,012 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@47add81c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:05:06, skipping insertion in model container [2024-11-09 16:05:06,012 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:06,013 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:05" (2/3) ... [2024-11-09 16:05:06,013 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@47add81c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:05:06, skipping insertion in model container [2024-11-09 16:05:06,013 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:06,013 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:06" (3/3) ... [2024-11-09 16:05:06,014 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_10-1.c [2024-11-09 16:05:06,152 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 16:05:06,153 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 16:05:06,153 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 16:05:06,153 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 16:05:06,154 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 16:05:06,154 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 16:05:06,154 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 16:05:06,154 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 16:05:06,159 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 16:05:06,179 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:06,179 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:06,179 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:06,184 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:05:06,185 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:06,185 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 16:05:06,185 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 16:05:06,187 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:06,188 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:06,188 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:06,188 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:05:06,188 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:06,196 INFO L745 eck$LassoCheckResult]: Stem: 17#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 9#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 4#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 11#$Ultimate##0true [2024-11-09 16:05:06,197 INFO L747 eck$LassoCheckResult]: Loop: 11#$Ultimate##0true ~n := #in~n; 5#L8true assume !(~n < 1); 7#L10true assume !(1 == ~n); 13#L13true call #t~ret4 := fibo(~n - 1);< 11#$Ultimate##0true [2024-11-09 16:05:06,205 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:06,205 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-11-09 16:05:06,215 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:06,216 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1623518541] [2024-11-09 16:05:06,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:06,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:06,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:06,322 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:06,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:06,353 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:06,357 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:06,357 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-11-09 16:05:06,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:06,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1745523371] [2024-11-09 16:05:06,358 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:06,358 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:06,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:06,370 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:06,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:06,377 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:06,380 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:06,380 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-11-09 16:05:06,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:06,384 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2109534218] [2024-11-09 16:05:06,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:06,384 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:06,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:06,404 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:06,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:06,417 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:06,560 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:06,560 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:06,560 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:06,561 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:06,561 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:06,561 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,561 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:06,561 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:06,561 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-11-09 16:05:06,562 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:06,562 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:06,579 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,593 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,599 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,601 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,614 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,690 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:06,690 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:06,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,693 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,696 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:06,697 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-09 16:05:06,698 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:06,698 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:06,718 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:06,719 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:06,734 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:06,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,736 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,737 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:06,738 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-09 16:05:06,739 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:06,739 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:06,751 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:06,751 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:06,766 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-09 16:05:06,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,769 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:06,770 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-09 16:05:06,771 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:06,771 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:06,785 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:06,786 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:06,797 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-09 16:05:06,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,798 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,800 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:06,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-09 16:05:06,802 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:06,803 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:06,831 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-09 16:05:06,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,833 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:06,834 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-09 16:05:06,835 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:06,835 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:06,904 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:06,909 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:06,909 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:06,909 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:06,910 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:06,910 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:06,910 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:06,910 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,910 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:06,910 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:06,910 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-11-09 16:05:06,910 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:06,910 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:06,912 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,916 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,920 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,925 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,938 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,995 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:06,998 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:06,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:07,001 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:07,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-09 16:05:07,003 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:07,013 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:07,014 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:07,014 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:07,014 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:07,014 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:07,016 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:07,016 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:07,018 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:07,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:07,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:07,030 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:07,031 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:07,032 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-09 16:05:07,032 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:07,042 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:07,043 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:07,043 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:07,043 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:07,043 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:07,044 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:07,044 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:07,047 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:07,058 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-09 16:05:07,058 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:07,059 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:07,060 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:07,061 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-09 16:05:07,062 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:07,073 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:07,073 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:07,073 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:07,073 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:07,073 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:07,074 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:07,074 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:07,076 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:07,087 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:07,088 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:07,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:07,089 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:07,090 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-09 16:05:07,093 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:07,106 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:07,106 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:07,106 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:07,106 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:07,107 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:07,108 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:07,108 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:07,111 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:07,114 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:07,114 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:07,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:07,116 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:07,141 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:07,142 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-09 16:05:07,142 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:07,143 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:07,143 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:07,143 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-09 16:05:07,154 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-11-09 16:05:07,158 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:07,184 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:07,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:07,213 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 16:05:07,215 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:07,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:07,245 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:07,246 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:07,296 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:07,328 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-09 16:05:07,330 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:05:07,449 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 41 states and 54 transitions. Complement of second has 16 states. [2024-11-09 16:05:07,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:07,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:05:07,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-09 16:05:07,458 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-09 16:05:07,459 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:07,459 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-09 16:05:07,459 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:07,459 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-09 16:05:07,460 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:07,460 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-09 16:05:07,463 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:07,469 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-09 16:05:07,470 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-09 16:05:07,471 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-09 16:05:07,471 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-09 16:05:07,472 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:07,472 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-09 16:05:07,485 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-09 16:05:07,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-09 16:05:07,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:07,495 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-09 16:05:07,496 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:05:07,496 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:05:07,496 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 16:05:07,497 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-09 16:05:07,497 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:07,498 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:07,498 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:07,499 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:07,499 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:07,499 INFO L745 eck$LassoCheckResult]: Stem: 135#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 136#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 121#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 120#$Ultimate##0 ~n := #in~n; 122#L8 assume !(~n < 1); 134#L10 assume !(1 == ~n); 124#L13 call #t~ret4 := fibo(~n - 1);< 123#$Ultimate##0 ~n := #in~n; 125#L8 assume ~n < 1;#res := 0; 131#fiboFINAL assume true; 132#fiboEXIT >#35#return; 127#L13-1 [2024-11-09 16:05:07,499 INFO L747 eck$LassoCheckResult]: Loop: 127#L13-1 call #t~ret5 := fibo(~n - 2);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume !(~n < 1); 139#L10 assume !(1 == ~n); 126#L13 call #t~ret4 := fibo(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume ~n < 1;#res := 0; 130#fiboFINAL assume true; 137#fiboEXIT >#35#return; 127#L13-1 [2024-11-09 16:05:07,500 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:07,500 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-11-09 16:05:07,500 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:07,500 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [489892421] [2024-11-09 16:05:07,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:07,501 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:07,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:07,569 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:07,661 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:05:07,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:07,721 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 16:05:07,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:07,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [489892421] [2024-11-09 16:05:07,723 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [489892421] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:07,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:07,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:05:07,727 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1789211897] [2024-11-09 16:05:07,728 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:07,730 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:07,731 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:07,732 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-11-09 16:05:07,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:07,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [221760444] [2024-11-09 16:05:07,735 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:07,735 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:07,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:07,811 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:07,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:07,860 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 16:05:07,861 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:07,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [221760444] [2024-11-09 16:05:07,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [221760444] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:07,862 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:07,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:05:07,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1786777310] [2024-11-09 16:05:07,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:07,863 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:07,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:07,865 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 16:05:07,866 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-09 16:05:07,867 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:07,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:07,943 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-09 16:05:07,943 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-09 16:05:07,944 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:07,945 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-09 16:05:07,946 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-09 16:05:07,946 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-09 16:05:07,946 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-09 16:05:07,946 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:07,946 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:07,946 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-09 16:05:07,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 16:05:07,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-09 16:05:07,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-09 16:05:07,951 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:07,952 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 16:05:07,953 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:07,954 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 16:05:07,954 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-09 16:05:07,955 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:07,956 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:07,957 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:07,957 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:07,957 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:07,958 INFO L745 eck$LassoCheckResult]: Stem: 205#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 206#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 199#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 202#$Ultimate##0 ~n := #in~n; 197#L8 assume !(~n < 1); 208#L10 assume !(1 == ~n); 196#L13 call #t~ret4 := fibo(~n - 1);< 195#$Ultimate##0 ~n := #in~n; 198#L8 assume !(~n < 1); 214#L10 assume 1 == ~n;#res := 1; 213#fiboFINAL assume true; 211#fiboEXIT >#35#return; 192#L13-1 [2024-11-09 16:05:07,958 INFO L747 eck$LassoCheckResult]: Loop: 192#L13-1 call #t~ret5 := fibo(~n - 2);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume !(1 == ~n); 193#L13 call #t~ret4 := fibo(~n - 1);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume 1 == ~n;#res := 1; 209#fiboFINAL assume true; 210#fiboEXIT >#35#return; 192#L13-1 [2024-11-09 16:05:07,959 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:07,959 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-11-09 16:05:07,959 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:07,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2108812045] [2024-11-09 16:05:07,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:07,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:07,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:08,048 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:05:08,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:08,096 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:08,097 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:08,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2108812045] [2024-11-09 16:05:08,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2108812045] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:08,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1367166513] [2024-11-09 16:05:08,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:08,098 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:08,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,101 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) [2024-11-09 16:05:08,103 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 16:05:08,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:08,143 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:08,144 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:08,177 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:08,178 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:08,293 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:08,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1367166513] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:08,293 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:08,293 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-09 16:05:08,294 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1820594185] [2024-11-09 16:05:08,294 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:08,294 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:08,295 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:08,295 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-11-09 16:05:08,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:08,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [393048765] [2024-11-09 16:05:08,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:08,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:08,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:08,300 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:08,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:08,304 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:08,434 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:08,434 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:08,434 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:08,434 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:08,434 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:08,434 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,435 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:08,435 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:08,435 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-11-09 16:05:08,435 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:08,435 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:08,436 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,440 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,443 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,446 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,452 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,490 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:08,491 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:08,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,493 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,494 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-09 16:05:08,495 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:08,495 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:08,511 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:08,511 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#in~n=2} Honda state: {fibo_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:08,526 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-09 16:05:08,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,528 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,529 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,531 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-09 16:05:08,532 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:08,532 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:08,545 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:08,545 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:08,560 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-09 16:05:08,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,563 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,564 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-09 16:05:08,565 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:08,565 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:08,580 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:08,580 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:08,596 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-09 16:05:08,596 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,598 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,600 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-09 16:05:08,601 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:08,602 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:08,634 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-09 16:05:08,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,636 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,638 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-09 16:05:08,639 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:08,639 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:08,666 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:08,684 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:08,684 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:08,684 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:08,684 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:08,684 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:08,685 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:08,685 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,685 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:08,685 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:08,685 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-11-09 16:05:08,685 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:08,685 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:08,686 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,693 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,696 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,699 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:08,765 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:08,765 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:08,765 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,765 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,767 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,769 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-11-09 16:05:08,770 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:08,783 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:08,783 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:08,783 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:08,783 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:08,783 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:08,784 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:08,784 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:08,786 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:08,797 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:08,797 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,798 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,799 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-09 16:05:08,800 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:08,810 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:08,811 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:08,811 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:08,811 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:08,811 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:08,812 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:08,812 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:08,814 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:08,826 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:08,826 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,827 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-09 16:05:08,829 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:08,839 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:08,839 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:08,839 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:08,839 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:08,839 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:08,840 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:08,840 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:08,842 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:08,853 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:08,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,855 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,857 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-11-09 16:05:08,857 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:08,868 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:08,868 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:08,868 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:08,868 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:08,868 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:08,869 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:08,869 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:08,870 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:08,886 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:08,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,887 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,889 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,892 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-09 16:05:08,893 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:08,903 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:08,903 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:08,903 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:08,903 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:08,903 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:08,904 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:08,904 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:08,907 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:08,910 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:08,910 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:08,911 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:08,911 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:08,913 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:08,915 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-09 16:05:08,916 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:08,916 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:08,916 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:08,916 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-09 16:05:08,933 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:08,934 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:08,952 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:08,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:08,976 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:08,977 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:09,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:09,082 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 16:05:09,083 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:09,178 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:09,179 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-09 16:05:09,179 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:09,380 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:09,455 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 128 states and 178 transitions. Complement of second has 40 states. [2024-11-09 16:05:09,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:09,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:09,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-09 16:05:09,459 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-11-09 16:05:09,459 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:09,459 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-11-09 16:05:09,459 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:09,460 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-11-09 16:05:09,460 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:09,460 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-11-09 16:05:09,473 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:09,479 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-11-09 16:05:09,480 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-11-09 16:05:09,481 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-11-09 16:05:09,481 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-11-09 16:05:09,481 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:09,481 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-11-09 16:05:09,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-11-09 16:05:09,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-11-09 16:05:09,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (35), 18 states have call predecessors, (35), 19 states have call successors, (35) [2024-11-09 16:05:09,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-11-09 16:05:09,502 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-11-09 16:05:09,502 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:09,503 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 16:05:09,503 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-09 16:05:09,503 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 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) [2024-11-09 16:05:09,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:09,635 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-11-09 16:05:09,635 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-11-09 16:05:09,641 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:09,644 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-11-09 16:05:09,644 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-09 16:05:09,645 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-09 16:05:09,645 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-11-09 16:05:09,645 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:09,645 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-11-09 16:05:09,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-11-09 16:05:09,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-11-09 16:05:09,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (39), 20 states have call predecessors, (39), 22 states have call successors, (39) [2024-11-09 16:05:09,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-11-09 16:05:09,656 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-09 16:05:09,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:05:09,658 INFO L425 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-09 16:05:09,658 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 16:05:09,658 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-11-09 16:05:09,660 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:09,660 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:09,660 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:09,661 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:09,662 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-09 16:05:09,662 INFO L745 eck$LassoCheckResult]: Stem: 806#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 807#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 792#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 793#$Ultimate##0 ~n := #in~n; 809#L8 assume !(~n < 1); 810#L10 assume !(1 == ~n); 780#L13 call #t~ret4 := fibo(~n - 1);< 779#$Ultimate##0 ~n := #in~n; 781#L8 assume !(~n < 1); 816#L10 assume !(1 == ~n); 790#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 839#L8 assume !(~n < 1); 837#L10 assume 1 == ~n;#res := 1; 835#fiboFINAL assume true; 834#fiboEXIT >#35#return; 817#L13-1 call #t~ret5 := fibo(~n - 2);< 833#$Ultimate##0 ~n := #in~n; 879#L8 assume ~n < 1;#res := 0; 878#fiboFINAL assume true; 877#fiboEXIT >#37#return; 875#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 872#fiboFINAL assume true; 864#fiboEXIT >#35#return; 813#L13-1 [2024-11-09 16:05:09,662 INFO L747 eck$LassoCheckResult]: Loop: 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#35#return; 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#37#return; 862#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 871#fiboFINAL assume true; 865#fiboEXIT >#35#return; 813#L13-1 [2024-11-09 16:05:09,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:09,663 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-11-09 16:05:09,663 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:09,663 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1579192375] [2024-11-09 16:05:09,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:09,663 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:09,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:09,806 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-09 16:05:09,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:09,889 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:09,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:09,921 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:09,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:09,927 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 16:05:09,927 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:09,928 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1579192375] [2024-11-09 16:05:09,928 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1579192375] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:09,928 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [659606341] [2024-11-09 16:05:09,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:09,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:09,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:09,930 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:09,931 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2024-11-09 16:05:09,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:09,970 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:09,972 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:10,043 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 16:05:10,044 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:10,345 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 16:05:10,345 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [659606341] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:10,346 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:10,346 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-09 16:05:10,346 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [988682481] [2024-11-09 16:05:10,346 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:10,347 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:10,347 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:10,347 INFO L85 PathProgramCache]: Analyzing trace with hash -1138642743, now seen corresponding path program 1 times [2024-11-09 16:05:10,347 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:10,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1740544605] [2024-11-09 16:05:10,347 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:10,348 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:10,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:10,379 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:10,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:10,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:10,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:10,426 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:10,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:10,451 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-09 16:05:10,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:10,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1740544605] [2024-11-09 16:05:10,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1740544605] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:10,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [717787414] [2024-11-09 16:05:10,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:10,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:10,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:10,454 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:10,455 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-11-09 16:05:10,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:10,489 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:10,490 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:10,524 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-09 16:05:10,524 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:10,688 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-09 16:05:10,688 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [717787414] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:10,688 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:10,688 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-09 16:05:10,688 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754091484] [2024-11-09 16:05:10,688 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:10,689 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:10,689 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:10,690 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-09 16:05:10,690 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-09 16:05:10,690 INFO L87 Difference]: Start difference. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 2 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:10,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:10,818 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-09 16:05:10,818 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-09 16:05:10,820 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:10,821 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-09 16:05:10,821 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-09 16:05:10,821 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-09 16:05:10,821 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-09 16:05:10,821 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:10,822 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:10,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-09 16:05:10,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-09 16:05:10,830 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-09 16:05:10,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-09 16:05:10,830 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:10,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:05:10,832 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:10,835 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 16:05:10,835 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-09 16:05:10,836 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:10,836 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:10,836 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:10,838 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:10,838 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2024-11-09 16:05:10,838 INFO L745 eck$LassoCheckResult]: Stem: 1377#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 1378#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 1371#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1372#$Ultimate##0 ~n := #in~n; 1387#L8 assume !(~n < 1); 1386#L10 assume !(1 == ~n); 1359#L13 call #t~ret4 := fibo(~n - 1);< 1358#$Ultimate##0 ~n := #in~n; 1360#L8 assume !(~n < 1); 1380#L10 assume !(1 == ~n); 1364#L13 call #t~ret4 := fibo(~n - 1);< 1365#$Ultimate##0 ~n := #in~n; 1385#L8 assume !(~n < 1); 1403#L10 assume !(1 == ~n); 1375#L13 call #t~ret4 := fibo(~n - 1);< 1365#$Ultimate##0 ~n := #in~n; 1385#L8 assume !(~n < 1); 1403#L10 assume !(1 == ~n); 1375#L13 call #t~ret4 := fibo(~n - 1);< 1365#$Ultimate##0 ~n := #in~n; 1384#L8 assume !(~n < 1); 1381#L10 assume 1 == ~n;#res := 1; 1382#fiboFINAL assume true; 1374#fiboEXIT >#35#return; 1376#L13-1 call #t~ret5 := fibo(~n - 2);< 1402#$Ultimate##0 ~n := #in~n; 1408#L8 assume ~n < 1;#res := 0; 1407#fiboFINAL assume true; 1401#fiboEXIT >#37#return; 1399#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1397#fiboFINAL assume true; 1394#fiboEXIT >#35#return; 1368#L13-1 [2024-11-09 16:05:10,841 INFO L747 eck$LassoCheckResult]: Loop: 1368#L13-1 call #t~ret5 := fibo(~n - 2);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume !(1 == ~n); 1367#L13 call #t~ret4 := fibo(~n - 1);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume !(1 == ~n); 1367#L13 call #t~ret4 := fibo(~n - 1);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume !(1 == ~n); 1367#L13 call #t~ret4 := fibo(~n - 1);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume 1 == ~n;#res := 1; 1404#fiboFINAL assume true; 1405#fiboEXIT >#35#return; 1356#L13-1 call #t~ret5 := fibo(~n - 2);< 1355#$Ultimate##0 ~n := #in~n; 1357#L8 assume ~n < 1;#res := 0; 1379#fiboFINAL assume true; 1400#fiboEXIT >#37#return; 1366#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1370#fiboFINAL assume true; 1373#fiboEXIT >#35#return; 1368#L13-1 call #t~ret5 := fibo(~n - 2);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume ~n < 1;#res := 0; 1379#fiboFINAL assume true; 1400#fiboEXIT >#37#return; 1391#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1398#fiboFINAL assume true; 1395#fiboEXIT >#35#return; 1368#L13-1 [2024-11-09 16:05:10,841 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:10,842 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 2 times [2024-11-09 16:05:10,842 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:10,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1673257751] [2024-11-09 16:05:10,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:10,842 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:10,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:10,966 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-09 16:05:10,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,023 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:11,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,062 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:11,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,069 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 16:05:11,070 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:11,070 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1673257751] [2024-11-09 16:05:11,071 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1673257751] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:11,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [737387229] [2024-11-09 16:05:11,071 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 16:05:11,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:11,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:11,074 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:11,076 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Waiting until timeout for monitored process [2024-11-09 16:05:11,117 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 16:05:11,118 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:11,119 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:11,120 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:11,176 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 16:05:11,176 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:11,460 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 16:05:11,461 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [737387229] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:11,461 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:11,461 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-09 16:05:11,462 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566677467] [2024-11-09 16:05:11,462 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:11,462 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:11,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:11,464 INFO L85 PathProgramCache]: Analyzing trace with hash 1083596768, now seen corresponding path program 1 times [2024-11-09 16:05:11,464 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:11,464 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1670092236] [2024-11-09 16:05:11,465 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:11,465 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:11,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,506 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:11,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,542 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:11,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,582 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:11,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,587 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:11,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,592 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 16:05:11,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,606 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 29 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-09 16:05:11,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:11,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1670092236] [2024-11-09 16:05:11,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1670092236] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:11,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2121767328] [2024-11-09 16:05:11,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:11,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:11,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:11,610 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:11,611 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (27)] Waiting until timeout for monitored process [2024-11-09 16:05:11,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:11,650 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:11,653 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:11,707 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-09 16:05:11,707 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:12,006 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 13 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-09 16:05:12,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2121767328] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:12,006 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:12,007 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2024-11-09 16:05:12,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1198681604] [2024-11-09 16:05:12,007 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:12,008 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:12,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:12,008 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-09 16:05:12,009 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-11-09 16:05:12,009 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 16:05:12,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:12,346 INFO L93 Difference]: Finished difference Result 110 states and 129 transitions. [2024-11-09 16:05:12,346 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 110 states and 129 transitions. [2024-11-09 16:05:12,349 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:12,354 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 110 states to 99 states and 118 transitions. [2024-11-09 16:05:12,354 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-09 16:05:12,354 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 72 [2024-11-09 16:05:12,355 INFO L73 IsDeterministic]: Start isDeterministic. Operand 99 states and 118 transitions. [2024-11-09 16:05:12,355 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:12,355 INFO L218 hiAutomatonCegarLoop]: Abstraction has 99 states and 118 transitions. [2024-11-09 16:05:12,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states and 118 transitions. [2024-11-09 16:05:12,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2024-11-09 16:05:12,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 64 states have (on average 1.046875) internal successors, (67), 66 states have internal predecessors, (67), 23 states have call successors, (23), 14 states have call predecessors, (23), 12 states have return successors, (28), 18 states have call predecessors, (28), 20 states have call successors, (28) [2024-11-09 16:05:12,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 118 transitions. [2024-11-09 16:05:12,365 INFO L240 hiAutomatonCegarLoop]: Abstraction has 99 states and 118 transitions. [2024-11-09 16:05:12,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-09 16:05:12,368 INFO L425 stractBuchiCegarLoop]: Abstraction has 99 states and 118 transitions. [2024-11-09 16:05:12,369 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 16:05:12,369 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 99 states and 118 transitions. [2024-11-09 16:05:12,370 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:12,370 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:12,371 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:12,372 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 9, 8, 8, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:12,374 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-09 16:05:12,374 INFO L745 eck$LassoCheckResult]: Stem: 2063#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 2064#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 2059#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 2060#$Ultimate##0 ~n := #in~n; 2066#L8 assume !(~n < 1); 2067#L10 assume !(1 == ~n); 2050#L13 call #t~ret4 := fibo(~n - 1);< 2049#$Ultimate##0 ~n := #in~n; 2051#L8 assume !(~n < 1); 2091#L10 assume !(1 == ~n); 2055#L13 call #t~ret4 := fibo(~n - 1);< 2056#$Ultimate##0 ~n := #in~n; 2090#L8 assume !(~n < 1); 2089#L10 assume !(1 == ~n); 2085#L13 call #t~ret4 := fibo(~n - 1);< 2088#$Ultimate##0 ~n := #in~n; 2087#L8 assume !(~n < 1); 2086#L10 assume !(1 == ~n); 2081#L13 call #t~ret4 := fibo(~n - 1);< 2084#$Ultimate##0 ~n := #in~n; 2083#L8 assume !(~n < 1); 2082#L10 assume !(1 == ~n); 2077#L13 call #t~ret4 := fibo(~n - 1);< 2080#$Ultimate##0 ~n := #in~n; 2079#L8 assume !(~n < 1); 2078#L10 assume !(1 == ~n); 2069#L13 call #t~ret4 := fibo(~n - 1);< 2075#$Ultimate##0 ~n := #in~n; 2076#L8 assume !(~n < 1); 2144#L10 assume !(1 == ~n); 2070#L13 call #t~ret4 := fibo(~n - 1);< 2075#$Ultimate##0 ~n := #in~n; 2076#L8 assume !(~n < 1); 2144#L10 assume !(1 == ~n); 2070#L13 call #t~ret4 := fibo(~n - 1);< 2075#$Ultimate##0 ~n := #in~n; 2074#L8 assume !(~n < 1); 2068#L10 assume 1 == ~n;#res := 1; 2071#fiboFINAL assume true; 2102#fiboEXIT >#35#return; 2047#L13-1 call #t~ret5 := fibo(~n - 2);< 2046#$Ultimate##0 ~n := #in~n; 2048#L8 assume ~n < 1;#res := 0; 2065#fiboFINAL assume true; 2119#fiboEXIT >#37#return; 2117#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2111#fiboFINAL assume true; 2107#fiboEXIT >#35#return; 2097#L13-1 [2024-11-09 16:05:12,374 INFO L747 eck$LassoCheckResult]: Loop: 2097#L13-1 call #t~ret5 := fibo(~n - 2);< 2103#$Ultimate##0 ~n := #in~n; 2115#L8 assume !(~n < 1); 2110#L10 assume !(1 == ~n); 2096#L13 call #t~ret4 := fibo(~n - 1);< 2103#$Ultimate##0 ~n := #in~n; 2115#L8 assume !(~n < 1); 2110#L10 assume !(1 == ~n); 2096#L13 call #t~ret4 := fibo(~n - 1);< 2103#$Ultimate##0 ~n := #in~n; 2115#L8 assume !(~n < 1); 2110#L10 assume 1 == ~n;#res := 1; 2104#fiboFINAL assume true; 2100#fiboEXIT >#35#return; 2093#L13-1 call #t~ret5 := fibo(~n - 2);< 2099#$Ultimate##0 ~n := #in~n; 2124#L8 assume ~n < 1;#res := 0; 2116#fiboFINAL assume true; 2120#fiboEXIT >#37#return; 2121#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2143#fiboFINAL assume true; 2105#fiboEXIT >#35#return; 2097#L13-1 [2024-11-09 16:05:12,375 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:12,375 INFO L85 PathProgramCache]: Analyzing trace with hash -683438758, now seen corresponding path program 3 times [2024-11-09 16:05:12,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:12,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [263729092] [2024-11-09 16:05:12,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:12,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:12,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:12,573 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-09 16:05:12,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:12,643 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:12,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:12,665 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:12,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:12,671 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 2 proven. 153 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 16:05:12,671 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:12,671 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [263729092] [2024-11-09 16:05:12,672 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [263729092] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:12,672 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1880290602] [2024-11-09 16:05:12,672 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 16:05:12,672 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:12,672 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:12,674 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:12,681 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (28)] Waiting until timeout for monitored process [2024-11-09 16:05:12,727 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-09 16:05:12,728 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:12,729 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:12,730 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:12,830 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 2 proven. 153 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 16:05:12,830 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:13,138 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 2 proven. 155 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 16:05:13,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1880290602] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:13,139 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:13,139 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 20] total 23 [2024-11-09 16:05:13,139 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1218882289] [2024-11-09 16:05:13,139 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:13,139 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:13,140 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:13,140 INFO L85 PathProgramCache]: Analyzing trace with hash -2000232554, now seen corresponding path program 2 times [2024-11-09 16:05:13,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:13,140 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154606390] [2024-11-09 16:05:13,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:13,140 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:13,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:13,145 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:13,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:13,149 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:13,390 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:13,390 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:13,390 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:13,390 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:13,390 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:13,390 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:13,390 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:13,390 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:13,391 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-11-09 16:05:13,391 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:13,391 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:13,391 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,401 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,403 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,405 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,443 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:13,443 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:13,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:13,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:13,445 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:13,446 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-11-09 16:05:13,448 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:13,448 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:13,479 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:13,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:13,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:13,481 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:13,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-09 16:05:13,483 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:13,483 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:13,968 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:13,973 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:13,973 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:13,974 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:13,974 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:13,974 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:13,974 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:13,974 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:13,974 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:13,974 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:13,974 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-11-09 16:05:13,974 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:13,974 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:13,975 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,982 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,985 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:13,987 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:14,020 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:14,020 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:14,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:14,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:14,021 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:14,022 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-09 16:05:14,024 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:14,034 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:14,034 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:14,034 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:14,034 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:14,034 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:14,035 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:14,035 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:14,038 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:14,040 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 16:05:14,040 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:14,040 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:14,040 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:14,041 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:14,042 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-09 16:05:14,043 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:14,043 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:14,043 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:14,043 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-09 16:05:14,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:14,055 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:14,062 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:14,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:14,119 INFO L255 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-09 16:05:14,121 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:14,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:14,362 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:14,364 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:14,489 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:14,490 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:14,491 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:14,586 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 106 states and 125 transitions. Complement of second has 11 states. [2024-11-09 16:05:14,587 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:14,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:14,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-09 16:05:14,588 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 48 letters. Loop has 22 letters. [2024-11-09 16:05:14,589 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:14,589 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:14,600 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:14,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:14,655 INFO L255 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-09 16:05:14,657 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:14,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:14,891 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:14,892 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:15,013 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:15,014 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:15,014 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:15,108 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 106 states and 125 transitions. Complement of second has 11 states. [2024-11-09 16:05:15,109 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:15,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:15,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-09 16:05:15,110 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 48 letters. Loop has 22 letters. [2024-11-09 16:05:15,110 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:15,111 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:15,123 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:15,171 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:15,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:15,197 INFO L255 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-09 16:05:15,198 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:15,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:15,403 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:15,404 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:15,536 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:15,537 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:15,537 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:15,795 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 537 states and 697 transitions. Complement of second has 132 states. [2024-11-09 16:05:15,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:15,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:15,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-09 16:05:15,797 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 48 letters. Loop has 22 letters. [2024-11-09 16:05:15,798 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:15,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 70 letters. Loop has 22 letters. [2024-11-09 16:05:15,799 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:15,799 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 48 letters. Loop has 44 letters. [2024-11-09 16:05:15,803 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:15,803 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 537 states and 697 transitions. [2024-11-09 16:05:15,812 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-09 16:05:15,824 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 537 states to 382 states and 513 transitions. [2024-11-09 16:05:15,824 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 161 [2024-11-09 16:05:15,825 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-11-09 16:05:15,826 INFO L73 IsDeterministic]: Start isDeterministic. Operand 382 states and 513 transitions. [2024-11-09 16:05:15,826 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:15,826 INFO L218 hiAutomatonCegarLoop]: Abstraction has 382 states and 513 transitions. [2024-11-09 16:05:15,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 382 states and 513 transitions. [2024-11-09 16:05:15,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 382 to 337. [2024-11-09 16:05:15,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 337 states, 206 states have (on average 1.0922330097087378) internal successors, (225), 219 states have internal predecessors, (225), 80 states have call successors, (84), 42 states have call predecessors, (84), 51 states have return successors, (126), 75 states have call predecessors, (126), 70 states have call successors, (126) [2024-11-09 16:05:15,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 337 states to 337 states and 435 transitions. [2024-11-09 16:05:15,868 INFO L240 hiAutomatonCegarLoop]: Abstraction has 337 states and 435 transitions. [2024-11-09 16:05:15,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:15,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-09 16:05:15,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=437, Unknown=0, NotChecked=0, Total=552 [2024-11-09 16:05:15,869 INFO L87 Difference]: Start difference. First operand 337 states and 435 transitions. Second operand has 24 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 15 states have internal predecessors, (43), 13 states have call successors, (13), 8 states have call predecessors, (13), 3 states have return successors, (6), 3 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 16:05:16,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:16,202 INFO L93 Difference]: Finished difference Result 462 states and 593 transitions. [2024-11-09 16:05:16,202 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 462 states and 593 transitions. [2024-11-09 16:05:16,209 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-09 16:05:16,219 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 462 states to 455 states and 580 transitions. [2024-11-09 16:05:16,219 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 210 [2024-11-09 16:05:16,220 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 210 [2024-11-09 16:05:16,220 INFO L73 IsDeterministic]: Start isDeterministic. Operand 455 states and 580 transitions. [2024-11-09 16:05:16,220 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:16,220 INFO L218 hiAutomatonCegarLoop]: Abstraction has 455 states and 580 transitions. [2024-11-09 16:05:16,221 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 455 states and 580 transitions. [2024-11-09 16:05:16,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 455 to 435. [2024-11-09 16:05:16,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 435 states, 267 states have (on average 1.0823970037453183) internal successors, (289), 281 states have internal predecessors, (289), 106 states have call successors, (110), 55 states have call predecessors, (110), 62 states have return successors, (159), 98 states have call predecessors, (159), 94 states have call successors, (159) [2024-11-09 16:05:16,247 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 435 states to 435 states and 558 transitions. [2024-11-09 16:05:16,247 INFO L240 hiAutomatonCegarLoop]: Abstraction has 435 states and 558 transitions. [2024-11-09 16:05:16,247 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-09 16:05:16,248 INFO L425 stractBuchiCegarLoop]: Abstraction has 435 states and 558 transitions. [2024-11-09 16:05:16,248 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-09 16:05:16,248 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 435 states and 558 transitions. [2024-11-09 16:05:16,252 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-09 16:05:16,252 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:16,252 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:16,255 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [13, 12, 11, 11, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:16,258 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:16,258 INFO L745 eck$LassoCheckResult]: Stem: 4917#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 4918#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 4908#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 4909#$Ultimate##0 ~n := #in~n; 4958#L8 assume !(~n < 1); 4957#L10 assume !(1 == ~n); 4953#L13 call #t~ret4 := fibo(~n - 1);< 4956#$Ultimate##0 ~n := #in~n; 4955#L8 assume !(~n < 1); 4954#L10 assume !(1 == ~n); 4949#L13 call #t~ret4 := fibo(~n - 1);< 4952#$Ultimate##0 ~n := #in~n; 4951#L8 assume !(~n < 1); 4950#L10 assume !(1 == ~n); 4945#L13 call #t~ret4 := fibo(~n - 1);< 4948#$Ultimate##0 ~n := #in~n; 4947#L8 assume !(~n < 1); 4946#L10 assume !(1 == ~n); 4941#L13 call #t~ret4 := fibo(~n - 1);< 4944#$Ultimate##0 ~n := #in~n; 4943#L8 assume !(~n < 1); 4942#L10 assume !(1 == ~n); 4937#L13 call #t~ret4 := fibo(~n - 1);< 4940#$Ultimate##0 ~n := #in~n; 4939#L8 assume !(~n < 1); 4938#L10 assume !(1 == ~n); 4933#L13 call #t~ret4 := fibo(~n - 1);< 4936#$Ultimate##0 ~n := #in~n; 4935#L8 assume !(~n < 1); 4934#L10 assume !(1 == ~n); 4914#L13 call #t~ret4 := fibo(~n - 1);< 4930#$Ultimate##0 ~n := #in~n; 4932#L8 assume !(~n < 1); 5268#L10 assume !(1 == ~n); 4913#L13 call #t~ret4 := fibo(~n - 1);< 4930#$Ultimate##0 ~n := #in~n; 4932#L8 assume !(~n < 1); 5268#L10 assume !(1 == ~n); 4913#L13 call #t~ret4 := fibo(~n - 1);< 4930#$Ultimate##0 ~n := #in~n; 4931#L8 assume !(~n < 1); 5315#L10 assume 1 == ~n;#res := 1; 5313#fiboFINAL assume true; 4912#fiboEXIT >#35#return; 4915#L13-1 call #t~ret5 := fibo(~n - 2);< 5284#$Ultimate##0 ~n := #in~n; 5288#L8 assume ~n < 1;#res := 0; 5287#fiboFINAL assume true; 5283#fiboEXIT >#37#return; 5282#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 5281#fiboFINAL assume true; 5267#fiboEXIT >#35#return; 4923#L13-1 call #t~ret5 := fibo(~n - 2);< 5244#$Ultimate##0 ~n := #in~n; 5273#L8 assume !(~n < 1); 5272#L10 assume !(1 == ~n); 4903#L13 call #t~ret4 := fibo(~n - 1);< 5046#$Ultimate##0 ~n := #in~n; 5045#L8 assume !(~n < 1); 5003#L10 assume !(1 == ~n); 4984#L13 call #t~ret4 := fibo(~n - 1);< 4992#$Ultimate##0 [2024-11-09 16:05:16,258 INFO L747 eck$LassoCheckResult]: Loop: 4992#$Ultimate##0 ~n := #in~n; 4999#L8 assume !(~n < 1); 4998#L10 assume !(1 == ~n); 4983#L13 call #t~ret4 := fibo(~n - 1);< 4992#$Ultimate##0 [2024-11-09 16:05:16,259 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:16,259 INFO L85 PathProgramCache]: Analyzing trace with hash -366223317, now seen corresponding path program 4 times [2024-11-09 16:05:16,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:16,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1943194037] [2024-11-09 16:05:16,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:16,259 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:16,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:16,591 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 16:05:16,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:16,597 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:16,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:16,600 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:16,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:16,602 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 198 proven. 72 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 16:05:16,603 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:16,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1943194037] [2024-11-09 16:05:16,603 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1943194037] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:16,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [103159767] [2024-11-09 16:05:16,603 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 16:05:16,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:16,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:16,605 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:16,609 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Waiting until timeout for monitored process [2024-11-09 16:05:16,658 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 16:05:16,659 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:16,660 INFO L255 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-09 16:05:16,661 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:16,763 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 199 proven. 72 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-09 16:05:16,764 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:16,996 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 199 proven. 72 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-09 16:05:16,996 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [103159767] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:16,996 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:16,996 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23, 23] total 24 [2024-11-09 16:05:16,996 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [440108511] [2024-11-09 16:05:16,996 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:16,997 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:16,997 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:16,997 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 2 times [2024-11-09 16:05:16,997 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:16,997 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [399018451] [2024-11-09 16:05:16,997 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:16,998 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:17,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:17,000 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:17,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:17,002 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:17,042 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:17,042 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:17,042 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:17,042 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:17,042 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:17,042 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,042 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:17,043 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:17,043 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-11-09 16:05:17,043 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:17,043 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:17,044 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,047 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,049 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,051 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,053 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,087 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:17,087 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:17,087 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,089 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,090 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-09 16:05:17,091 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:17,091 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,101 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:17,102 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:17,112 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,114 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,115 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-09 16:05:17,116 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:17,116 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,127 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:17,127 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:17,143 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-11-09 16:05:17,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,146 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,148 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-09 16:05:17,148 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:17,148 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,160 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:17,160 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:17,170 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,171 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,171 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,172 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-09 16:05:17,173 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:17,173 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,184 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:17,184 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:17,194 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,194 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,195 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,196 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,196 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-09 16:05:17,197 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:17,197 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,220 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,220 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,220 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,221 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,222 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-09 16:05:17,223 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:17,223 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,275 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:17,279 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Ended with exit code 0 [2024-11-09 16:05:17,279 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:17,280 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:17,280 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:17,280 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:17,280 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:17,280 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,280 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:17,280 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:17,280 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-11-09 16:05:17,280 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:17,280 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:17,281 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,287 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,289 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,295 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,297 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,325 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:17,325 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:17,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,325 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,327 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,329 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-11-09 16:05:17,330 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:17,339 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:17,339 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:17,339 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:17,339 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:17,340 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:17,340 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:17,340 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:17,341 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:17,352 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,353 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,354 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-09 16:05:17,355 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:17,364 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:17,364 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:17,364 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:17,365 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:17,365 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:17,365 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:17,365 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:17,366 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:17,376 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-11-09 16:05:17,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,377 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,378 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,379 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-09 16:05:17,380 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:17,392 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:17,393 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:17,393 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:17,393 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:17,393 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:17,394 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:17,394 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:17,396 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:17,400 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:17,400 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:17,400 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,400 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,402 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,403 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2024-11-09 16:05:17,405 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:17,405 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:17,405 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:17,405 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-09 16:05:17,420 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,421 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:17,439 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:17,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:17,510 INFO L255 TraceCheckSpWp]: Trace formula consists of 538 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-09 16:05:17,512 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:17,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:17,713 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:17,714 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:17,756 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:17,757 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 16:05:17,757 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:17,767 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2024-11-09 16:05:17,819 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 460 states and 583 transitions. Complement of second has 15 states. [2024-11-09 16:05:17,820 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:17,820 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:17,821 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-09 16:05:17,821 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 61 letters. Loop has 4 letters. [2024-11-09 16:05:17,821 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:17,821 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:17,834 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:17,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:17,917 INFO L255 TraceCheckSpWp]: Trace formula consists of 538 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-09 16:05:17,919 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,109 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,110 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,134 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:18,134 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 16:05:18,135 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:18,192 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 460 states and 583 transitions. Complement of second has 15 states. [2024-11-09 16:05:18,192 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:18,193 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:18,193 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-09 16:05:18,193 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 61 letters. Loop has 4 letters. [2024-11-09 16:05:18,193 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,193 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:18,204 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,281 INFO L255 TraceCheckSpWp]: Trace formula consists of 538 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,285 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,483 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,484 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,510 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:18,510 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 16:05:18,510 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:18,586 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 589 states and 714 transitions. Complement of second has 19 states. [2024-11-09 16:05:18,587 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:18,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:18,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-09 16:05:18,588 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 4 letters. [2024-11-09 16:05:18,588 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,588 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 65 letters. Loop has 4 letters. [2024-11-09 16:05:18,589 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,589 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 8 letters. [2024-11-09 16:05:18,590 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,590 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 589 states and 714 transitions. [2024-11-09 16:05:18,598 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-09 16:05:18,603 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 589 states to 450 states and 574 transitions. [2024-11-09 16:05:18,604 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 160 [2024-11-09 16:05:18,604 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 163 [2024-11-09 16:05:18,604 INFO L73 IsDeterministic]: Start isDeterministic. Operand 450 states and 574 transitions. [2024-11-09 16:05:18,605 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:18,605 INFO L218 hiAutomatonCegarLoop]: Abstraction has 450 states and 574 transitions. [2024-11-09 16:05:18,605 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 450 states and 574 transitions. [2024-11-09 16:05:18,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 450 to 445. [2024-11-09 16:05:18,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 445 states, 276 states have (on average 1.0797101449275361) internal successors, (298), 290 states have internal predecessors, (298), 107 states have call successors, (111), 56 states have call predecessors, (111), 62 states have return successors, (159), 98 states have call predecessors, (159), 94 states have call successors, (159) [2024-11-09 16:05:18,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 445 states to 445 states and 568 transitions. [2024-11-09 16:05:18,625 INFO L240 hiAutomatonCegarLoop]: Abstraction has 445 states and 568 transitions. [2024-11-09 16:05:18,625 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:18,626 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-09 16:05:18,626 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=408, Unknown=0, NotChecked=0, Total=552 [2024-11-09 16:05:18,626 INFO L87 Difference]: Start difference. First operand 445 states and 568 transitions. Second operand has 24 states, 23 states have (on average 1.8695652173913044) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (14), 12 states have call predecessors, (14), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:18,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:18,963 INFO L93 Difference]: Finished difference Result 469 states and 569 transitions. [2024-11-09 16:05:18,963 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 469 states and 569 transitions. [2024-11-09 16:05:18,968 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:18,968 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 469 states to 0 states and 0 transitions. [2024-11-09 16:05:18,968 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:05:18,968 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:05:18,969 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:05:18,969 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:05:18,969 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:18,969 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:18,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-09 16:05:18,969 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:18,970 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-09 16:05:18,970 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 16:05:18,970 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:18,970 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 16:05:18,977 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 04:05:18 BoogieIcfgContainer [2024-11-09 16:05:18,977 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 16:05:18,978 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 16:05:18,978 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 16:05:18,978 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 16:05:18,978 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:06" (3/4) ... [2024-11-09 16:05:18,981 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 16:05:18,982 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 16:05:18,982 INFO L158 Benchmark]: Toolchain (without parser) took 13581.80ms. Allocated memory was 151.0MB in the beginning and 220.2MB in the end (delta: 69.2MB). Free memory was 114.1MB in the beginning and 180.2MB in the end (delta: -66.1MB). Peak memory consumption was 5.2MB. Max. memory is 16.1GB. [2024-11-09 16:05:18,983 INFO L158 Benchmark]: CDTParser took 0.29ms. Allocated memory is still 151.0MB. Free memory is still 119.0MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:18,983 INFO L158 Benchmark]: CACSL2BoogieTranslator took 241.52ms. Allocated memory is still 151.0MB. Free memory was 113.5MB in the beginning and 101.7MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 16:05:18,983 INFO L158 Benchmark]: Boogie Procedure Inliner took 33.06ms. Allocated memory is still 151.0MB. Free memory was 101.7MB in the beginning and 100.3MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:18,984 INFO L158 Benchmark]: Boogie Preprocessor took 29.37ms. Allocated memory is still 151.0MB. Free memory was 100.3MB in the beginning and 98.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:18,984 INFO L158 Benchmark]: RCFGBuilder took 297.73ms. Allocated memory is still 151.0MB. Free memory was 98.8MB in the beginning and 89.3MB in the end (delta: 9.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-09 16:05:18,985 INFO L158 Benchmark]: BuchiAutomizer took 12971.06ms. Allocated memory was 151.0MB in the beginning and 220.2MB in the end (delta: 69.2MB). Free memory was 89.3MB in the beginning and 180.2MB in the end (delta: -90.9MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:18,985 INFO L158 Benchmark]: Witness Printer took 4.36ms. Allocated memory is still 220.2MB. Free memory was 180.2MB in the beginning and 180.2MB in the end (delta: 2.6kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:18,986 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.29ms. Allocated memory is still 151.0MB. Free memory is still 119.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 241.52ms. Allocated memory is still 151.0MB. Free memory was 113.5MB in the beginning and 101.7MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 33.06ms. Allocated memory is still 151.0MB. Free memory was 101.7MB in the beginning and 100.3MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 29.37ms. Allocated memory is still 151.0MB. Free memory was 100.3MB in the beginning and 98.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 297.73ms. Allocated memory is still 151.0MB. Free memory was 98.8MB in the beginning and 89.3MB in the end (delta: 9.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 12971.06ms. Allocated memory was 151.0MB in the beginning and 220.2MB in the end (delta: 69.2MB). Free memory was 89.3MB in the beginning and 180.2MB in the end (delta: -90.9MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 4.36ms. Allocated memory is still 220.2MB. Free memory was 180.2MB in the beginning and 180.2MB in the end (delta: 2.6kB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (6 trivial, 2 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function n and consists of 11 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 6 modules have a trivial ranking function, the largest among these consists of 24 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 12.8s and 8 iterations. TraceHistogramMax:13. Analysis of lassos took 7.3s. Construction of modules took 1.1s. Büchi inclusion checks took 4.0s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 92 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 517 SdHoareTripleChecker+Valid, 1.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 485 mSDsluCounter, 720 SdHoareTripleChecker+Invalid, 1.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 509 mSDsCounter, 308 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1524 IncrementalHoareTripleChecker+Invalid, 1832 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 308 mSolverCounterUnsat, 211 mSDtfsCounter, 1524 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI3 SILT3 lasso0 LassoPreprocessingBenchmarks: Lassos: inital16 mio100 ax100 hnf100 lsp86 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq178 hnf93 smp76 dnf100 smp100 tf112 neg100 sie107 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 19ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.9s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-09 16:05:19,011 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:19,212 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (28)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:19,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (27)] Ended with exit code 0 [2024-11-09 16:05:19,612 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:19,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:20,013 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Ended with exit code 0 [2024-11-09 16:05:20,213 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-09 16:05:20,414 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE