./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.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 b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-13 17:41:24,322 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-13 17:41:24,387 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-13 17:41:24,390 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-13 17:41:24,393 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-13 17:41:24,425 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-13 17:41:24,426 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-13 17:41:24,426 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-13 17:41:24,427 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-13 17:41:24,432 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-13 17:41:24,432 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-13 17:41:24,432 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-13 17:41:24,433 INFO L153 SettingsManager]: * Use SBE=true [2024-10-13 17:41:24,433 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-13 17:41:24,433 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-13 17:41:24,433 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-13 17:41:24,433 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-13 17:41:24,434 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-13 17:41:24,434 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-13 17:41:24,434 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-13 17:41:24,434 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-13 17:41:24,436 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-13 17:41:24,436 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-13 17:41:24,437 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-13 17:41:24,437 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-13 17:41:24,437 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-13 17:41:24,437 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-13 17:41:24,438 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-13 17:41:24,438 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-13 17:41:24,438 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-13 17:41:24,438 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-13 17:41:24,439 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-13 17:41:24,439 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-13 17:41:24,439 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-13 17:41:24,440 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-13 17:41:24,440 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-13 17:41:24,441 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-13 17:41:24,441 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-13 17:41:24,441 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-13 17:41:24,441 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 -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2024-10-13 17:41:24,749 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-13 17:41:24,776 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-13 17:41:24,778 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-13 17:41:24,780 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-13 17:41:24,780 INFO L274 PluginConnector]: CDTParser initialized [2024-10-13 17:41:24,781 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-13 17:41:26,191 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-13 17:41:26,357 INFO L384 CDTParser]: Found 1 translation units. [2024-10-13 17:41:26,357 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-13 17:41:26,364 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f604dabd7/c6a54c29ce304843a0f2db8fcf77b70e/FLAGc0cc06506 [2024-10-13 17:41:26,375 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f604dabd7/c6a54c29ce304843a0f2db8fcf77b70e [2024-10-13 17:41:26,378 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-13 17:41:26,379 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-13 17:41:26,380 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:26,380 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-13 17:41:26,386 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-13 17:41:26,387 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,387 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2744e52a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26, skipping insertion in model container [2024-10-13 17:41:26,388 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,406 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-13 17:41:26,588 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:26,598 INFO L200 MainTranslator]: Completed pre-run [2024-10-13 17:41:26,611 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:26,626 INFO L204 MainTranslator]: Completed translation [2024-10-13 17:41:26,627 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26 WrapperNode [2024-10-13 17:41:26,627 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:26,628 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:26,628 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-13 17:41:26,629 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-13 17:41:26,637 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,645 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,661 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-10-13 17:41:26,661 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:26,662 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-13 17:41:26,662 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-13 17:41:26,662 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-13 17:41:26,672 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,672 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,674 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,684 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-10-13 17:41:26,685 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,685 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,688 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,690 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,694 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,695 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,697 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-13 17:41:26,698 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-13 17:41:26,699 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-13 17:41:26,699 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-13 17:41:26,700 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,704 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:26,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:26,727 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-10-13 17:41:26,729 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-10-13 17:41:26,766 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-10-13 17:41:26,767 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-10-13 17:41:26,767 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-13 17:41:26,767 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-13 17:41:26,767 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-13 17:41:26,767 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-13 17:41:26,830 INFO L238 CfgBuilder]: Building ICFG [2024-10-13 17:41:26,832 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-13 17:41:26,951 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-13 17:41:26,952 INFO L287 CfgBuilder]: Performing block encoding [2024-10-13 17:41:26,964 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-13 17:41:26,965 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-13 17:41:26,965 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:26 BoogieIcfgContainer [2024-10-13 17:41:26,965 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-13 17:41:26,966 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-13 17:41:26,966 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-13 17:41:26,970 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-13 17:41:26,971 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:26,971 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 13.10 05:41:26" (1/3) ... [2024-10-13 17:41:26,972 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@fe82c8e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:26, skipping insertion in model container [2024-10-13 17:41:26,973 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:26,973 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26" (2/3) ... [2024-10-13 17:41:26,973 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@fe82c8e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:26, skipping insertion in model container [2024-10-13 17:41:26,973 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:26,973 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:26" (3/3) ... [2024-10-13 17:41:26,975 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2024-10-13 17:41:27,032 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-13 17:41:27,032 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-13 17:41:27,032 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-13 17:41:27,033 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-13 17:41:27,034 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-13 17:41:27,034 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-13 17:41:27,034 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-13 17:41:27,034 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-13 17:41:27,041 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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-10-13 17:41:27,056 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:27,056 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:27,057 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:27,061 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:27,061 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:27,061 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-13 17:41:27,061 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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-10-13 17:41:27,063 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:27,063 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:27,063 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:27,064 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:27,064 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:27,069 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(14, 2);call #Ultimate.allocInit(12, 3); 12#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 := 9; 8#L29true call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 14#$Ultimate##0true [2024-10-13 17:41:27,069 INFO L747 eck$LassoCheckResult]: Loop: 14#$Ultimate##0true ~n := #in~n; 4#L17true assume !(~n < 1); 18#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 14#$Ultimate##0true [2024-10-13 17:41:27,074 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,074 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-10-13 17:41:27,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:27,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1894538879] [2024-10-13 17:41:27,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:27,081 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:27,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,155 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:27,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,178 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:27,182 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,183 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-10-13 17:41:27,183 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:27,183 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1005646934] [2024-10-13 17:41:27,183 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:27,183 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:27,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,195 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:27,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,201 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:27,203 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,203 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-10-13 17:41:27,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:27,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [840056263] [2024-10-13 17:41:27,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:27,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:27,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,217 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:27,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,226 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:27,330 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:27,331 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:27,331 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:27,331 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:27,331 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:27,331 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,331 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:27,331 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:27,332 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-13 17:41:27,332 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:27,332 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:27,346 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,359 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,362 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,366 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,380 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,449 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:27,450 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:27,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,451 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,453 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-10-13 17:41:27,455 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-10-13 17:41:27,456 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,456 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,472 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:27,472 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:27,483 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-10-13 17:41:27,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,484 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,487 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-10-13 17:41:27,487 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-10-13 17:41:27,489 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,489 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,503 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:27,503 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:27,519 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:27,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,521 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-10-13 17:41:27,524 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-10-13 17:41:27,525 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,525 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,540 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:27,541 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:27,555 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-10-13 17:41:27,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,558 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-10-13 17:41:27,561 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-10-13 17:41:27,563 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,563 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,587 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:27,588 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,588 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,589 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-10-13 17:41:27,590 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-10-13 17:41:27,591 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:27,591 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,657 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:27,661 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-10-13 17:41:27,661 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:27,661 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:27,662 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:27,662 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:27,662 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:27,662 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,662 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:27,662 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:27,662 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-13 17:41:27,662 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:27,662 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:27,664 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,667 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,670 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,677 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,687 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,739 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:27,743 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:27,744 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,744 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,745 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-10-13 17:41:27,746 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-10-13 17:41:27,747 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-10-13 17:41:27,758 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:27,758 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:27,759 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:27,759 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:27,759 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:27,760 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:27,760 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:27,763 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:27,773 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-10-13 17:41:27,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,774 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,775 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-10-13 17:41:27,776 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-10-13 17:41:27,777 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-10-13 17:41:27,788 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:27,788 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:27,789 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:27,789 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:27,789 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:27,789 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:27,789 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:27,793 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:27,806 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:27,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,808 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-10-13 17:41:27,809 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-10-13 17:41:27,810 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-10-13 17:41:27,820 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:27,820 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:27,820 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:27,820 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:27,820 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:27,821 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:27,821 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:27,822 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:27,833 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-10-13 17:41:27,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,835 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-10-13 17:41:27,836 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-10-13 17:41:27,836 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-10-13 17:41:27,846 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:27,846 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:27,847 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:27,847 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:27,847 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:27,848 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:27,848 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:27,850 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:27,853 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:27,853 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:27,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,876 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-10-13 17:41:27,878 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-10-13 17:41:27,878 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:27,878 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:27,878 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:27,879 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-13 17:41:27,894 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-10-13 17:41:27,902 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:27,924 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:27,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-13 17:41:27,952 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:27,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:27,978 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:27,979 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:28,037 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:28,064 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-10-13 17:41:28,065 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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-10-13 17:41:28,154 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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 40 states and 53 transitions. Complement of second has 16 states. [2024-10-13 17:41:28,158 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-10-13 17:41:28,163 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-10-13 17:41:28,164 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-13 17:41:28,165 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-13 17:41:28,166 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:28,167 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-13 17:41:28,167 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:28,167 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-13 17:41:28,167 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:28,168 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-10-13 17:41:28,174 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,179 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-10-13 17:41:28,181 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-13 17:41:28,182 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-13 17:41:28,182 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-13 17:41:28,183 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:28,184 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-13 17:41:28,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-13 17:41:28,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-13 17:41:28,209 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-10-13 17:41:28,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-13 17:41:28,213 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:41:28,213 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:41:28,213 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-13 17:41:28,213 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-13 17:41:28,214 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,214 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:28,214 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:28,215 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:28,215 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:28,216 INFO L745 eck$LassoCheckResult]: Stem: 130#$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(14, 2);call #Ultimate.allocInit(12, 3); 131#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 := 9; 120#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 132#$Ultimate##0 ~n := #in~n; 126#L17 assume !(~n < 1); 127#L19 assume !(1 == ~n); 119#L22 call #t~ret4 := fibonacci(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 123#L17 assume ~n < 1;#res := 0; 124#fibonacciFINAL assume true; 129#fibonacciEXIT >#31#return; 118#L22-1 [2024-10-13 17:41:28,216 INFO L747 eck$LassoCheckResult]: Loop: 118#L22-1 call #t~ret5 := fibonacci(~n - 2);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume !(~n < 1); 136#L19 assume !(1 == ~n); 121#L22 call #t~ret4 := fibonacci(~n - 1);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume ~n < 1;#res := 0; 134#fibonacciFINAL assume true; 135#fibonacciEXIT >#31#return; 118#L22-1 [2024-10-13 17:41:28,216 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,216 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-10-13 17:41:28,216 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1264017695] [2024-10-13 17:41:28,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,357 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:28,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,408 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:41:28,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:28,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1264017695] [2024-10-13 17:41:28,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1264017695] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:28,410 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:28,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:41:28,413 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1438304202] [2024-10-13 17:41:28,413 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:28,415 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:28,416 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,417 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-10-13 17:41:28,417 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [268301521] [2024-10-13 17:41:28,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,419 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,480 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:41:28,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,516 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:41:28,516 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:28,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [268301521] [2024-10-13 17:41:28,516 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [268301521] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:28,516 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:28,517 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:41:28,517 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [678341726] [2024-10-13 17:41:28,517 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:28,517 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:41:28,517 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:28,519 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-13 17:41:28,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-13 17:41:28,520 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-10-13 17:41:28,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:28,570 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-13 17:41:28,570 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-13 17:41:28,572 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,573 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-13 17:41:28,573 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-13 17:41:28,573 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-13 17:41:28,574 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-13 17:41:28,574 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:28,574 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:28,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-13 17:41:28,578 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-13 17:41:28,579 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-10-13 17:41:28,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-13 17:41:28,580 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:28,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-13 17:41:28,581 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:28,581 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-13 17:41:28,582 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-13 17:41:28,582 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,583 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:28,583 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:28,584 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:28,584 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-13 17:41:28,584 INFO L745 eck$LassoCheckResult]: Stem: 202#$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(14, 2);call #Ultimate.allocInit(12, 3); 203#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 := 9; 191#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 201#$Ultimate##0 ~n := #in~n; 196#L17 assume !(~n < 1); 197#L19 assume !(1 == ~n); 192#L22 call #t~ret4 := fibonacci(~n - 1);< 198#$Ultimate##0 ~n := #in~n; 194#L17 assume !(~n < 1); 195#L19 assume 1 == ~n;#res := 1; 205#fibonacciFINAL assume true; 208#fibonacciEXIT >#31#return; 189#L22-1 [2024-10-13 17:41:28,584 INFO L747 eck$LassoCheckResult]: Loop: 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume 1 == ~n;#res := 1; 210#fibonacciFINAL assume true; 207#fibonacciEXIT >#31#return; 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume ~n < 1;#res := 0; 212#fibonacciFINAL assume true; 199#fibonacciEXIT >#33#return; 200#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 204#fibonacciFINAL assume true; 206#fibonacciEXIT >#31#return; 189#L22-1 [2024-10-13 17:41:28,585 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,585 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-10-13 17:41:28,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,585 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1226502191] [2024-10-13 17:41:28,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,585 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,638 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:28,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,674 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:28,674 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:28,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1226502191] [2024-10-13 17:41:28,674 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1226502191] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:28,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1122798742] [2024-10-13 17:41:28,674 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:28,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,676 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-10-13 17:41:28,692 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-10-13 17:41:28,729 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-10-13 17:41:28,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,775 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:28,776 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:28,821 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:28,821 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:28,935 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:28,935 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1122798742] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:28,935 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:28,936 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-10-13 17:41:28,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1106390766] [2024-10-13 17:41:28,936 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:28,936 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:28,936 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,937 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-10-13 17:41:28,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1880249666] [2024-10-13 17:41:28,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:28,954 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:28,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:28,967 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:29,209 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:29,209 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:29,209 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:29,209 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:29,209 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:29,210 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,210 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:29,210 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:29,210 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-13 17:41:29,210 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:29,210 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:29,211 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,214 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,220 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,222 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,225 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,280 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:29,280 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:29,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,283 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-10-13 17:41:29,284 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-10-13 17:41:29,285 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,285 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,300 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:29,301 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:29,311 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-10-13 17:41:29,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,312 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-10-13 17:41:29,313 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-10-13 17:41:29,314 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,314 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,335 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-10-13 17:41:29,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,337 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-10-13 17:41:29,338 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-10-13 17:41:29,339 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:29,339 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,354 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:29,366 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-10-13 17:41:29,366 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:29,366 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:29,366 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:29,366 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:29,366 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:29,366 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,366 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:29,366 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:29,367 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-13 17:41:29,367 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:29,367 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:29,368 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,374 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,385 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,388 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,390 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,429 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:29,429 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:29,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,429 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,431 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-10-13 17:41:29,433 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-10-13 17:41:29,433 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-10-13 17:41:29,446 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:29,446 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:29,446 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:29,446 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:29,446 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:29,448 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:29,448 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:29,452 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:29,456 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:29,457 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:29,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,459 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-10-13 17:41:29,461 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-10-13 17:41:29,462 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:29,462 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:29,462 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:29,462 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-13 17:41:29,477 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-10-13 17:41:29,478 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:29,495 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:29,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:29,516 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:29,517 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:29,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:29,632 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:29,634 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:29,777 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:29,778 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-10-13 17:41:29,778 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-13 17:41:30,041 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 152 states and 210 transitions. Complement of second has 54 states. [2024-10-13 17:41:30,043 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-10-13 17:41:30,044 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-13 17:41:30,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-10-13 17:41:30,044 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-10-13 17:41:30,045 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,045 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-10-13 17:41:30,046 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,046 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-10-13 17:41:30,048 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,048 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-10-13 17:41:30,056 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-13 17:41:30,063 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-10-13 17:41:30,063 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-10-13 17:41:30,064 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-13 17:41:30,064 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-10-13 17:41:30,064 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:30,064 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-10-13 17:41:30,064 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-10-13 17:41:30,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-10-13 17:41:30,076 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 70 states have internal predecessors, (81), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (35), 22 states have call predecessors, (35), 23 states have call successors, (35) [2024-10-13 17:41:30,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-10-13 17:41:30,078 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-10-13 17:41:30,078 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:30,079 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-13 17:41:30,079 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-10-13 17:41:30,079 INFO L87 Difference]: Start difference. First operand 106 states and 142 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-10-13 17:41:30,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:30,214 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-10-13 17:41:30,214 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-10-13 17:41:30,219 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-13 17:41:30,223 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-10-13 17:41:30,234 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-10-13 17:41:30,235 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-10-13 17:41:30,236 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-10-13 17:41:30,236 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:30,236 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-10-13 17:41:30,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-10-13 17:41:30,250 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-13 17:41:30,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-10-13 17:41:30,255 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 74 states have (on average 1.2027027027027026) internal successors, (89), 78 states have internal predecessors, (89), 28 states have call successors, (29), 15 states have call predecessors, (29), 16 states have return successors, (39), 24 states have call predecessors, (39), 26 states have call successors, (39) [2024-10-13 17:41:30,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-10-13 17:41:30,257 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-13 17:41:30,259 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-13 17:41:30,260 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-13 17:41:30,260 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-13 17:41:30,260 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-10-13 17:41:30,263 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-13 17:41:30,263 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:30,263 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:30,265 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:30,265 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:30,265 INFO L745 eck$LassoCheckResult]: Stem: 905#$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(14, 2);call #Ultimate.allocInit(12, 3); 906#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 := 9; 880#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 907#$Ultimate##0 ~n := #in~n; 887#L17 assume !(~n < 1); 888#L19 assume !(1 == ~n); 891#L22 call #t~ret4 := fibonacci(~n - 1);< 892#$Ultimate##0 ~n := #in~n; 949#L17 assume !(~n < 1); 948#L19 assume !(1 == ~n); 937#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 947#L17 assume !(~n < 1); 945#L19 assume 1 == ~n;#res := 1; 943#fibonacciFINAL assume true; 941#fibonacciEXIT >#31#return; 883#L22-1 call #t~ret5 := fibonacci(~n - 2);< 940#$Ultimate##0 ~n := #in~n; 885#L17 assume ~n < 1;#res := 0; 886#fibonacciFINAL assume true; 992#fibonacciEXIT >#33#return; 990#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 987#fibonacciFINAL assume true; 980#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-13 17:41:30,266 INFO L747 eck$LassoCheckResult]: Loop: 913#L22-1 call #t~ret5 := fibonacci(~n - 2);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume !(1 == ~n); 914#L22 call #t~ret4 := fibonacci(~n - 1);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume 1 == ~n;#res := 1; 915#fibonacciFINAL assume true; 916#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-13 17:41:30,266 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,266 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2024-10-13 17:41:30,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [112315643] [2024-10-13 17:41:30,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,423 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-13 17:41:30,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,512 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:30,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,549 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:30,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,560 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:30,561 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:30,561 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [112315643] [2024-10-13 17:41:30,561 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [112315643] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:30,561 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2123803321] [2024-10-13 17:41:30,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:30,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,564 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,569 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-13 17:41:30,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,614 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:30,616 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:30,692 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:30,693 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:30,959 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-13 17:41:30,959 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2123803321] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:30,959 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:30,959 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-10-13 17:41:30,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [935138488] [2024-10-13 17:41:30,960 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:30,960 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:30,960 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,960 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2024-10-13 17:41:30,961 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,961 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1430181978] [2024-10-13 17:41:30,961 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,961 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,965 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:30,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,971 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:31,079 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:31,079 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:31,079 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:31,079 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:31,080 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:31,080 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,080 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:31,080 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:31,080 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-13 17:41:31,080 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:31,080 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:31,081 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,085 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,090 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,092 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,094 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,129 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:31,129 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:31,129 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,129 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,131 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-10-13 17:41:31,133 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-10-13 17:41:31,134 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:31,134 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,148 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:31,148 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=2} Honda state: {fibonacci_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:31,164 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-10-13 17:41:31,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,166 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-10-13 17:41:31,168 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-10-13 17:41:31,169 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:31,169 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,194 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-10-13 17:41:31,194 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,194 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,195 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-10-13 17:41:31,196 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-10-13 17:41:31,197 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:31,197 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,210 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:31,220 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-10-13 17:41:31,221 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:31,221 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:31,221 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:31,221 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:31,221 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:31,221 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,221 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:31,221 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:31,221 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-13 17:41:31,221 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:31,221 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:31,222 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,226 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,231 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,235 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,237 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,276 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:31,276 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:31,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,279 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-10-13 17:41:31,280 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-10-13 17:41:31,280 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-10-13 17:41:31,290 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:31,290 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:31,290 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:31,290 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:31,290 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:31,292 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:31,292 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:31,295 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:31,306 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-10-13 17:41:31,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,307 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-10-13 17:41:31,308 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-10-13 17:41:31,309 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-10-13 17:41:31,319 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:31,319 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:31,319 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:31,319 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:31,319 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:31,320 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:31,320 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:31,322 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:31,326 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:31,326 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:31,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,327 INFO L229 MonitoredProcess]: Starting monitored process 24 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-10-13 17:41:31,328 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-10-13 17:41:31,328 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:31,328 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:31,328 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:31,328 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-13 17:41:31,338 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-10-13 17:41:31,340 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:31,351 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:31,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:31,405 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:41:31,407 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:31,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:31,664 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-13 17:41:31,665 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:31,671 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:31,740 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:31,741 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-10-13 17:41:31,741 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:31,944 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 230 states and 321 transitions. Complement of second has 37 states. [2024-10-13 17:41:31,945 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-10-13 17:41:31,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:31,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-10-13 17:41:31,946 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-13 17:41:31,947 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:31,947 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:31,957 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:31,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:31,997 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:41:31,999 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:32,193 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-13 17:41:32,195 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,268 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:32,269 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-13 17:41:32,269 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:32,435 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 300 states and 408 transitions. Complement of second has 29 states. [2024-10-13 17:41:32,436 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:32,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:32,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-10-13 17:41:32,437 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-13 17:41:32,438 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,438 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:32,446 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:32,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:32,496 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:41:32,498 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:32,677 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-13 17:41:32,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,755 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:32,756 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 6 loop predicates [2024-10-13 17:41:32,756 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:32,978 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 808 states and 1112 transitions. Complement of second has 135 states. [2024-10-13 17:41:32,978 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-10-13 17:41:32,979 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:32,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-10-13 17:41:32,979 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-13 17:41:32,980 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,980 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-10-13 17:41:32,980 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,980 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-10-13 17:41:32,981 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,981 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 808 states and 1112 transitions. [2024-10-13 17:41:32,992 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-10-13 17:41:33,003 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 808 states to 427 states and 634 transitions. [2024-10-13 17:41:33,004 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 166 [2024-10-13 17:41:33,004 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-10-13 17:41:33,004 INFO L73 IsDeterministic]: Start isDeterministic. Operand 427 states and 634 transitions. [2024-10-13 17:41:33,004 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:33,005 INFO L218 hiAutomatonCegarLoop]: Abstraction has 427 states and 634 transitions. [2024-10-13 17:41:33,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states and 634 transitions. [2024-10-13 17:41:33,045 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 352. [2024-10-13 17:41:33,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 352 states, 221 states have (on average 1.1990950226244343) internal successors, (265), 235 states have internal predecessors, (265), 75 states have call successors, (84), 46 states have call predecessors, (84), 56 states have return successors, (130), 70 states have call predecessors, (130), 71 states have call successors, (130) [2024-10-13 17:41:33,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 479 transitions. [2024-10-13 17:41:33,052 INFO L240 hiAutomatonCegarLoop]: Abstraction has 352 states and 479 transitions. [2024-10-13 17:41:33,052 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:33,053 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-13 17:41:33,053 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-10-13 17:41:33,053 INFO L87 Difference]: Start difference. First operand 352 states and 479 transitions. 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-10-13 17:41:33,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:33,378 INFO L93 Difference]: Finished difference Result 707 states and 1054 transitions. [2024-10-13 17:41:33,378 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 707 states and 1054 transitions. [2024-10-13 17:41:33,388 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-13 17:41:33,398 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 707 states to 676 states and 1009 transitions. [2024-10-13 17:41:33,398 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 296 [2024-10-13 17:41:33,399 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 299 [2024-10-13 17:41:33,399 INFO L73 IsDeterministic]: Start isDeterministic. Operand 676 states and 1009 transitions. [2024-10-13 17:41:33,399 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:33,399 INFO L218 hiAutomatonCegarLoop]: Abstraction has 676 states and 1009 transitions. [2024-10-13 17:41:33,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 676 states and 1009 transitions. [2024-10-13 17:41:33,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 676 to 628. [2024-10-13 17:41:33,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 628 states, 383 states have (on average 1.1618798955613576) internal successors, (445), 406 states have internal predecessors, (445), 151 states have call successors, (165), 76 states have call predecessors, (165), 94 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-13 17:41:33,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 936 transitions. [2024-10-13 17:41:33,433 INFO L240 hiAutomatonCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-13 17:41:33,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-13 17:41:33,434 INFO L425 stractBuchiCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-13 17:41:33,435 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-13 17:41:33,435 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 628 states and 936 transitions. [2024-10-13 17:41:33,439 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-13 17:41:33,439 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:33,439 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:33,441 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:33,441 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:33,441 INFO L745 eck$LassoCheckResult]: Stem: 4310#$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(14, 2);call #Ultimate.allocInit(12, 3); 4311#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 := 9; 4312#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 4313#$Ultimate##0 ~n := #in~n; 4329#L17 assume !(~n < 1); 4398#L19 assume !(1 == ~n); 4394#L22 call #t~ret4 := fibonacci(~n - 1);< 4395#$Ultimate##0 ~n := #in~n; 4427#L17 assume !(~n < 1); 4414#L19 assume !(1 == ~n); 4407#L22 call #t~ret4 := fibonacci(~n - 1);< 4410#$Ultimate##0 ~n := #in~n; 4421#L17 assume !(~n < 1); 4412#L19 assume !(1 == ~n); 4402#L22 call #t~ret4 := fibonacci(~n - 1);< 4408#$Ultimate##0 ~n := #in~n; 4431#L17 assume !(~n < 1); 4430#L19 assume !(1 == ~n); 4424#L22 call #t~ret4 := fibonacci(~n - 1);< 4429#$Ultimate##0 ~n := #in~n; 4448#L17 assume !(~n < 1); 4447#L19 assume !(1 == ~n); 4416#L22 call #t~ret4 := fibonacci(~n - 1);< 4446#$Ultimate##0 ~n := #in~n; 4461#L17 assume !(~n < 1); 4460#L19 assume !(1 == ~n); 4344#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4345#L17 assume !(~n < 1); 4464#L19 assume !(1 == ~n); 4343#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4346#L17 assume !(~n < 1); 4536#L19 assume 1 == ~n;#res := 1; 4535#fibonacciFINAL assume true; 4530#fibonacciEXIT >#31#return; 4514#L22-1 call #t~ret5 := fibonacci(~n - 2);< 4528#$Ultimate##0 ~n := #in~n; 4777#L17 assume !(~n < 1); 4655#L19 assume !(1 == ~n); 4656#L22 call #t~ret4 := fibonacci(~n - 1);< 4707#$Ultimate##0 ~n := #in~n; 4821#L17 assume !(~n < 1); 4818#L19 assume !(1 == ~n); 4819#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-13 17:41:33,441 INFO L747 eck$LassoCheckResult]: Loop: 4828#$Ultimate##0 ~n := #in~n; 4850#L17 assume !(~n < 1); 4847#L19 assume !(1 == ~n); 4827#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-13 17:41:33,441 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:33,442 INFO L85 PathProgramCache]: Analyzing trace with hash 1729544275, now seen corresponding path program 1 times [2024-10-13 17:41:33,442 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:33,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1884434427] [2024-10-13 17:41:33,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:33,442 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:33,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-13 17:41:33,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,719 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:33,720 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:33,720 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1884434427] [2024-10-13 17:41:33,720 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1884434427] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:33,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [690313175] [2024-10-13 17:41:33,721 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:33,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:33,722 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:33,725 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-10-13 17:41:33,727 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-10-13 17:41:33,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,774 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-10-13 17:41:33,776 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:33,841 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:33,842 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:34,075 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:34,075 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [690313175] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:34,075 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:34,075 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2024-10-13 17:41:34,075 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [6852669] [2024-10-13 17:41:34,076 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:34,076 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:34,076 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:34,076 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-10-13 17:41:34,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:34,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [429446217] [2024-10-13 17:41:34,076 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:34,077 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:34,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:34,080 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:34,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:34,082 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:34,124 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:34,125 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:34,125 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:34,125 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:34,125 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:34,125 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,125 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:34,126 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:34,126 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-13 17:41:34,126 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:34,126 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:34,126 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,130 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,132 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,138 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,140 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,169 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:34,169 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:34,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,171 INFO L229 MonitoredProcess]: Starting monitored process 26 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-10-13 17:41:34,173 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-10-13 17:41:34,174 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:34,174 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,191 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:34,191 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:34,206 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:34,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,208 INFO L229 MonitoredProcess]: Starting monitored process 27 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-10-13 17:41:34,209 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-10-13 17:41:34,210 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:34,210 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,225 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:34,225 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:34,240 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:34,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,242 INFO L229 MonitoredProcess]: Starting monitored process 28 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-10-13 17:41:34,244 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-10-13 17:41:34,244 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:34,245 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,272 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-10-13 17:41:34,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,287 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-10-13 17:41:34,288 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-10-13 17:41:34,289 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:34,290 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,317 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:34,321 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-10-13 17:41:34,321 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:34,321 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:34,321 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:34,321 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:34,321 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:34,321 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,322 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:34,322 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:34,322 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-13 17:41:34,322 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:34,322 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:34,323 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,327 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,329 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,336 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,338 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,366 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:34,366 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:34,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,368 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-10-13 17:41:34,369 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-10-13 17:41:34,370 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-10-13 17:41:34,382 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,382 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,382 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,382 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,382 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,382 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,383 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,384 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:34,398 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2024-10-13 17:41:34,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,399 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,400 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-10-13 17:41:34,401 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-10-13 17:41:34,402 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-10-13 17:41:34,414 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,414 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,415 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,415 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,415 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,415 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,415 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,418 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:34,428 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-10-13 17:41:34,428 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,428 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,429 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-10-13 17:41:34,431 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-10-13 17:41:34,431 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-10-13 17:41:34,441 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,441 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,441 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,441 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,441 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,442 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,442 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,443 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:34,446 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:34,446 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:34,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,447 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,448 INFO L229 MonitoredProcess]: Starting monitored process 33 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-10-13 17:41:34,450 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-10-13 17:41:34,450 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:34,450 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:34,450 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:34,450 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-13 17:41:34,461 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-10-13 17:41:34,462 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:34,470 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:34,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,534 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,535 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:34,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,630 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,630 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:34,658 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:34,658 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-10-13 17:41:34,659 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:34,724 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-13 17:41:34,725 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-10-13 17:41:34,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:34,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-13 17:41:34,726 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-13 17:41:34,726 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:34,726 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:34,737 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:34,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,793 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,794 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:34,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,899 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,899 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:34,927 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:34,928 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-10-13 17:41:34,928 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:34,993 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-13 17:41:34,994 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-10-13 17:41:34,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:34,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-13 17:41:34,995 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-13 17:41:34,995 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:34,995 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:35,006 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:35,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,064 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-13 17:41:35,066 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:35,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,172 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:35,173 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:35,196 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:35,197 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-10-13 17:41:35,197 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:35,238 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2024-10-13 17:41:35,293 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 839 states and 1163 transitions. Complement of second has 19 states. [2024-10-13 17:41:35,294 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-10-13 17:41:35,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:35,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-10-13 17:41:35,296 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-13 17:41:35,299 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,299 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-10-13 17:41:35,299 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,299 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-10-13 17:41:35,300 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,300 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1163 transitions. [2024-10-13 17:41:35,313 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-13 17:41:35,322 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 996 transitions. [2024-10-13 17:41:35,322 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2024-10-13 17:41:35,323 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2024-10-13 17:41:35,323 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 996 transitions. [2024-10-13 17:41:35,323 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:35,323 INFO L218 hiAutomatonCegarLoop]: Abstraction has 684 states and 996 transitions. [2024-10-13 17:41:35,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 996 transitions. [2024-10-13 17:41:35,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2024-10-13 17:41:35,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 654 states, 407 states have (on average 1.1523341523341524) internal successors, (469), 432 states have internal predecessors, (469), 151 states have call successors, (165), 76 states have call predecessors, (165), 96 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-13 17:41:35,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 960 transitions. [2024-10-13 17:41:35,355 INFO L240 hiAutomatonCegarLoop]: Abstraction has 654 states and 960 transitions. [2024-10-13 17:41:35,355 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:35,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-13 17:41:35,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-10-13 17:41:35,356 INFO L87 Difference]: Start difference. First operand 654 states and 960 transitions. Second operand has 21 states, 20 states have (on average 1.8) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (10), 9 states have call predecessors, (10), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:35,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:35,651 INFO L93 Difference]: Finished difference Result 781 states and 1180 transitions. [2024-10-13 17:41:35,651 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 781 states and 1180 transitions. [2024-10-13 17:41:35,659 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-13 17:41:35,668 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 781 states to 760 states and 1148 transitions. [2024-10-13 17:41:35,668 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 279 [2024-10-13 17:41:35,669 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 282 [2024-10-13 17:41:35,669 INFO L73 IsDeterministic]: Start isDeterministic. Operand 760 states and 1148 transitions. [2024-10-13 17:41:35,669 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:35,669 INFO L218 hiAutomatonCegarLoop]: Abstraction has 760 states and 1148 transitions. [2024-10-13 17:41:35,670 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states and 1148 transitions. [2024-10-13 17:41:35,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 702. [2024-10-13 17:41:35,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 702 states, 437 states have (on average 1.1464530892448512) internal successors, (501), 462 states have internal predecessors, (501), 169 states have call successors, (185), 86 states have call predecessors, (185), 96 states have return successors, (336), 153 states have call predecessors, (336), 159 states have call successors, (336) [2024-10-13 17:41:35,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 702 states to 702 states and 1022 transitions. [2024-10-13 17:41:35,693 INFO L240 hiAutomatonCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-13 17:41:35,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-13 17:41:35,694 INFO L425 stractBuchiCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-13 17:41:35,694 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-13 17:41:35,694 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 702 states and 1022 transitions. [2024-10-13 17:41:35,699 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-13 17:41:35,699 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:35,699 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:35,702 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:35,702 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:35,702 INFO L745 eck$LassoCheckResult]: Stem: 9342#$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(14, 2);call #Ultimate.allocInit(12, 3); 9343#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 := 9; 9344#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 9345#$Ultimate##0 ~n := #in~n; 9513#L17 assume !(~n < 1); 9512#L19 assume !(1 == ~n); 9490#L22 call #t~ret4 := fibonacci(~n - 1);< 9491#$Ultimate##0 ~n := #in~n; 9555#L17 assume !(~n < 1); 9553#L19 assume !(1 == ~n); 9545#L22 call #t~ret4 := fibonacci(~n - 1);< 9551#$Ultimate##0 ~n := #in~n; 9550#L17 assume !(~n < 1); 9547#L19 assume !(1 == ~n); 9509#L22 call #t~ret4 := fibonacci(~n - 1);< 9546#$Ultimate##0 ~n := #in~n; 9661#L17 assume !(~n < 1); 9657#L19 assume !(1 == ~n); 9653#L22 call #t~ret4 := fibonacci(~n - 1);< 9655#$Ultimate##0 ~n := #in~n; 9680#L17 assume !(~n < 1); 9679#L19 assume !(1 == ~n); 9319#L22 call #t~ret4 := fibonacci(~n - 1);< 9678#$Ultimate##0 ~n := #in~n; 9723#L17 assume !(~n < 1); 9721#L19 assume !(1 == ~n); 9674#L22 call #t~ret4 := fibonacci(~n - 1);< 9698#$Ultimate##0 ~n := #in~n; 9792#L17 assume !(~n < 1); 9777#L19 assume !(1 == ~n); 9694#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9819#L17 assume !(~n < 1); 9815#L19 assume !(1 == ~n); 9693#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9822#L17 assume !(~n < 1); 9820#L19 assume 1 == ~n;#res := 1; 9816#fibonacciFINAL assume true; 9808#fibonacciEXIT >#31#return; 9715#L22-1 call #t~ret5 := fibonacci(~n - 2);< 9726#$Ultimate##0 ~n := #in~n; 9846#L17 assume !(~n < 1); 9909#L19 assume !(1 == ~n); 9368#L22 call #t~ret4 := fibonacci(~n - 1);< 9374#$Ultimate##0 ~n := #in~n; 9375#L17 assume !(~n < 1); 9973#L19 assume !(1 == ~n); 9354#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-13 17:41:35,702 INFO L747 eck$LassoCheckResult]: Loop: 9355#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-13 17:41:35,702 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:35,702 INFO L85 PathProgramCache]: Analyzing trace with hash 1537328375, now seen corresponding path program 2 times [2024-10-13 17:41:35,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:35,703 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1415868091] [2024-10-13 17:41:35,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:35,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:35,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,964 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-13 17:41:35,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,968 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-13 17:41:35,968 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:35,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1415868091] [2024-10-13 17:41:35,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1415868091] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:35,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [173339028] [2024-10-13 17:41:35,968 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-13 17:41:35,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:35,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:35,970 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:35,974 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2024-10-13 17:41:36,023 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-13 17:41:36,024 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:36,025 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-10-13 17:41:36,026 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:36,089 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-13 17:41:36,089 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:36,284 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-13 17:41:36,284 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [173339028] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:36,285 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:36,285 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2024-10-13 17:41:36,285 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028319975] [2024-10-13 17:41:36,285 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:36,285 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:36,286 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:36,286 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-10-13 17:41:36,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:36,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1923042113] [2024-10-13 17:41:36,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:36,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:36,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:36,289 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:36,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:36,291 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:36,366 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:36,367 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:36,367 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:36,367 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:36,367 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:36,367 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:36,367 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:36,367 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:36,367 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-13 17:41:36,367 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:36,367 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:36,368 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:36,370 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:36,371 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:36,380 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:36,422 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:36,422 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:36,422 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:36,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:36,427 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-10-13 17:41:36,428 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-10-13 17:41:36,430 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:36,430 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:36,447 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:36,447 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:36,460 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-10-13 17:41:36,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:36,460 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:36,461 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-10-13 17:41:36,462 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-10-13 17:41:36,463 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:36,463 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:36,474 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:36,474 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:36,485 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2024-10-13 17:41:36,485 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:36,485 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:36,486 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-10-13 17:41:36,488 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-10-13 17:41:36,488 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:36,488 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:36,517 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-10-13 17:41:36,518 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:36,518 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:36,519 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-10-13 17:41:36,519 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-10-13 17:41:36,520 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:36,520 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:37,688 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:37,693 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-10-13 17:41:37,694 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:37,694 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:37,694 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:37,694 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:37,694 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:37,694 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,694 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:37,694 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:37,694 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-13 17:41:37,694 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:37,694 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:37,695 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,697 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,698 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,704 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,736 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:37,736 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:37,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,736 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:37,737 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-10-13 17:41:37,738 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-10-13 17:41:37,739 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-10-13 17:41:37,751 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:37,751 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:37,751 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:37,751 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:37,751 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:37,752 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:37,752 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:37,755 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:37,767 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:37,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:37,769 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-10-13 17:41:37,769 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-10-13 17:41:37,771 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-10-13 17:41:37,780 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:37,780 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:37,781 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:37,781 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:37,781 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:37,781 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:37,781 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:37,783 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:37,796 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Ended with exit code 0 [2024-10-13 17:41:37,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:37,797 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-10-13 17:41:37,798 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-10-13 17:41:37,798 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-10-13 17:41:37,808 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:37,808 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:37,808 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:37,808 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:37,808 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:37,809 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:37,809 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:37,813 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:37,817 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-13 17:41:37,817 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:37,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:37,820 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-10-13 17:41:37,822 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-10-13 17:41:37,822 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:37,822 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:37,823 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:37,823 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-13 17:41:37,837 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-10-13 17:41:37,838 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:37,852 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:37,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:37,916 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-13 17:41:37,918 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:38,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:38,029 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:38,030 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:38,061 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:38,062 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-10-13 17:41:38,062 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:38,114 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 724 states and 1045 transitions. Complement of second has 18 states. [2024-10-13 17:41:38,114 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-10-13 17:41:38,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:38,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-13 17:41:38,115 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-13 17:41:38,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:38,115 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:38,126 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:38,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:38,187 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-13 17:41:38,189 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:38,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:38,287 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:38,288 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:38,318 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:38,318 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-10-13 17:41:38,318 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:38,403 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 944 states and 1356 transitions. Complement of second has 22 states. [2024-10-13 17:41:38,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:38,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:38,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-10-13 17:41:38,405 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-13 17:41:38,405 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:38,405 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-10-13 17:41:38,405 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:38,405 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2024-10-13 17:41:38,405 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:38,405 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 944 states and 1356 transitions. [2024-10-13 17:41:38,414 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-13 17:41:38,423 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 944 states to 874 states and 1278 transitions. [2024-10-13 17:41:38,423 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2024-10-13 17:41:38,424 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 310 [2024-10-13 17:41:38,424 INFO L73 IsDeterministic]: Start isDeterministic. Operand 874 states and 1278 transitions. [2024-10-13 17:41:38,424 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:38,424 INFO L218 hiAutomatonCegarLoop]: Abstraction has 874 states and 1278 transitions. [2024-10-13 17:41:38,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 874 states and 1278 transitions. [2024-10-13 17:41:38,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 874 to 854. [2024-10-13 17:41:38,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 854 states, 537 states have (on average 1.1340782122905029) internal successors, (609), 569 states have internal predecessors, (609), 202 states have call successors, (236), 111 states have call predecessors, (236), 115 states have return successors, (409), 173 states have call predecessors, (409), 192 states have call successors, (409) [2024-10-13 17:41:38,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1254 transitions. [2024-10-13 17:41:38,446 INFO L240 hiAutomatonCegarLoop]: Abstraction has 854 states and 1254 transitions. [2024-10-13 17:41:38,446 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:38,447 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-13 17:41:38,447 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2024-10-13 17:41:38,447 INFO L87 Difference]: Start difference. First operand 854 states and 1254 transitions. Second operand has 21 states, 20 states have (on average 1.75) internal successors, (35), 12 states have internal predecessors, (35), 10 states have call successors, (11), 11 states have call predecessors, (11), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:38,733 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:38,734 INFO L93 Difference]: Finished difference Result 471 states and 558 transitions. [2024-10-13 17:41:38,734 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 471 states and 558 transitions. [2024-10-13 17:41:38,737 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:41:38,737 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 471 states to 0 states and 0 transitions. [2024-10-13 17:41:38,737 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-13 17:41:38,737 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-13 17:41:38,737 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-13 17:41:38,738 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-13 17:41:38,738 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:38,738 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:38,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-13 17:41:38,738 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:38,739 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-13 17:41:38,739 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-13 17:41:38,739 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:41:38,739 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-13 17:41:38,746 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 13.10 05:41:38 BoogieIcfgContainer [2024-10-13 17:41:38,746 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-13 17:41:38,747 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-13 17:41:38,747 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-13 17:41:38,747 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-13 17:41:38,747 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:26" (3/4) ... [2024-10-13 17:41:38,749 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-13 17:41:38,750 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-13 17:41:38,751 INFO L158 Benchmark]: Toolchain (without parser) took 12371.66ms. Allocated memory was 161.5MB in the beginning and 234.9MB in the end (delta: 73.4MB). Free memory was 124.5MB in the beginning and 79.9MB in the end (delta: 44.5MB). Peak memory consumption was 116.8MB. Max. memory is 16.1GB. [2024-10-13 17:41:38,751 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 100.7MB. Free memory is still 67.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:41:38,751 INFO L158 Benchmark]: CACSL2BoogieTranslator took 247.56ms. Allocated memory is still 161.5MB. Free memory was 123.6MB in the beginning and 112.8MB in the end (delta: 10.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-13 17:41:38,751 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.93ms. Allocated memory is still 161.5MB. Free memory was 112.8MB in the beginning and 110.9MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:38,751 INFO L158 Benchmark]: Boogie Preprocessor took 35.08ms. Allocated memory is still 161.5MB. Free memory was 110.9MB in the beginning and 109.8MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:38,752 INFO L158 Benchmark]: RCFGBuilder took 267.40ms. Allocated memory is still 161.5MB. Free memory was 109.8MB in the beginning and 129.0MB in the end (delta: -19.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-13 17:41:38,752 INFO L158 Benchmark]: BuchiAutomizer took 11780.03ms. Allocated memory was 161.5MB in the beginning and 234.9MB in the end (delta: 73.4MB). Free memory was 128.2MB in the beginning and 79.9MB in the end (delta: 48.2MB). Peak memory consumption was 123.4MB. Max. memory is 16.1GB. [2024-10-13 17:41:38,752 INFO L158 Benchmark]: Witness Printer took 3.49ms. Allocated memory is still 234.9MB. Free memory is still 79.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:41:38,753 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.17ms. Allocated memory is still 100.7MB. Free memory is still 67.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 247.56ms. Allocated memory is still 161.5MB. Free memory was 123.6MB in the beginning and 112.8MB in the end (delta: 10.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 32.93ms. Allocated memory is still 161.5MB. Free memory was 112.8MB in the beginning and 110.9MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 35.08ms. Allocated memory is still 161.5MB. Free memory was 110.9MB in the beginning and 109.8MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 267.40ms. Allocated memory is still 161.5MB. Free memory was 109.8MB in the beginning and 129.0MB in the end (delta: -19.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 11780.03ms. Allocated memory was 161.5MB in the beginning and 234.9MB in the end (delta: 73.4MB). Free memory was 128.2MB in the beginning and 79.9MB in the end (delta: 48.2MB). Peak memory consumption was 123.4MB. Max. memory is 16.1GB. * Witness Printer took 3.49ms. Allocated memory is still 234.9MB. Free memory is still 79.9MB. 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 (5 trivial, 3 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 11 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 11.7s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 6.2s. Construction of modules took 1.0s. 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, 265 StatesRemovedByMinimization, 8 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, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 596 SdHoareTripleChecker+Valid, 1.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 571 mSDsluCounter, 658 SdHoareTripleChecker+Invalid, 1.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 425 mSDsCounter, 357 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1357 IncrementalHoareTripleChecker+Invalid, 1714 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 357 mSolverCounterUnsat, 233 mSDtfsCounter, 1357 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI1 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp82 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf92 smp80 dnf100 smp100 tf112 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 19ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-13 17:41:38,774 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-10-13 17:41:38,979 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:39,178 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-10-13 17:41:39,378 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:39,579 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:39,780 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE