./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/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.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive/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.3.0-?-8fc3dc6-m [2025-03-17 20:34:54,402 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 20:34:54,468 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-03-17 20:34:54,472 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 20:34:54,473 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 20:34:54,473 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-17 20:34:54,492 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 20:34:54,494 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 20:34:54,494 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 20:34:54,495 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 20:34:54,495 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 20:34:54,495 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 20:34:54,495 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 20:34:54,496 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 20:34:54,496 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-17 20:34:54,496 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-17 20:34:54,496 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-17 20:34:54,496 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-17 20:34:54,496 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-17 20:34:54,496 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-17 20:34:54,497 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 20:34:54,497 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-17 20:34:54,498 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 20:34:54,498 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 20:34:54,498 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 20:34:54,498 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 20:34:54,498 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 20:34:54,498 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 20:34:54,499 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-17 20:34:54,499 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR 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 [2025-03-17 20:34:54,740 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 20:34:54,746 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 20:34:54,749 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 20:34:54,750 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 20:34:54,750 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 20:34:54,752 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci02.c [2025-03-17 20:34:55,931 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0878467ab/cb1cc04f4c6140ef86ed86a98ae75393/FLAGb7a0e19b8 [2025-03-17 20:34:56,151 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 20:34:56,153 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2025-03-17 20:34:56,158 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0878467ab/cb1cc04f4c6140ef86ed86a98ae75393/FLAGb7a0e19b8 [2025-03-17 20:34:56,518 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0878467ab/cb1cc04f4c6140ef86ed86a98ae75393 [2025-03-17 20:34:56,521 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 20:34:56,523 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 20:34:56,524 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 20:34:56,525 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 20:34:56,528 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 20:34:56,529 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,531 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6da76ceb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56, skipping insertion in model container [2025-03-17 20:34:56,532 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,544 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 20:34:56,674 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 20:34:56,683 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 20:34:56,694 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 20:34:56,710 INFO L204 MainTranslator]: Completed translation [2025-03-17 20:34:56,710 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56 WrapperNode [2025-03-17 20:34:56,711 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 20:34:56,713 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 20:34:56,713 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 20:34:56,713 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 20:34:56,719 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,724 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,733 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2025-03-17 20:34:56,733 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 20:34:56,733 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 20:34:56,733 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 20:34:56,734 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 20:34:56,739 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,740 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,741 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,749 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]. [2025-03-17 20:34:56,749 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,749 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,750 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,751 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,752 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,755 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,756 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 20:34:56,759 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 20:34:56,759 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 20:34:56,759 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 20:34:56,760 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (1/1) ... [2025-03-17 20:34:56,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:56,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:56,787 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) [2025-03-17 20:34:56,789 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 [2025-03-17 20:34:56,810 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-03-17 20:34:56,810 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-03-17 20:34:56,810 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-17 20:34:56,811 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 20:34:56,811 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 20:34:56,811 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-17 20:34:56,846 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 20:34:56,848 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 20:34:56,897 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-03-17 20:34:56,927 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-03-17 20:34:56,927 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 20:34:56,937 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 20:34:56,937 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 20:34:56,938 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:34:56 BoogieIcfgContainer [2025-03-17 20:34:56,938 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 20:34:56,939 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-17 20:34:56,939 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-17 20:34:56,943 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-17 20:34:56,943 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:34:56,944 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.03 08:34:56" (1/3) ... [2025-03-17 20:34:56,945 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3ad6e61b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 08:34:56, skipping insertion in model container [2025-03-17 20:34:56,945 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:34:56,945 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:56" (2/3) ... [2025-03-17 20:34:56,946 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3ad6e61b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 08:34:56, skipping insertion in model container [2025-03-17 20:34:56,946 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:34:56,946 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:34:56" (3/3) ... [2025-03-17 20:34:56,947 INFO L363 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2025-03-17 20:34:56,989 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-17 20:34:56,989 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-17 20:34:56,990 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-17 20:34:56,990 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-17 20:34:56,990 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-17 20:34:56,991 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-17 20:34:56,991 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-17 20:34:56,991 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-17 20:34:56,995 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 10 states have internal predecessors, (13), 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) [2025-03-17 20:34:57,009 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-17 20:34:57,010 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:57,010 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:57,013 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 20:34:57,013 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-17 20:34:57,013 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-17 20:34:57,014 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 10 states have internal predecessors, (13), 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) [2025-03-17 20:34:57,015 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-17 20:34:57,015 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:57,015 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:57,015 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 20:34:57,016 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-17 20:34:57,021 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< [2025-03-17 20:34:57,021 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-03-17 20:34:57,024 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:57,025 INFO L85 PathProgramCache]: Analyzing trace with hash 1479, now seen corresponding path program 1 times [2025-03-17 20:34:57,030 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:57,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1635569549] [2025-03-17 20:34:57,031 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:57,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:57,078 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:34:57,092 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:34:57,093 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:57,093 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:57,096 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:34:57,099 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:34:57,101 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,101 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:57,112 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:57,114 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:57,114 INFO L85 PathProgramCache]: Analyzing trace with hash 1168782, now seen corresponding path program 1 times [2025-03-17 20:34:57,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:57,115 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2126574118] [2025-03-17 20:34:57,115 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:57,115 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:57,121 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:34:57,124 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:34:57,124 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,124 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:57,124 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:57,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:34:57,127 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:34:57,128 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,128 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:57,129 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:57,131 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:57,131 INFO L85 PathProgramCache]: Analyzing trace with hash 1366132820, now seen corresponding path program 1 times [2025-03-17 20:34:57,131 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:57,131 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1219847094] [2025-03-17 20:34:57,132 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:57,132 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:57,136 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-17 20:34:57,142 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-17 20:34:57,142 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,142 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:57,142 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:57,144 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-17 20:34:57,149 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-17 20:34:57,149 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,149 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:57,150 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:57,240 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:57,240 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:57,241 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:57,241 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:57,241 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:34:57,241 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,241 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:57,241 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:57,241 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2025-03-17 20:34:57,241 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:57,241 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:57,249 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,254 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,258 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,261 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,263 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,329 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:57,329 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:34:57,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,331 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,332 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) [2025-03-17 20:34:57,333 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 [2025-03-17 20:34:57,338 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:57,338 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:57,352 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:34:57,352 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:34:57,358 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2025-03-17 20:34:57,358 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,360 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) [2025-03-17 20:34:57,361 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 [2025-03-17 20:34:57,362 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:57,363 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:57,373 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:34:57,373 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:34:57,379 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 [2025-03-17 20:34:57,379 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,381 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) [2025-03-17 20:34:57,381 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 [2025-03-17 20:34:57,384 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:57,384 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:57,396 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:34:57,396 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:34:57,402 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 [2025-03-17 20:34:57,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,405 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) [2025-03-17 20:34:57,406 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 [2025-03-17 20:34:57,408 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:57,408 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:57,419 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:34:57,419 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:34:57,425 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 [2025-03-17 20:34:57,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,426 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,427 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) [2025-03-17 20:34:57,429 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 [2025-03-17 20:34:57,431 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:57,431 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:57,451 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2025-03-17 20:34:57,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,453 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) [2025-03-17 20:34:57,454 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 [2025-03-17 20:34:57,456 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:34:57,456 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:57,502 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:34:57,505 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-03-17 20:34:57,506 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:57,506 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:57,506 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:57,506 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:57,506 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:34:57,506 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,506 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:57,506 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:57,506 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2025-03-17 20:34:57,506 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:57,506 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:57,507 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,509 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,511 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,513 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,514 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:57,560 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:57,563 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:34:57,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,568 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) [2025-03-17 20:34:57,570 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 [2025-03-17 20:34:57,571 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 [2025-03-17 20:34:57,582 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:57,582 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:57,583 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:57,583 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:57,583 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:57,587 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:57,588 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:57,597 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:34:57,602 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 [2025-03-17 20:34:57,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,606 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) [2025-03-17 20:34:57,606 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 [2025-03-17 20:34:57,608 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 [2025-03-17 20:34:57,618 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:57,619 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:57,619 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:57,619 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:57,619 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:57,619 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:57,620 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:57,622 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:34:57,628 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 [2025-03-17 20:34:57,628 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,628 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,630 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) [2025-03-17 20:34:57,631 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 [2025-03-17 20:34:57,633 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 [2025-03-17 20:34:57,644 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:57,644 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:57,644 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:57,644 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:57,644 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:57,645 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:57,645 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:57,646 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:34:57,652 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-03-17 20:34:57,652 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,654 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) [2025-03-17 20:34:57,655 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 [2025-03-17 20:34:57,655 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 [2025-03-17 20:34:57,665 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:57,665 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:57,665 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:57,665 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:57,665 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:57,666 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:57,666 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:57,667 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:34:57,672 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 [2025-03-17 20:34:57,673 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,673 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,674 INFO L229 MonitoredProcess]: Starting monitored process 12 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) [2025-03-17 20:34:57,675 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-03-17 20:34:57,676 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 [2025-03-17 20:34:57,686 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:57,686 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:57,686 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:57,686 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:57,686 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:57,688 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:57,688 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:57,691 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:34:57,694 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:34:57,696 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-17 20:34:57,697 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:57,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:57,699 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) [2025-03-17 20:34:57,700 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 [2025-03-17 20:34:57,701 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:34:57,701 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:34:57,701 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:34:57,702 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2025-03-17 20:34:57,707 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2025-03-17 20:34:57,709 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:34:57,724 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:57,732 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:34:57,740 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:34:57,741 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,741 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:57,742 INFO L256 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-17 20:34:57,743 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:57,750 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:34:57,755 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:34:57,755 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,755 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:57,756 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:34:57,757 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:57,796 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:34:57,818 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 [2025-03-17 20:34:57,820 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 10 states have internal predecessors, (13), 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.0) internal successors, (4), 3 states have internal predecessors, (4), 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) [2025-03-17 20:34:57,887 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 10 states have internal predecessors, (13), 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.0) internal successors, (4), 3 states have internal predecessors, (4), 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 37 states and 50 transitions. Complement of second has 16 states. [2025-03-17 20:34:57,889 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 [2025-03-17 20:34:57,891 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.0) internal successors, (4), 3 states have internal predecessors, (4), 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) [2025-03-17 20:34:57,893 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 9 transitions. [2025-03-17 20:34:57,895 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 9 transitions. Stem has 2 letters. Loop has 4 letters. [2025-03-17 20:34:57,896 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:57,896 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 9 transitions. Stem has 6 letters. Loop has 4 letters. [2025-03-17 20:34:57,896 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:57,896 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 9 transitions. Stem has 2 letters. Loop has 8 letters. [2025-03-17 20:34:57,897 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:57,897 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 37 states and 50 transitions. [2025-03-17 20:34:57,900 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-17 20:34:57,903 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 37 states to 22 states and 30 transitions. [2025-03-17 20:34:57,904 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 14 [2025-03-17 20:34:57,904 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 15 [2025-03-17 20:34:57,904 INFO L73 IsDeterministic]: Start isDeterministic. Operand 22 states and 30 transitions. [2025-03-17 20:34:57,905 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:34:57,905 INFO L218 hiAutomatonCegarLoop]: Abstraction has 22 states and 30 transitions. [2025-03-17 20:34:57,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states and 30 transitions. [2025-03-17 20:34:57,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 19. [2025-03-17 20:34:57,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 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) [2025-03-17 20:34:57,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2025-03-17 20:34:57,921 INFO L240 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2025-03-17 20:34:57,921 INFO L432 stractBuchiCegarLoop]: Abstraction has 19 states and 25 transitions. [2025-03-17 20:34:57,921 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-17 20:34:57,921 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 19 states and 25 transitions. [2025-03-17 20:34:57,921 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-17 20:34:57,921 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:57,921 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:57,922 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:57,922 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:57,922 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#21#return;" [2025-03-17 20:34:57,922 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#21#return;" [2025-03-17 20:34:57,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:57,923 INFO L85 PathProgramCache]: Analyzing trace with hash 1410130552, now seen corresponding path program 1 times [2025-03-17 20:34:57,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:57,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1352576277] [2025-03-17 20:34:57,923 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:57,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:57,928 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:34:57,938 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:34:57,938 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:57,938 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:58,046 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-17 20:34:58,046 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:34:58,047 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1352576277] [2025-03-17 20:34:58,048 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1352576277] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 20:34:58,048 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 20:34:58,048 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-17 20:34:58,048 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [402549570] [2025-03-17 20:34:58,049 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 20:34:58,050 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:34:58,050 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:58,051 INFO L85 PathProgramCache]: Analyzing trace with hash 499700450, now seen corresponding path program 1 times [2025-03-17 20:34:58,051 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:58,051 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [915150851] [2025-03-17 20:34:58,051 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:58,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:58,054 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:34:58,058 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:34:58,059 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,060 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:58,122 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 [2025-03-17 20:34:58,140 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-17 20:34:58,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:34:58,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [915150851] [2025-03-17 20:34:58,140 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [915150851] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 20:34:58,140 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 20:34:58,140 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-17 20:34:58,140 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [301935326] [2025-03-17 20:34:58,140 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 20:34:58,141 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-17 20:34:58,141 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:34:58,142 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-17 20:34:58,142 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-03-17 20:34:58,143 INFO L87 Difference]: Start difference. First operand 19 states and 25 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) [2025-03-17 20:34:58,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:34:58,205 INFO L93 Difference]: Finished difference Result 25 states and 31 transitions. [2025-03-17 20:34:58,205 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 25 states and 31 transitions. [2025-03-17 20:34:58,206 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-17 20:34:58,206 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 25 states to 23 states and 29 transitions. [2025-03-17 20:34:58,207 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 19 [2025-03-17 20:34:58,207 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 19 [2025-03-17 20:34:58,207 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 29 transitions. [2025-03-17 20:34:58,207 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:34:58,207 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 29 transitions. [2025-03-17 20:34:58,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 29 transitions. [2025-03-17 20:34:58,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2025-03-17 20:34:58,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 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) [2025-03-17 20:34:58,211 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 29 transitions. [2025-03-17 20:34:58,212 INFO L240 hiAutomatonCegarLoop]: Abstraction has 23 states and 29 transitions. [2025-03-17 20:34:58,212 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-17 20:34:58,213 INFO L432 stractBuchiCegarLoop]: Abstraction has 23 states and 29 transitions. [2025-03-17 20:34:58,214 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-17 20:34:58,214 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 23 states and 29 transitions. [2025-03-17 20:34:58,214 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-17 20:34:58,215 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:58,215 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:58,215 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:58,216 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:58,216 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#21#return;" [2025-03-17 20:34:58,216 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#21#return;" [2025-03-17 20:34:58,216 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:58,217 INFO L85 PathProgramCache]: Analyzing trace with hash 764574650, now seen corresponding path program 1 times [2025-03-17 20:34:58,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:58,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1458843884] [2025-03-17 20:34:58,217 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:58,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:58,225 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-17 20:34:58,227 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-17 20:34:58,227 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,227 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:58,297 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:34:58,298 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:34:58,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1458843884] [2025-03-17 20:34:58,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1458843884] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:34:58,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1865930358] [2025-03-17 20:34:58,298 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:58,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:34:58,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,314 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 20:34:58,315 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-17 20:34:58,335 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-17 20:34:58,345 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-17 20:34:58,345 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,345 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:58,348 INFO L256 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-17 20:34:58,349 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:58,374 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:34:58,374 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 20:34:58,470 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:34:58,471 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1865930358] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 20:34:58,471 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 20:34:58,471 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2025-03-17 20:34:58,471 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2053613094] [2025-03-17 20:34:58,471 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 20:34:58,471 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:34:58,472 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:58,472 INFO L85 PathProgramCache]: Analyzing trace with hash -1688954736, now seen corresponding path program 1 times [2025-03-17 20:34:58,472 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:58,472 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1766615212] [2025-03-17 20:34:58,472 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:58,472 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:58,476 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:34:58,478 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:34:58,478 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,478 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:58,478 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:58,479 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:34:58,483 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:34:58,486 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,486 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:58,487 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:58,572 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:58,572 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:58,572 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:58,572 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:58,572 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:34:58,572 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,572 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:58,572 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:58,572 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2025-03-17 20:34:58,572 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:58,573 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:58,573 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,575 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,579 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,581 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,584 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,614 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:58,614 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:34:58,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,618 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) [2025-03-17 20:34:58,620 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 [2025-03-17 20:34:58,621 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:58,621 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:58,632 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:34:58,632 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:34:58,639 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 [2025-03-17 20:34:58,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,641 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) [2025-03-17 20:34:58,642 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 [2025-03-17 20:34:58,645 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:58,645 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:58,669 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2025-03-17 20:34:58,670 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,672 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) [2025-03-17 20:34:58,673 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 [2025-03-17 20:34:58,673 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:34:58,673 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:58,685 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:34:58,691 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 [2025-03-17 20:34:58,691 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:58,691 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:58,691 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:58,691 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:58,691 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:34:58,691 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,691 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:58,691 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:58,691 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2025-03-17 20:34:58,691 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:58,691 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:58,692 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,700 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,709 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,711 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,713 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:58,746 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:58,746 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:34:58,746 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,747 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,749 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 20:34:58,750 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-03-17 20:34:58,752 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 [2025-03-17 20:34:58,762 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:58,762 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:58,762 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:58,762 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:58,762 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:58,764 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:58,764 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:58,765 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:34:58,770 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2025-03-17 20:34:58,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,774 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) [2025-03-17 20:34:58,775 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 [2025-03-17 20:34:58,776 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 [2025-03-17 20:34:58,785 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:58,786 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:58,786 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:58,786 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:58,786 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:58,787 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:58,787 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:58,788 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:34:58,790 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:34:58,790 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-17 20:34:58,790 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,791 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,792 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) [2025-03-17 20:34:58,793 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 [2025-03-17 20:34:58,794 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:34:58,794 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:34:58,794 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:34:58,794 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-03-17 20:34:58,799 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2025-03-17 20:34:58,800 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:34:58,810 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:58,815 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-17 20:34:58,825 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-17 20:34:58,825 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:58,826 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-17 20:34:58,826 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:58,918 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:34:58,930 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:34:58,930 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,930 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:58,931 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-17 20:34:58,936 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:59,040 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:34:59,040 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 [2025-03-17 20:34:59,041 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 23 states and 29 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-17 20:34:59,267 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 23 states and 29 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 127 states and 177 transitions. Complement of second has 40 states. [2025-03-17 20:34:59,269 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 [2025-03-17 20:34:59,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-17 20:34:59,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 39 transitions. [2025-03-17 20:34:59,271 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 39 transitions. Stem has 11 letters. Loop has 10 letters. [2025-03-17 20:34:59,272 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:59,272 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 39 transitions. Stem has 21 letters. Loop has 10 letters. [2025-03-17 20:34:59,272 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:59,272 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 39 transitions. Stem has 11 letters. Loop has 20 letters. [2025-03-17 20:34:59,272 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:59,273 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 127 states and 177 transitions. [2025-03-17 20:34:59,277 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-17 20:34:59,280 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 127 states to 104 states and 150 transitions. [2025-03-17 20:34:59,281 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 61 [2025-03-17 20:34:59,281 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 65 [2025-03-17 20:34:59,281 INFO L73 IsDeterministic]: Start isDeterministic. Operand 104 states and 150 transitions. [2025-03-17 20:34:59,281 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:34:59,281 INFO L218 hiAutomatonCegarLoop]: Abstraction has 104 states and 150 transitions. [2025-03-17 20:34:59,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states and 150 transitions. [2025-03-17 20:34:59,289 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 93. [2025-03-17 20:34:59,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 57 states have (on average 1.2280701754385965) internal successors, (70), 63 states have internal predecessors, (70), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (35), 18 states have call predecessors, (35), 19 states have call successors, (35) [2025-03-17 20:34:59,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 127 transitions. [2025-03-17 20:34:59,291 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 127 transitions. [2025-03-17 20:34:59,291 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:34:59,291 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-17 20:34:59,291 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-17 20:34:59,292 INFO L87 Difference]: Start difference. First operand 93 states and 127 transitions. Second operand has 11 states, 8 states have (on average 1.875) internal successors, (15), 7 states have internal predecessors, (15), 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) [2025-03-17 20:34:59,396 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2025-03-17 20:34:59,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:34:59,418 INFO L93 Difference]: Finished difference Result 118 states and 162 transitions. [2025-03-17 20:34:59,418 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 118 states and 162 transitions. [2025-03-17 20:34:59,420 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-17 20:34:59,422 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 118 states to 113 states and 157 transitions. [2025-03-17 20:34:59,422 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2025-03-17 20:34:59,423 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 72 [2025-03-17 20:34:59,423 INFO L73 IsDeterministic]: Start isDeterministic. Operand 113 states and 157 transitions. [2025-03-17 20:34:59,423 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:34:59,423 INFO L218 hiAutomatonCegarLoop]: Abstraction has 113 states and 157 transitions. [2025-03-17 20:34:59,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states and 157 transitions. [2025-03-17 20:34:59,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 105. [2025-03-17 20:34:59,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 65 states have (on average 1.2) internal successors, (78), 71 states have internal predecessors, (78), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (39), 20 states have call predecessors, (39), 22 states have call successors, (39) [2025-03-17 20:34:59,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 142 transitions. [2025-03-17 20:34:59,429 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 142 transitions. [2025-03-17 20:34:59,429 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-17 20:34:59,430 INFO L432 stractBuchiCegarLoop]: Abstraction has 105 states and 142 transitions. [2025-03-17 20:34:59,430 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-17 20:34:59,430 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 142 transitions. [2025-03-17 20:34:59,431 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-17 20:34:59,431 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:59,431 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:59,432 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:59,432 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:59,432 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#21#return;" "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#19#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#return;" [2025-03-17 20:34:59,432 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#21#return;" [2025-03-17 20:34:59,432 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,432 INFO L85 PathProgramCache]: Analyzing trace with hash -724959954, now seen corresponding path program 1 times [2025-03-17 20:34:59,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1244862716] [2025-03-17 20:34:59,432 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,432 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,435 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:34:59,441 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:34:59,441 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,441 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:59,564 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-17 20:34:59,565 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:34:59,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1244862716] [2025-03-17 20:34:59,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1244862716] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:34:59,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1802574895] [2025-03-17 20:34:59,565 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:34:59,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,567 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 20:34:59,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-17 20:34:59,587 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:34:59,594 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:34:59,594 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,594 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:59,595 INFO L256 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:34:59,596 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:59,644 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-17 20:34:59,645 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 20:34:59,875 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-17 20:34:59,875 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1802574895] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 20:34:59,875 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 20:34:59,876 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 12] total 20 [2025-03-17 20:34:59,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1367607060] [2025-03-17 20:34:59,876 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 20:34:59,876 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:34:59,876 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,876 INFO L85 PathProgramCache]: Analyzing trace with hash -1688954736, now seen corresponding path program 2 times [2025-03-17 20:34:59,876 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [181147247] [2025-03-17 20:34:59,877 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:34:59,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,880 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 10 statements into 2 equivalence classes. [2025-03-17 20:34:59,882 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:34:59,882 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:34:59,882 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,882 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:59,883 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:34:59,884 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:34:59,884 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,884 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,885 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:59,958 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:59,958 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:59,958 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:59,958 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:59,958 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:34:59,958 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,958 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:59,958 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:59,959 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2025-03-17 20:34:59,959 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:59,959 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:59,959 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,961 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,963 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,964 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,966 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,995 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:59,995 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:34:59,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,997 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) [2025-03-17 20:34:59,999 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 [2025-03-17 20:35:00,000 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,000 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,011 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,011 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:00,017 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 [2025-03-17 20:35:00,017 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,017 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,019 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) [2025-03-17 20:35:00,020 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 [2025-03-17 20:35:00,021 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,021 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,032 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,032 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=1} Honda state: {fibonacci_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:00,038 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2025-03-17 20:35:00,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,040 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) [2025-03-17 20:35:00,040 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 [2025-03-17 20:35:00,041 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,042 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,052 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,053 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:00,058 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2025-03-17 20:35:00,058 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,058 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,060 INFO L229 MonitoredProcess]: Starting monitored process 25 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) [2025-03-17 20:35:00,061 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-03-17 20:35:00,062 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,062 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,073 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,073 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=2} Honda state: {fibonacci_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:00,079 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-03-17 20:35:00,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,081 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) [2025-03-17 20:35:00,082 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 [2025-03-17 20:35:00,083 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,083 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,099 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 [2025-03-17 20:35:00,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,101 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) [2025-03-17 20:35:00,102 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 [2025-03-17 20:35:00,103 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:00,103 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,114 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:00,120 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2025-03-17 20:35:00,120 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:00,120 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:00,120 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:00,120 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:00,120 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:00,120 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,120 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:00,120 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:00,120 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2025-03-17 20:35:00,120 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:00,120 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:00,121 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,123 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,126 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,128 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,162 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:00,162 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:00,162 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,162 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,164 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) [2025-03-17 20:35:00,164 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 [2025-03-17 20:35:00,165 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 [2025-03-17 20:35:00,176 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,176 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,176 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,176 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,176 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,177 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,177 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,178 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:00,184 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 [2025-03-17 20:35:00,184 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,184 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,186 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) [2025-03-17 20:35:00,187 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 [2025-03-17 20:35:00,188 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 [2025-03-17 20:35:00,198 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,198 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,199 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,199 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,199 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,199 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,199 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,200 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:00,206 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 [2025-03-17 20:35:00,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,208 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) [2025-03-17 20:35:00,209 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 [2025-03-17 20:35:00,211 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 [2025-03-17 20:35:00,221 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,221 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,221 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,221 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,221 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,221 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,221 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,222 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:00,229 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:00,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,231 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) [2025-03-17 20:35:00,233 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 [2025-03-17 20:35:00,234 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 [2025-03-17 20:35:00,244 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,244 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,244 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,244 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,244 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,244 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,244 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,246 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:00,252 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:00,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,254 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) [2025-03-17 20:35:00,255 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 [2025-03-17 20:35:00,257 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 [2025-03-17 20:35:00,267 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,267 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,267 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,267 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,267 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,268 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,268 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,271 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:00,274 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:00,274 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-17 20:35:00,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,276 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) [2025-03-17 20:35:00,280 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 [2025-03-17 20:35:00,280 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:00,280 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:00,280 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:00,280 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-03-17 20:35:00,288 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2025-03-17 20:35:00,288 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:00,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,308 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:00,329 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:00,330 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,330 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,331 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,332 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,451 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 [2025-03-17 20:35:00,489 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:35:00,496 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:35:00,496 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,496 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,498 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,499 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,555 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:00,556 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 [2025-03-17 20:35:00,556 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 105 states and 142 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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) [2025-03-17 20:35:00,705 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 105 states and 142 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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 189 states and 264 transitions. Complement of second has 37 states. [2025-03-17 20:35:00,705 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 [2025-03-17 20:35:00,705 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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) [2025-03-17 20:35:00,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 39 transitions. [2025-03-17 20:35:00,706 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 39 transitions. Stem has 31 letters. Loop has 10 letters. [2025-03-17 20:35:00,706 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:00,706 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:00,714 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,723 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:00,743 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:00,743 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,743 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,744 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,745 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,874 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:35:00,881 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:35:00,881 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,881 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,883 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,884 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,940 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:00,941 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 [2025-03-17 20:35:00,941 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 105 states and 142 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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) [2025-03-17 20:35:01,077 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 105 states and 142 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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 295 states and 401 transitions. Complement of second has 29 states. [2025-03-17 20:35:01,078 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 [2025-03-17 20:35:01,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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) [2025-03-17 20:35:01,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 23 transitions. [2025-03-17 20:35:01,078 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 23 transitions. Stem has 31 letters. Loop has 10 letters. [2025-03-17 20:35:01,079 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,079 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:01,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,096 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:01,122 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:01,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:01,124 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-17 20:35:01,125 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:01,252 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-17 20:35:01,258 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-17 20:35:01,258 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,258 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:01,259 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-17 20:35:01,259 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:01,308 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:01,309 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 [2025-03-17 20:35:01,309 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 105 states and 142 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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) [2025-03-17 20:35:01,473 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 105 states and 142 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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 816 states and 1128 transitions. Complement of second has 135 states. [2025-03-17 20:35:01,474 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 [2025-03-17 20:35:01,474 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 5 states have internal predecessors, (18), 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) [2025-03-17 20:35:01,475 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 44 transitions. [2025-03-17 20:35:01,475 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 44 transitions. Stem has 31 letters. Loop has 10 letters. [2025-03-17 20:35:01,475 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,475 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 44 transitions. Stem has 41 letters. Loop has 10 letters. [2025-03-17 20:35:01,475 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,475 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 44 transitions. Stem has 31 letters. Loop has 20 letters. [2025-03-17 20:35:01,476 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,476 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 816 states and 1128 transitions. [2025-03-17 20:35:01,485 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2025-03-17 20:35:01,491 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 816 states to 417 states and 628 transitions. [2025-03-17 20:35:01,492 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 161 [2025-03-17 20:35:01,492 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 181 [2025-03-17 20:35:01,492 INFO L73 IsDeterministic]: Start isDeterministic. Operand 417 states and 628 transitions. [2025-03-17 20:35:01,492 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:01,492 INFO L218 hiAutomatonCegarLoop]: Abstraction has 417 states and 628 transitions. [2025-03-17 20:35:01,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 417 states and 628 transitions. [2025-03-17 20:35:01,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 417 to 355. [2025-03-17 20:35:01,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 355 states, 222 states have (on average 1.1981981981981982) internal successors, (266), 238 states have internal predecessors, (266), 75 states have call successors, (84), 46 states have call predecessors, (84), 58 states have return successors, (142), 70 states have call predecessors, (142), 71 states have call successors, (142) [2025-03-17 20:35:01,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 355 states to 355 states and 492 transitions. [2025-03-17 20:35:01,515 INFO L240 hiAutomatonCegarLoop]: Abstraction has 355 states and 492 transitions. [2025-03-17 20:35:01,515 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:01,515 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-17 20:35:01,515 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2025-03-17 20:35:01,515 INFO L87 Difference]: Start difference. First operand 355 states and 492 transitions. Second operand has 21 states, 18 states have (on average 2.0) internal successors, (36), 14 states have internal predecessors, (36), 11 states have call successors, (11), 7 states have call predecessors, (11), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-17 20:35:01,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:01,759 INFO L93 Difference]: Finished difference Result 644 states and 1006 transitions. [2025-03-17 20:35:01,759 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 644 states and 1006 transitions. [2025-03-17 20:35:01,769 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2025-03-17 20:35:01,783 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 644 states to 613 states and 961 transitions. [2025-03-17 20:35:01,783 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2025-03-17 20:35:01,788 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 285 [2025-03-17 20:35:01,788 INFO L73 IsDeterministic]: Start isDeterministic. Operand 613 states and 961 transitions. [2025-03-17 20:35:01,788 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:01,788 INFO L218 hiAutomatonCegarLoop]: Abstraction has 613 states and 961 transitions. [2025-03-17 20:35:01,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 613 states and 961 transitions. [2025-03-17 20:35:01,821 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 613 to 537. [2025-03-17 20:35:01,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 537 states, 327 states have (on average 1.143730886850153) internal successors, (374), 352 states have internal predecessors, (374), 125 states have call successors, (135), 65 states have call predecessors, (135), 85 states have return successors, (288), 119 states have call predecessors, (288), 115 states have call successors, (288) [2025-03-17 20:35:01,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 537 states to 537 states and 797 transitions. [2025-03-17 20:35:01,828 INFO L240 hiAutomatonCegarLoop]: Abstraction has 537 states and 797 transitions. [2025-03-17 20:35:01,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-17 20:35:01,829 INFO L432 stractBuchiCegarLoop]: Abstraction has 537 states and 797 transitions. [2025-03-17 20:35:01,829 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-17 20:35:01,830 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 537 states and 797 transitions. [2025-03-17 20:35:01,834 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-17 20:35:01,834 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:01,834 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:01,835 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:01,835 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-17 20:35:01,835 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#21#return;" "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-03-17 20:35:01,835 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-03-17 20:35:01,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,835 INFO L85 PathProgramCache]: Analyzing trace with hash 939143040, now seen corresponding path program 1 times [2025-03-17 20:35:01,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,836 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [76743190] [2025-03-17 20:35:01,836 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:01,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,839 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-17 20:35:01,846 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-17 20:35:01,846 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,846 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,118 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-17 20:35:02,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:02,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [76743190] [2025-03-17 20:35:02,119 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [76743190] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:35:02,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [476326731] [2025-03-17 20:35:02,119 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:02,119 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:35:02,119 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,121 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) [2025-03-17 20:35:02,122 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2025-03-17 20:35:02,144 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-17 20:35:02,153 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-17 20:35:02,153 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,153 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,154 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,155 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,208 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-17 20:35:02,209 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 20:35:02,361 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-17 20:35:02,361 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [476326731] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 20:35:02,361 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 20:35:02,361 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 20 [2025-03-17 20:35:02,361 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1121399179] [2025-03-17 20:35:02,361 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 20:35:02,362 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:35:02,362 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,362 INFO L85 PathProgramCache]: Analyzing trace with hash 1168782, now seen corresponding path program 2 times [2025-03-17 20:35:02,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [790192380] [2025-03-17 20:35:02,362 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:02,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,363 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:02,364 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:02,364 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-17 20:35:02,364 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,364 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:02,366 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:02,368 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:02,368 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,368 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,369 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:02,402 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:02,403 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:02,403 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:02,403 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:02,403 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:02,403 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,403 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:02,403 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:02,403 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2025-03-17 20:35:02,403 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:02,403 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:02,404 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,408 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,410 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,411 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,413 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,437 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:02,437 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:02,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,439 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) [2025-03-17 20:35:02,441 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 [2025-03-17 20:35:02,442 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:02,442 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:02,460 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:02,461 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,461 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,463 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) [2025-03-17 20:35:02,464 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 [2025-03-17 20:35:02,465 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:02,465 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:02,509 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:02,514 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:02,514 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:02,514 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:02,514 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:02,514 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:02,514 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:02,514 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,514 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:02,514 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:02,514 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2025-03-17 20:35:02,514 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:02,514 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:02,515 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,518 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,522 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,524 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,525 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,554 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:02,554 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:02,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,556 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) [2025-03-17 20:35:02,558 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 [2025-03-17 20:35:02,563 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 [2025-03-17 20:35:02,575 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:02,575 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:02,575 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:02,575 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:02,575 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:02,576 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:02,576 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:02,581 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:02,588 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 [2025-03-17 20:35:02,588 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,589 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,590 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) [2025-03-17 20:35:02,606 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 [2025-03-17 20:35:02,607 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 [2025-03-17 20:35:02,619 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:02,619 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:02,619 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:02,619 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:02,619 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:02,620 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:02,620 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:02,623 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:02,625 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-17 20:35:02,625 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:02,625 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,625 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,633 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) [2025-03-17 20:35:02,634 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 [2025-03-17 20:35:02,636 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:02,636 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:02,636 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:02,636 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2025-03-17 20:35:02,647 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2025-03-17 20:35:02,648 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:02,659 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,678 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-17 20:35:02,719 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-17 20:35:02,719 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,720 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,722 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,723 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,801 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:02,804 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:02,805 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,805 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,805 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,806 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,826 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:02,827 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 [2025-03-17 20:35:02,827 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 537 states and 797 transitions. cyclomatic complexity: 267 Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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) [2025-03-17 20:35:02,875 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 537 states and 797 transitions. cyclomatic complexity: 267. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 559 states and 819 transitions. Complement of second has 15 states. [2025-03-17 20:35:02,876 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 [2025-03-17 20:35:02,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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) [2025-03-17 20:35:02,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 12 transitions. [2025-03-17 20:35:02,876 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 12 transitions. Stem has 44 letters. Loop has 4 letters. [2025-03-17 20:35:02,877 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,877 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:02,883 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,897 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-17 20:35:02,924 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-17 20:35:02,925 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,925 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,926 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,928 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,005 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 [2025-03-17 20:35:03,028 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:03,031 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:03,031 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,031 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,033 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,033 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,053 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:03,053 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 [2025-03-17 20:35:03,053 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 537 states and 797 transitions. cyclomatic complexity: 267 Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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) [2025-03-17 20:35:03,107 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 537 states and 797 transitions. cyclomatic complexity: 267. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 559 states and 819 transitions. Complement of second has 15 states. [2025-03-17 20:35:03,107 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 [2025-03-17 20:35:03,108 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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) [2025-03-17 20:35:03,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 12 transitions. [2025-03-17 20:35:03,108 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 12 transitions. Stem has 44 letters. Loop has 4 letters. [2025-03-17 20:35:03,108 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,108 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:03,116 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,127 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-17 20:35:03,160 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-17 20:35:03,160 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,160 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,161 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,164 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,241 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:03,245 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:03,245 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,245 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,246 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,246 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,266 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:03,267 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 [2025-03-17 20:35:03,267 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 537 states and 797 transitions. cyclomatic complexity: 267 Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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) [2025-03-17 20:35:03,336 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 537 states and 797 transitions. cyclomatic complexity: 267. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 722 states and 985 transitions. Complement of second has 19 states. [2025-03-17 20:35:03,337 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 [2025-03-17 20:35:03,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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) [2025-03-17 20:35:03,338 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 20 transitions. [2025-03-17 20:35:03,338 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 44 letters. Loop has 4 letters. [2025-03-17 20:35:03,338 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,338 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 48 letters. Loop has 4 letters. [2025-03-17 20:35:03,339 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,339 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 44 letters. Loop has 8 letters. [2025-03-17 20:35:03,339 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,339 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 722 states and 985 transitions. [2025-03-17 20:35:03,346 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-17 20:35:03,352 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 722 states to 577 states and 838 transitions. [2025-03-17 20:35:03,352 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 210 [2025-03-17 20:35:03,352 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 216 [2025-03-17 20:35:03,352 INFO L73 IsDeterministic]: Start isDeterministic. Operand 577 states and 838 transitions. [2025-03-17 20:35:03,352 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:03,352 INFO L218 hiAutomatonCegarLoop]: Abstraction has 577 states and 838 transitions. [2025-03-17 20:35:03,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 577 states and 838 transitions. [2025-03-17 20:35:03,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 577 to 567. [2025-03-17 20:35:03,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 567 states, 354 states have (on average 1.1327683615819208) internal successors, (401), 382 states have internal predecessors, (401), 125 states have call successors, (135), 65 states have call predecessors, (135), 88 states have return successors, (288), 119 states have call predecessors, (288), 115 states have call successors, (288) [2025-03-17 20:35:03,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 567 states to 567 states and 824 transitions. [2025-03-17 20:35:03,366 INFO L240 hiAutomatonCegarLoop]: Abstraction has 567 states and 824 transitions. [2025-03-17 20:35:03,367 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:03,367 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-17 20:35:03,367 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=292, Unknown=0, NotChecked=0, Total=380 [2025-03-17 20:35:03,367 INFO L87 Difference]: Start difference. First operand 567 states and 824 transitions. Second operand has 20 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 12 states have internal predecessors, (32), 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) [2025-03-17 20:35:03,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:03,628 INFO L93 Difference]: Finished difference Result 684 states and 1025 transitions. [2025-03-17 20:35:03,628 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 684 states and 1025 transitions. [2025-03-17 20:35:03,635 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-17 20:35:03,642 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 684 states to 663 states and 993 transitions. [2025-03-17 20:35:03,642 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 247 [2025-03-17 20:35:03,642 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2025-03-17 20:35:03,642 INFO L73 IsDeterministic]: Start isDeterministic. Operand 663 states and 993 transitions. [2025-03-17 20:35:03,643 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:03,643 INFO L218 hiAutomatonCegarLoop]: Abstraction has 663 states and 993 transitions. [2025-03-17 20:35:03,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 663 states and 993 transitions. [2025-03-17 20:35:03,657 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 663 to 609. [2025-03-17 20:35:03,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 609 states, 384 states have (on average 1.1276041666666667) internal successors, (433), 412 states have internal predecessors, (433), 137 states have call successors, (149), 75 states have call predecessors, (149), 88 states have return successors, (269), 121 states have call predecessors, (269), 127 states have call successors, (269) [2025-03-17 20:35:03,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 609 states to 609 states and 851 transitions. [2025-03-17 20:35:03,664 INFO L240 hiAutomatonCegarLoop]: Abstraction has 609 states and 851 transitions. [2025-03-17 20:35:03,666 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-17 20:35:03,666 INFO L432 stractBuchiCegarLoop]: Abstraction has 609 states and 851 transitions. [2025-03-17 20:35:03,666 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-17 20:35:03,667 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 609 states and 851 transitions. [2025-03-17 20:35:03,670 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-17 20:35:03,671 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:03,671 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:03,671 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:03,671 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-17 20:35:03,672 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#21#return;" "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" [2025-03-17 20:35:03,672 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" [2025-03-17 20:35:03,672 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,672 INFO L85 PathProgramCache]: Analyzing trace with hash -1680572934, now seen corresponding path program 2 times [2025-03-17 20:35:03,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:03,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [681399889] [2025-03-17 20:35:03,673 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:03,673 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:03,677 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 51 statements into 2 equivalence classes. [2025-03-17 20:35:03,684 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 51 of 51 statements. [2025-03-17 20:35:03,685 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:03,685 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,926 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-17 20:35:03,926 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:03,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [681399889] [2025-03-17 20:35:03,926 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [681399889] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:35:03,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [76016763] [2025-03-17 20:35:03,926 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:03,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:35:03,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,929 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 20:35:03,930 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Waiting until timeout for monitored process [2025-03-17 20:35:03,950 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 51 statements into 2 equivalence classes. [2025-03-17 20:35:03,960 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 51 of 51 statements. [2025-03-17 20:35:03,960 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:03,960 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,961 INFO L256 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,962 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,005 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-17 20:35:04,006 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 20:35:04,175 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-17 20:35:04,175 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [76016763] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 20:35:04,175 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 20:35:04,175 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2025-03-17 20:35:04,175 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1292982702] [2025-03-17 20:35:04,175 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 20:35:04,175 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:35:04,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:04,176 INFO L85 PathProgramCache]: Analyzing trace with hash 1527252, now seen corresponding path program 3 times [2025-03-17 20:35:04,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:04,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [201550008] [2025-03-17 20:35:04,176 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:04,176 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:04,178 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:04,178 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:04,178 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2025-03-17 20:35:04,178 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:04,178 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:04,179 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:04,179 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:04,179 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,179 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:04,180 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:04,220 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:04,220 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:04,220 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:04,220 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:04,220 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:04,220 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,220 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:04,220 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:04,220 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2025-03-17 20:35:04,220 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:04,220 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:04,221 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,222 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,223 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,229 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,255 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:04,255 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:04,256 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,258 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) [2025-03-17 20:35:04,259 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 [2025-03-17 20:35:04,260 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:04,260 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:04,272 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:04,272 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:04,278 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:04,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,280 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) [2025-03-17 20:35:04,281 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 [2025-03-17 20:35:04,283 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:04,283 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:04,295 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:04,296 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:04,301 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 [2025-03-17 20:35:04,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,304 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 20:35:04,305 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2025-03-17 20:35:04,307 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:04,307 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:04,331 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2025-03-17 20:35:04,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,333 INFO L229 MonitoredProcess]: Starting monitored process 44 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) [2025-03-17 20:35:04,335 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2025-03-17 20:35:04,336 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:04,336 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:04,482 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:04,488 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Ended with exit code 0 [2025-03-17 20:35:04,489 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:04,489 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:04,489 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:04,489 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:04,489 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:04,489 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,489 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:04,489 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:04,489 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2025-03-17 20:35:04,489 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:04,489 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:04,490 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,493 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,499 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,503 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,526 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:04,526 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:04,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,529 INFO L229 MonitoredProcess]: Starting monitored process 45 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) [2025-03-17 20:35:04,530 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2025-03-17 20:35:04,530 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 [2025-03-17 20:35:04,540 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:04,540 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:04,540 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:04,540 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:04,540 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:04,540 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:04,540 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:04,541 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:04,547 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Ended with exit code 0 [2025-03-17 20:35:04,547 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,549 INFO L229 MonitoredProcess]: Starting monitored process 46 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) [2025-03-17 20:35:04,551 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Waiting until timeout for monitored process [2025-03-17 20:35:04,552 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 [2025-03-17 20:35:04,562 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:04,562 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:04,562 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:04,562 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:04,562 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:04,563 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:04,563 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:04,565 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:04,566 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-17 20:35:04,566 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:04,566 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,566 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,569 INFO L229 MonitoredProcess]: Starting monitored process 47 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) [2025-03-17 20:35:04,570 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2025-03-17 20:35:04,571 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:04,571 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:04,571 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:04,571 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-03-17 20:35:04,577 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:04,577 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:04,587 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:04,599 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-03-17 20:35:04,632 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-03-17 20:35:04,632 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,632 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,634 INFO L256 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,635 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,725 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2025-03-17 20:35:04,725 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:04,728 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:04,728 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,728 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,729 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,729 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,753 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:04,754 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 [2025-03-17 20:35:04,754 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 609 states and 851 transitions. cyclomatic complexity: 249 Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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) [2025-03-17 20:35:04,793 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 609 states and 851 transitions. cyclomatic complexity: 249. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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 631 states and 874 transitions. Complement of second has 18 states. [2025-03-17 20:35:04,794 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 [2025-03-17 20:35:04,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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) [2025-03-17 20:35:04,795 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 20:35:04,795 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 51 letters. Loop has 4 letters. [2025-03-17 20:35:04,795 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:04,795 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:04,802 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:04,814 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-03-17 20:35:04,847 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-03-17 20:35:04,847 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,847 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,848 INFO L256 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,850 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,927 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-17 20:35:04,930 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-17 20:35:04,931 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,931 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,935 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,935 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,961 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:04,961 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 [2025-03-17 20:35:04,961 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 609 states and 851 transitions. cyclomatic complexity: 249 Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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) [2025-03-17 20:35:05,024 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 609 states and 851 transitions. cyclomatic complexity: 249. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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 851 states and 1191 transitions. Complement of second has 22 states. [2025-03-17 20:35:05,026 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 [2025-03-17 20:35:05,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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) [2025-03-17 20:35:05,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 14 transitions. [2025-03-17 20:35:05,027 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 14 transitions. Stem has 51 letters. Loop has 4 letters. [2025-03-17 20:35:05,027 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,027 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 14 transitions. Stem has 55 letters. Loop has 4 letters. [2025-03-17 20:35:05,027 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,027 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 14 transitions. Stem has 51 letters. Loop has 8 letters. [2025-03-17 20:35:05,027 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,027 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 851 states and 1191 transitions. [2025-03-17 20:35:05,036 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-17 20:35:05,045 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 851 states to 781 states and 1113 transitions. [2025-03-17 20:35:05,046 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 256 [2025-03-17 20:35:05,046 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 284 [2025-03-17 20:35:05,047 INFO L73 IsDeterministic]: Start isDeterministic. Operand 781 states and 1113 transitions. [2025-03-17 20:35:05,047 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:05,047 INFO L218 hiAutomatonCegarLoop]: Abstraction has 781 states and 1113 transitions. [2025-03-17 20:35:05,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 781 states and 1113 transitions. [2025-03-17 20:35:05,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 781 to 761. [2025-03-17 20:35:05,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 761 states, 484 states have (on average 1.1177685950413223) internal successors, (541), 519 states have internal predecessors, (541), 170 states have call successors, (200), 100 states have call predecessors, (200), 107 states have return successors, (348), 141 states have call predecessors, (348), 160 states have call successors, (348) [2025-03-17 20:35:05,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 761 states to 761 states and 1089 transitions. [2025-03-17 20:35:05,068 INFO L240 hiAutomatonCegarLoop]: Abstraction has 761 states and 1089 transitions. [2025-03-17 20:35:05,068 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:05,069 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-17 20:35:05,069 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2025-03-17 20:35:05,069 INFO L87 Difference]: Start difference. First operand 761 states and 1089 transitions. Second operand has 21 states, 20 states have (on average 1.7) internal successors, (34), 12 states have internal predecessors, (34), 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) [2025-03-17 20:35:05,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:05,321 INFO L93 Difference]: Finished difference Result 455 states and 538 transitions. [2025-03-17 20:35:05,322 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 455 states and 538 transitions. [2025-03-17 20:35:05,326 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:05,326 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 455 states to 0 states and 0 transitions. [2025-03-17 20:35:05,327 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 20:35:05,327 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 20:35:05,327 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 20:35:05,327 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 20:35:05,327 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:05,327 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:05,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-17 20:35:05,329 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:05,329 INFO L338 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2025-03-17 20:35:05,330 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-17 20:35:05,330 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:05,330 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-17 20:35:05,343 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.03 08:35:05 BoogieIcfgContainer [2025-03-17 20:35:05,344 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-17 20:35:05,344 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-17 20:35:05,344 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-17 20:35:05,344 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-17 20:35:05,345 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:34:56" (3/4) ... [2025-03-17 20:35:05,347 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-17 20:35:05,347 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-17 20:35:05,348 INFO L158 Benchmark]: Toolchain (without parser) took 8825.42ms. Allocated memory is still 167.8MB. Free memory was 129.9MB in the beginning and 60.0MB in the end (delta: 69.9MB). Peak memory consumption was 68.3MB. Max. memory is 16.1GB. [2025-03-17 20:35:05,348 INFO L158 Benchmark]: CDTParser took 0.31ms. Allocated memory is still 201.3MB. Free memory is still 126.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:05,349 INFO L158 Benchmark]: CACSL2BoogieTranslator took 186.99ms. Allocated memory is still 167.8MB. Free memory was 129.9MB in the beginning and 119.5MB in the end (delta: 10.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 20:35:05,350 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.02ms. Allocated memory is still 167.8MB. Free memory was 119.5MB in the beginning and 118.6MB in the end (delta: 965.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:05,350 INFO L158 Benchmark]: Boogie Preprocessor took 24.53ms. Allocated memory is still 167.8MB. Free memory was 118.6MB in the beginning and 117.6MB in the end (delta: 939.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:05,350 INFO L158 Benchmark]: IcfgBuilder took 179.15ms. Allocated memory is still 167.8MB. Free memory was 117.6MB in the beginning and 107.2MB in the end (delta: 10.5MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-17 20:35:05,350 INFO L158 Benchmark]: BuchiAutomizer took 8405.14ms. Allocated memory is still 167.8MB. Free memory was 107.2MB in the beginning and 60.0MB in the end (delta: 47.1MB). Peak memory consumption was 43.1MB. Max. memory is 16.1GB. [2025-03-17 20:35:05,350 INFO L158 Benchmark]: Witness Printer took 2.96ms. Allocated memory is still 167.8MB. Free memory was 60.0MB in the beginning and 60.0MB in the end (delta: 30.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:05,351 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.31ms. Allocated memory is still 201.3MB. Free memory is still 126.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 186.99ms. Allocated memory is still 167.8MB. Free memory was 129.9MB in the beginning and 119.5MB in the end (delta: 10.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.02ms. Allocated memory is still 167.8MB. Free memory was 119.5MB in the beginning and 118.6MB in the end (delta: 965.6kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 24.53ms. Allocated memory is still 167.8MB. Free memory was 118.6MB in the beginning and 117.6MB in the end (delta: 939.1kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 179.15ms. Allocated memory is still 167.8MB. Free memory was 117.6MB in the beginning and 107.2MB in the end (delta: 10.5MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * BuchiAutomizer took 8405.14ms. Allocated memory is still 167.8MB. Free memory was 107.2MB in the beginning and 60.0MB in the end (delta: 47.1MB). Peak memory consumption was 43.1MB. Max. memory is 16.1GB. * Witness Printer took 2.96ms. Allocated memory is still 167.8MB. Free memory was 60.0MB in the beginning and 60.0MB in the end (delta: 30.1kB). 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 10 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 21 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.3s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 4.0s. Construction of modules took 0.8s. Büchi inclusion checks took 3.2s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 244 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: 0/6 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 506 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 482 mSDsluCounter, 605 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 391 mSDsCounter, 301 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1409 IncrementalHoareTripleChecker+Invalid, 1710 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 301 mSolverCounterUnsat, 214 mSDtfsCounter, 1409 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: 33ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 11 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.5s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-17 20:35:05,366 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:05,567 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:05,768 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:05,968 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:06,169 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