./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 c00e63dc Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive/Fibonacci02.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/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-?-c00e63d-m [2025-02-06 19:47:47,646 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-06 19:47:47,709 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-02-06 19:47:47,712 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-06 19:47:47,715 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-06 19:47:47,715 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-02-06 19:47:47,735 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-06 19:47:47,735 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-06 19:47:47,736 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-06 19:47:47,736 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-06 19:47:47,737 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-06 19:47:47,737 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-06 19:47:47,737 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-06 19:47:47,737 INFO L153 SettingsManager]: * Use SBE=true [2025-02-06 19:47:47,737 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Use old map elimination=false [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-02-06 19:47:47,738 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-06 19:47:47,738 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-06 19:47:47,739 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-02-06 19:47:47,740 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-06 19:47:47,740 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-06 19:47:47,740 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-06 19:47:47,740 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-06 19:47:47,740 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-06 19:47:47,740 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-06 19:47:47,740 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-02-06 19:47:47,740 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-jdk21/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-02-06 19:47:47,973 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-06 19:47:47,985 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-06 19:47:47,987 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-06 19:47:47,989 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-06 19:47:47,989 INFO L274 PluginConnector]: CDTParser initialized [2025-02-06 19:47:47,990 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci02.c [2025-02-06 19:47:49,182 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/e29505e74/dcf9316cca8b4403969065faf59bfa26/FLAGc65174a15 [2025-02-06 19:47:49,389 INFO L384 CDTParser]: Found 1 translation units. [2025-02-06 19:47:49,391 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2025-02-06 19:47:49,407 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/e29505e74/dcf9316cca8b4403969065faf59bfa26/FLAGc65174a15 [2025-02-06 19:47:49,429 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/e29505e74/dcf9316cca8b4403969065faf59bfa26 [2025-02-06 19:47:49,431 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-06 19:47:49,431 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-06 19:47:49,432 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-06 19:47:49,437 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-06 19:47:49,441 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-06 19:47:49,445 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,446 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7a8cc25d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49, skipping insertion in model container [2025-02-06 19:47:49,446 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,469 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-06 19:47:49,584 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-06 19:47:49,593 INFO L200 MainTranslator]: Completed pre-run [2025-02-06 19:47:49,601 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-06 19:47:49,612 INFO L204 MainTranslator]: Completed translation [2025-02-06 19:47:49,613 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49 WrapperNode [2025-02-06 19:47:49,613 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-06 19:47:49,614 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-06 19:47:49,614 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-06 19:47:49,614 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-06 19:47:49,618 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,624 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,633 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2025-02-06 19:47:49,633 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-06 19:47:49,634 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-06 19:47:49,634 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-06 19:47:49,635 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-06 19:47:49,639 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,639 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,641 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,647 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-02-06 19:47:49,648 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,648 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,650 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,653 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,654 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,654 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,655 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-06 19:47:49,656 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-06 19:47:49,656 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-06 19:47:49,656 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-06 19:47:49,658 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (1/1) ... [2025-02-06 19:47:49,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:49,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:49,691 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:49,696 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2025-02-06 19:47:49,713 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-02-06 19:47:49,713 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-02-06 19:47:49,713 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-06 19:47:49,713 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-06 19:47:49,713 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-06 19:47:49,714 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-06 19:47:49,753 INFO L257 CfgBuilder]: Building ICFG [2025-02-06 19:47:49,754 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-06 19:47:49,796 INFO L1309 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-02-06 19:47:49,826 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-02-06 19:47:49,827 INFO L308 CfgBuilder]: Performing block encoding [2025-02-06 19:47:49,833 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-06 19:47:49,833 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-06 19:47:49,833 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 07:47:49 BoogieIcfgContainer [2025-02-06 19:47:49,833 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-06 19:47:49,836 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-02-06 19:47:49,836 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-02-06 19:47:49,840 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-02-06 19:47:49,840 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-02-06 19:47:49,841 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 06.02 07:47:49" (1/3) ... [2025-02-06 19:47:49,841 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@14147205 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 06.02 07:47:49, skipping insertion in model container [2025-02-06 19:47:49,841 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-02-06 19:47:49,842 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.02 07:47:49" (2/3) ... [2025-02-06 19:47:49,842 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@14147205 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 06.02 07:47:49, skipping insertion in model container [2025-02-06 19:47:49,842 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-02-06 19:47:49,843 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 07:47:49" (3/3) ... [2025-02-06 19:47:49,844 INFO L363 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2025-02-06 19:47:49,880 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-02-06 19:47:49,880 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-02-06 19:47:49,881 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-02-06 19:47:49,881 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-02-06 19:47:49,881 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-02-06 19:47:49,881 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-02-06 19:47:49,881 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-02-06 19:47:49,881 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-02-06 19:47:49,885 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-06 19:47:49,897 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-02-06 19:47:49,897 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:49,897 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:49,900 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-02-06 19:47:49,900 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-02-06 19:47:49,900 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-02-06 19:47:49,901 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-06 19:47:49,903 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-02-06 19:47:49,903 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:49,903 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:49,904 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-02-06 19:47:49,904 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-02-06 19:47:49,907 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-02-06 19:47:49,907 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-02-06 19:47:49,912 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:49,912 INFO L85 PathProgramCache]: Analyzing trace with hash 48633, now seen corresponding path program 1 times [2025-02-06 19:47:49,917 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:49,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [816812045] [2025-02-06 19:47:49,919 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:49,919 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:49,967 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-06 19:47:49,979 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-06 19:47:49,979 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:49,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:49,980 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:49,984 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-06 19:47:49,988 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-06 19:47:49,988 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:49,988 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:50,001 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:50,003 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:50,004 INFO L85 PathProgramCache]: Analyzing trace with hash 1168785, now seen corresponding path program 1 times [2025-02-06 19:47:50,004 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:50,004 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1771379430] [2025-02-06 19:47:50,004 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:50,004 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:50,007 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:50,010 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:50,011 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,011 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:50,011 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:50,012 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:50,014 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:50,014 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,014 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:50,015 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:50,018 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:50,018 INFO L85 PathProgramCache]: Analyzing trace with hash 1964169097, now seen corresponding path program 1 times [2025-02-06 19:47:50,018 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:50,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [612110362] [2025-02-06 19:47:50,018 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:50,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:50,023 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-02-06 19:47:50,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-02-06 19:47:50,030 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:50,031 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:50,032 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-02-06 19:47:50,037 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-02-06 19:47:50,040 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,041 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:50,042 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:50,143 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:50,144 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:50,144 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:50,144 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:50,145 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-06 19:47:50,145 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,145 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:50,145 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:50,145 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2025-02-06 19:47:50,145 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:50,145 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:50,155 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,163 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,167 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,170 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,176 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,235 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:50,235 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-06 19:47:50,236 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,245 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,249 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2025-02-06 19:47:50,250 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:50,250 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:50,266 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:50,266 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-06 19:47:50,272 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2025-02-06 19:47:50,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,275 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,277 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,278 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2025-02-06 19:47:50,280 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:50,280 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:50,292 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:50,293 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-02-06 19:47:50,300 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:50,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,302 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,314 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2025-02-06 19:47:50,314 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:50,314 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:50,326 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:50,326 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-02-06 19:47:50,332 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:50,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,335 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,336 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2025-02-06 19:47:50,337 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:50,337 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:50,351 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:50,351 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-06 19:47:50,359 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2025-02-06 19:47:50,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,360 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,362 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,363 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2025-02-06 19:47:50,364 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:50,364 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:50,391 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2025-02-06 19:47:50,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,394 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,395 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-02-06 19:47:50,396 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-06 19:47:50,397 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:50,462 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-06 19:47:50,467 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-02-06 19:47:50,467 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:50,467 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:50,467 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:50,467 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:50,467 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-06 19:47:50,467 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,467 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:50,467 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:50,467 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2025-02-06 19:47:50,467 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:50,467 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:50,469 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,472 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,474 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,477 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,480 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:50,537 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:50,539 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-06 19:47:50,540 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,540 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,542 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,544 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2025-02-06 19:47:50,545 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-02-06 19:47:50,555 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:50,556 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:50,556 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:50,556 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:50,556 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:50,559 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:50,559 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:50,561 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:50,567 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:50,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,568 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,569 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,570 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2025-02-06 19:47:50,572 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-02-06 19:47:50,582 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:50,582 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:50,582 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:50,582 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:50,582 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:50,583 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:50,583 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:50,584 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:50,590 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:50,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,591 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,592 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,593 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2025-02-06 19:47:50,595 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-02-06 19:47:50,605 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:50,605 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:50,605 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:50,606 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:50,606 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:50,606 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:50,606 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:50,607 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:50,613 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:50,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,615 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,617 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2025-02-06 19:47:50,617 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-02-06 19:47:50,627 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:50,627 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:50,628 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:50,628 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:50,628 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:50,628 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:50,628 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:50,630 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:50,635 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2025-02-06 19:47:50,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,637 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,638 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-02-06 19:47:50,639 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-02-06 19:47:50,649 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:50,649 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:50,649 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:50,649 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:50,649 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:50,650 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:50,650 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:50,661 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-06 19:47:50,664 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-06 19:47:50,666 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-02-06 19:47:50,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:50,668 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:50,669 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:50,671 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2025-02-06 19:47:50,672 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-06 19:47:50,672 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-06 19:47:50,672 INFO L474 LassoAnalysis]: Proved termination. [2025-02-06 19:47:50,673 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2025-02-06 19:47:50,678 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2025-02-06 19:47:50,681 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-06 19:47:50,698 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:50,721 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-06 19:47:50,735 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-06 19:47:50,735 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,735 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:50,737 INFO L256 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-06 19:47:50,738 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:50,751 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:50,757 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:50,757 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,757 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:50,758 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-06 19:47:50,759 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:50,801 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:50,817 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-02-06 19:47:50,819 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-06 19:47:50,844 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2025-02-06 19:47:50,910 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 40 states and 53 transitions. Complement of second has 16 states. [2025-02-06 19:47:50,913 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-02-06 19:47:50,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-06 19:47:50,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2025-02-06 19:47:50,921 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2025-02-06 19:47:50,922 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:50,922 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2025-02-06 19:47:50,922 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:50,922 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2025-02-06 19:47:50,922 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:50,923 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2025-02-06 19:47:50,925 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-02-06 19:47:50,928 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2025-02-06 19:47:50,929 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2025-02-06 19:47:50,929 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2025-02-06 19:47:50,929 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2025-02-06 19:47:50,930 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:50,930 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2025-02-06 19:47:50,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2025-02-06 19:47:50,945 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2025-02-06 19:47:50,945 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:50,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2025-02-06 19:47:50,946 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-02-06 19:47:50,946 INFO L432 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-02-06 19:47:50,946 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-02-06 19:47:50,947 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2025-02-06 19:47:50,947 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-02-06 19:47:50,947 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:50,947 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:50,948 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:50,948 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:50,948 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;" >"#24#return;" [2025-02-06 19:47:50,948 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;" >"#24#return;" [2025-02-06 19:47:50,949 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:50,949 INFO L85 PathProgramCache]: Analyzing trace with hash 2036174640, now seen corresponding path program 1 times [2025-02-06 19:47:50,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:50,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754930255] [2025-02-06 19:47:50,949 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:50,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:50,952 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-02-06 19:47:50,956 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-02-06 19:47:50,956 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:50,956 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:51,015 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-02-06 19:47:51,016 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 19:47:51,016 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754930255] [2025-02-06 19:47:51,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [754930255] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 19:47:51,016 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 19:47:51,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-06 19:47:51,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1634054438] [2025-02-06 19:47:51,017 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 19:47:51,018 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-02-06 19:47:51,018 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:51,018 INFO L85 PathProgramCache]: Analyzing trace with hash -624925077, now seen corresponding path program 1 times [2025-02-06 19:47:51,018 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:51,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1119250829] [2025-02-06 19:47:51,018 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:51,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:51,020 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-06 19:47:51,023 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-06 19:47:51,023 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,023 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:51,055 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-02-06 19:47:51,056 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 19:47:51,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1119250829] [2025-02-06 19:47:51,056 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1119250829] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-06 19:47:51,056 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-06 19:47:51,056 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-06 19:47:51,056 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [668307999] [2025-02-06 19:47:51,056 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-06 19:47:51,056 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-02-06 19:47:51,056 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 19:47:51,057 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-06 19:47:51,057 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-02-06 19:47:51,058 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:51,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 19:47:51,111 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2025-02-06 19:47:51,111 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2025-02-06 19:47:51,112 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-02-06 19:47:51,113 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2025-02-06 19:47:51,113 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2025-02-06 19:47:51,113 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2025-02-06 19:47:51,113 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2025-02-06 19:47:51,113 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:51,113 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-02-06 19:47:51,113 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2025-02-06 19:47:51,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2025-02-06 19:47:51,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2025-02-06 19:47:51,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2025-02-06 19:47:51,115 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-02-06 19:47:51,115 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-02-06 19:47:51,116 INFO L432 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-02-06 19:47:51,116 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-02-06 19:47:51,116 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2025-02-06 19:47:51,116 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-02-06 19:47:51,116 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:51,116 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:51,116 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:51,116 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:51,117 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;" >"#24#return;" [2025-02-06 19:47:51,117 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;" >"#24#return;" [2025-02-06 19:47:51,117 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:51,117 INFO L85 PathProgramCache]: Analyzing trace with hash -1302895192, now seen corresponding path program 1 times [2025-02-06 19:47:51,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:51,117 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [159486964] [2025-02-06 19:47:51,117 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:51,117 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:51,120 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-06 19:47:51,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-06 19:47:51,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:51,172 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:51,173 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 19:47:51,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [159486964] [2025-02-06 19:47:51,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [159486964] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 19:47:51,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [786393813] [2025-02-06 19:47:51,173 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:51,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 19:47:51,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,175 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,177 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-02-06 19:47:51,194 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-06 19:47:51,199 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-06 19:47:51,199 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:51,201 INFO L256 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-06 19:47:51,202 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:51,219 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:51,219 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 19:47:51,292 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:51,292 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [786393813] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 19:47:51,292 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 19:47:51,292 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2025-02-06 19:47:51,293 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [646934970] [2025-02-06 19:47:51,293 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 19:47:51,293 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-02-06 19:47:51,293 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:51,293 INFO L85 PathProgramCache]: Analyzing trace with hash 2102359501, now seen corresponding path program 1 times [2025-02-06 19:47:51,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:51,293 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [855219452] [2025-02-06 19:47:51,293 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:51,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:51,296 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:51,298 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:51,298 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,298 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:51,298 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:51,299 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:51,301 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:51,301 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,301 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:51,302 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:51,384 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:51,384 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:51,384 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:51,384 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:51,384 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-06 19:47:51,384 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,384 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:51,384 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:51,384 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2025-02-06 19:47:51,384 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:51,384 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:51,385 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,387 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,391 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,393 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,395 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,423 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:51,423 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-06 19:47:51,424 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,424 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,425 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,427 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2025-02-06 19:47:51,428 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:51,428 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:51,440 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:51,440 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-02-06 19:47:51,446 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:51,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,448 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,450 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2025-02-06 19:47:51,451 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:51,451 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:51,469 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2025-02-06 19:47:51,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,471 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,473 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2025-02-06 19:47:51,473 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-06 19:47:51,473 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:51,486 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-06 19:47:51,492 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:51,493 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:51,493 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:51,493 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:51,493 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:51,493 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-06 19:47:51,493 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,493 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:51,493 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:51,493 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2025-02-06 19:47:51,493 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:51,493 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:51,494 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,496 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,500 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,501 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,504 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:51,533 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:51,533 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-06 19:47:51,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,534 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,539 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,540 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-02-06 19:47:51,541 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-02-06 19:47:51,551 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:51,551 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:51,551 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:51,551 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:51,551 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:51,552 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:51,552 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:51,553 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:51,558 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-02-06 19:47:51,559 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,559 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,560 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,561 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2025-02-06 19:47:51,568 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-02-06 19:47:51,578 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:51,578 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:51,579 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:51,579 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:51,579 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:51,580 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:51,580 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:51,581 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-06 19:47:51,584 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-06 19:47:51,584 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-02-06 19:47:51,584 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:51,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:51,586 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:51,587 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2025-02-06 19:47:51,588 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-06 19:47:51,588 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-06 19:47:51,588 INFO L474 LassoAnalysis]: Proved termination. [2025-02-06 19:47:51,588 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-02-06 19:47:51,598 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2025-02-06 19:47:51,598 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-06 19:47:51,608 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:51,613 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-06 19:47:51,624 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-06 19:47:51,624 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,624 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:51,625 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-06 19:47:51,626 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:51,675 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:51,706 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:51,712 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:51,712 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:51,712 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:51,713 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-06 19:47:51,714 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:51,786 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:51,787 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-02-06 19:47:51,787 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 19:47:51,943 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 128 states and 178 transitions. Complement of second has 40 states. [2025-02-06 19:47:51,944 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-02-06 19:47:51,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-06 19:47:51,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2025-02-06 19:47:51,945 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2025-02-06 19:47:51,945 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:51,945 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2025-02-06 19:47:51,946 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:51,946 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2025-02-06 19:47:51,946 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:51,946 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2025-02-06 19:47:51,950 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-02-06 19:47:51,953 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2025-02-06 19:47:51,953 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2025-02-06 19:47:51,953 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2025-02-06 19:47:51,953 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2025-02-06 19:47:51,953 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:51,954 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2025-02-06 19:47:51,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2025-02-06 19:47:51,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2025-02-06 19:47:51,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (35), 18 states have call predecessors, (35), 19 states have call successors, (35) [2025-02-06 19:47:51,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2025-02-06 19:47:51,961 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2025-02-06 19:47:51,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 19:47:51,962 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-02-06 19:47:51,962 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-02-06 19:47:51,962 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 11 states, 8 states have (on average 2.0) internal successors, (16), 8 states have internal predecessors, (16), 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-02-06 19:47:52,056 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 19:47:52,057 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2025-02-06 19:47:52,057 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2025-02-06 19:47:52,060 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-02-06 19:47:52,064 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2025-02-06 19:47:52,064 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2025-02-06 19:47:52,065 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2025-02-06 19:47:52,065 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2025-02-06 19:47:52,065 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:52,065 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2025-02-06 19:47:52,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2025-02-06 19:47:52,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2025-02-06 19:47:52,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (39), 20 states have call predecessors, (39), 22 states have call successors, (39) [2025-02-06 19:47:52,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2025-02-06 19:47:52,072 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2025-02-06 19:47:52,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-02-06 19:47:52,073 INFO L432 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2025-02-06 19:47:52,073 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-02-06 19:47:52,073 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2025-02-06 19:47:52,074 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-02-06 19:47:52,074 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:52,074 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:52,075 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:52,075 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:52,075 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;" >"#24#return;" "call #t~ret5 := fibonacci(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#22#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#24#return;" [2025-02-06 19:47:52,075 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;" >"#24#return;" [2025-02-06 19:47:52,075 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:52,076 INFO L85 PathProgramCache]: Analyzing trace with hash -1833162896, now seen corresponding path program 1 times [2025-02-06 19:47:52,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:52,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1620077653] [2025-02-06 19:47:52,076 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:52,076 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:52,079 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 19:47:52,087 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 19:47:52,087 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:52,087 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:52,210 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-02-06 19:47:52,210 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 19:47:52,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1620077653] [2025-02-06 19:47:52,210 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1620077653] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 19:47:52,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119314741] [2025-02-06 19:47:52,210 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:52,211 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 19:47:52,211 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,212 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,213 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-02-06 19:47:52,237 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 19:47:52,245 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 19:47:52,245 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:52,245 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:52,246 INFO L256 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-06 19:47:52,247 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:52,281 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-02-06 19:47:52,281 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 19:47:52,497 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-02-06 19:47:52,497 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [119314741] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 19:47:52,497 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 19:47:52,497 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 12] total 20 [2025-02-06 19:47:52,497 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [323869019] [2025-02-06 19:47:52,497 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 19:47:52,498 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-02-06 19:47:52,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:52,498 INFO L85 PathProgramCache]: Analyzing trace with hash 2102359501, now seen corresponding path program 2 times [2025-02-06 19:47:52,498 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:52,498 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [999283056] [2025-02-06 19:47:52,498 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 19:47:52,498 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:52,502 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 10 statements into 2 equivalence classes. [2025-02-06 19:47:52,504 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:52,504 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 19:47:52,504 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:52,504 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:52,505 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:52,506 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:52,506 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:52,506 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:52,507 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:52,577 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:52,577 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:52,578 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:52,578 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:52,578 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-06 19:47:52,578 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,578 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:52,578 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:52,578 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2025-02-06 19:47:52,578 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:52,578 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:52,579 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,580 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,582 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,584 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,586 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,621 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:52,621 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-06 19:47:52,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,626 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2025-02-06 19:47:52,637 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:52,637 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:52,651 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:52,651 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-06 19:47:52,659 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2025-02-06 19:47:52,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,667 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,668 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2025-02-06 19:47:52,669 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:52,669 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:52,681 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:52,681 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-02-06 19:47:52,690 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2025-02-06 19:47:52,690 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,695 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,696 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2025-02-06 19:47:52,697 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:52,697 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:52,711 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:52,711 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-02-06 19:47:52,719 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2025-02-06 19:47:52,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,721 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-02-06 19:47:52,726 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:52,726 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:52,738 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:52,738 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-02-06 19:47:52,746 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-02-06 19:47:52,746 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,746 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,748 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,749 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-02-06 19:47:52,751 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:52,751 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:52,767 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2025-02-06 19:47:52,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,769 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,771 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2025-02-06 19:47:52,772 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-06 19:47:52,772 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:52,785 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-06 19:47:52,790 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:52,791 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:52,791 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:52,791 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:52,791 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:52,791 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-06 19:47:52,791 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,791 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:52,791 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:52,791 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2025-02-06 19:47:52,791 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:52,791 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:52,792 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,798 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,799 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,800 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,802 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:52,830 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:52,831 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-06 19:47:52,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,833 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,834 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2025-02-06 19:47:52,835 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-02-06 19:47:52,845 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:52,845 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:52,845 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:52,845 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:52,845 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:52,847 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:52,847 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:52,849 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:52,855 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:52,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,861 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,864 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2025-02-06 19:47:52,864 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-02-06 19:47:52,874 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:52,874 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:52,874 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:52,874 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:52,875 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:52,875 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:52,875 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:52,877 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:52,882 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:52,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,883 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,884 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,885 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2025-02-06 19:47:52,890 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-02-06 19:47:52,901 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:52,901 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:52,901 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:52,901 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:52,901 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:52,902 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:52,902 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:52,903 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:52,909 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:52,909 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,909 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,911 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,912 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2025-02-06 19:47:52,913 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-02-06 19:47:52,923 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:52,923 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:52,923 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:52,923 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:52,923 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:52,925 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:52,925 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:52,929 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:52,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2025-02-06 19:47:52,937 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,937 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,939 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,941 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2025-02-06 19:47:52,942 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-02-06 19:47:52,951 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:52,952 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:52,952 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:52,952 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:52,952 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:52,954 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:52,954 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:52,957 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-06 19:47:52,960 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-06 19:47:52,960 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-02-06 19:47:52,960 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:52,960 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:52,966 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:52,969 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2025-02-06 19:47:52,969 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-06 19:47:52,969 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-06 19:47:52,969 INFO L474 LassoAnalysis]: Proved termination. [2025-02-06 19:47:52,969 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-02-06 19:47:52,979 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2025-02-06 19:47:52,980 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-06 19:47:52,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:53,008 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 19:47:53,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 19:47:53,030 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:53,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:53,034 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-06 19:47:53,036 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:53,194 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:53,200 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:53,200 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:53,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:53,201 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-06 19:47:53,201 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:53,259 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:53,259 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-02-06 19:47:53,260 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:53,413 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2025-02-06 19:47:53,450 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 190 states and 265 transitions. Complement of second has 37 states. [2025-02-06 19:47:53,450 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-02-06 19:47:53,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:53,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2025-02-06 19:47:53,451 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2025-02-06 19:47:53,451 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:53,451 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-06 19:47:53,461 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:53,469 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 19:47:53,487 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 19:47:53,487 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:53,487 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:53,491 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-06 19:47:53,496 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:53,621 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:53,627 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:53,627 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:53,627 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:53,628 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-06 19:47:53,628 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:53,679 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:53,680 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-02-06 19:47:53,680 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:53,799 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 296 states and 402 transitions. Complement of second has 29 states. [2025-02-06 19:47:53,799 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-02-06 19:47:53,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:53,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2025-02-06 19:47:53,800 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2025-02-06 19:47:53,800 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:53,800 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-06 19:47:53,811 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:53,819 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-02-06 19:47:53,839 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-02-06 19:47:53,839 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:53,839 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:53,843 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-02-06 19:47:53,844 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:53,957 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-02-06 19:47:53,963 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-02-06 19:47:53,963 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:53,963 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:53,964 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-06 19:47:53,964 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:54,037 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:54,037 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-02-06 19:47:54,037 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:54,227 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 817 states and 1129 transitions. Complement of second has 135 states. [2025-02-06 19:47:54,227 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-02-06 19:47:54,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-06 19:47:54,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2025-02-06 19:47:54,228 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2025-02-06 19:47:54,229 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:54,229 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2025-02-06 19:47:54,229 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:54,229 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2025-02-06 19:47:54,230 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:54,230 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 817 states and 1129 transitions. [2025-02-06 19:47:54,248 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2025-02-06 19:47:54,263 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 817 states to 418 states and 629 transitions. [2025-02-06 19:47:54,264 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 162 [2025-02-06 19:47:54,264 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 182 [2025-02-06 19:47:54,265 INFO L73 IsDeterministic]: Start isDeterministic. Operand 418 states and 629 transitions. [2025-02-06 19:47:54,266 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:54,266 INFO L218 hiAutomatonCegarLoop]: Abstraction has 418 states and 629 transitions. [2025-02-06 19:47:54,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 418 states and 629 transitions. [2025-02-06 19:47:54,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 418 to 356. [2025-02-06 19:47:54,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 356 states, 223 states have (on average 1.1973094170403586) internal successors, (267), 239 states have internal predecessors, (267), 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-02-06 19:47:54,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 356 states to 356 states and 493 transitions. [2025-02-06 19:47:54,290 INFO L240 hiAutomatonCegarLoop]: Abstraction has 356 states and 493 transitions. [2025-02-06 19:47:54,290 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 19:47:54,290 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-02-06 19:47:54,290 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2025-02-06 19:47:54,290 INFO L87 Difference]: Start difference. First operand 356 states and 493 transitions. Second operand has 21 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 14 states have internal predecessors, (37), 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-02-06 19:47:54,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 19:47:54,541 INFO L93 Difference]: Finished difference Result 645 states and 1007 transitions. [2025-02-06 19:47:54,541 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 645 states and 1007 transitions. [2025-02-06 19:47:54,548 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2025-02-06 19:47:54,566 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 645 states to 614 states and 962 transitions. [2025-02-06 19:47:54,566 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 283 [2025-02-06 19:47:54,567 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 286 [2025-02-06 19:47:54,567 INFO L73 IsDeterministic]: Start isDeterministic. Operand 614 states and 962 transitions. [2025-02-06 19:47:54,567 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:54,567 INFO L218 hiAutomatonCegarLoop]: Abstraction has 614 states and 962 transitions. [2025-02-06 19:47:54,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 614 states and 962 transitions. [2025-02-06 19:47:54,599 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 614 to 538. [2025-02-06 19:47:54,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 538 states, 328 states have (on average 1.1432926829268293) internal successors, (375), 353 states have internal predecessors, (375), 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-02-06 19:47:54,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 538 states to 538 states and 798 transitions. [2025-02-06 19:47:54,611 INFO L240 hiAutomatonCegarLoop]: Abstraction has 538 states and 798 transitions. [2025-02-06 19:47:54,611 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-02-06 19:47:54,612 INFO L432 stractBuchiCegarLoop]: Abstraction has 538 states and 798 transitions. [2025-02-06 19:47:54,612 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-02-06 19:47:54,612 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 538 states and 798 transitions. [2025-02-06 19:47:54,619 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-02-06 19:47:54,619 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:54,619 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:54,620 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:54,620 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-02-06 19:47:54,620 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;" >"#24#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-02-06 19:47:54,620 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-02-06 19:47:54,621 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:54,621 INFO L85 PathProgramCache]: Analyzing trace with hash 1871794157, now seen corresponding path program 1 times [2025-02-06 19:47:54,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:54,621 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1742099835] [2025-02-06 19:47:54,621 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:54,621 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:54,627 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-06 19:47:54,641 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-06 19:47:54,641 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:54,641 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:54,901 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-06 19:47:54,902 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 19:47:54,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1742099835] [2025-02-06 19:47:54,902 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1742099835] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 19:47:54,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [465581215] [2025-02-06 19:47:54,902 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-06 19:47:54,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 19:47:54,902 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:54,906 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 19:47:54,907 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2025-02-06 19:47:54,925 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-06 19:47:54,934 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-06 19:47:54,934 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:54,934 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:54,934 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-06 19:47:54,935 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:54,976 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-06 19:47:54,976 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 19:47:55,123 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-06 19:47:55,123 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [465581215] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 19:47:55,123 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 19:47:55,123 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 20 [2025-02-06 19:47:55,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [645597113] [2025-02-06 19:47:55,124 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 19:47:55,124 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-02-06 19:47:55,124 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:55,124 INFO L85 PathProgramCache]: Analyzing trace with hash 1168785, now seen corresponding path program 2 times [2025-02-06 19:47:55,124 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:55,124 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1423427182] [2025-02-06 19:47:55,124 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 19:47:55,124 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:55,126 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:55,126 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:55,126 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-02-06 19:47:55,126 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:55,127 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:55,127 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:55,127 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:55,127 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,127 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:55,128 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:55,155 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:55,155 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:55,155 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:55,155 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:55,156 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-06 19:47:55,156 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,156 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:55,156 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:55,156 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2025-02-06 19:47:55,156 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:55,156 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:55,156 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,162 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,164 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,165 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,188 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:55,189 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-06 19:47:55,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:55,191 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:55,192 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2025-02-06 19:47:55,193 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:55,193 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:55,209 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:55,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:55,212 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:55,213 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2025-02-06 19:47:55,214 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-06 19:47:55,214 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:55,257 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-06 19:47:55,261 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:55,262 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:55,262 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:55,262 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:55,262 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:55,262 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-06 19:47:55,262 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,262 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:55,262 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:55,262 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2025-02-06 19:47:55,262 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:55,262 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:55,262 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,268 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,273 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,274 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,276 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:55,301 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:55,301 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-06 19:47:55,301 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:55,306 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:55,307 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2025-02-06 19:47:55,308 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-02-06 19:47:55,317 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:55,317 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:55,317 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:55,317 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:55,318 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:55,318 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:55,318 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:55,321 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:55,326 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2025-02-06 19:47:55,327 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:55,329 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:55,335 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2025-02-06 19:47:55,336 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-02-06 19:47:55,347 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:55,347 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:55,347 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:55,347 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:55,347 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:55,348 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:55,348 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:55,350 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-06 19:47:55,351 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-02-06 19:47:55,352 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-06 19:47:55,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:55,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:55,356 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:55,357 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2025-02-06 19:47:55,358 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-06 19:47:55,358 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-06 19:47:55,358 INFO L474 LassoAnalysis]: Proved termination. [2025-02-06 19:47:55,358 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2025-02-06 19:47:55,363 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:55,364 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-06 19:47:55,372 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:55,382 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-06 19:47:55,411 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-06 19:47:55,412 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,412 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:55,413 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-02-06 19:47:55,415 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:55,457 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:55,501 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:55,504 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:55,504 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,505 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:55,505 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-06 19:47:55,505 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:55,523 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:55,523 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-02-06 19:47:55,524 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 538 states and 798 transitions. cyclomatic complexity: 267 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:55,569 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 538 states and 798 transitions. cyclomatic complexity: 267. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 560 states and 820 transitions. Complement of second has 15 states. [2025-02-06 19:47:55,570 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-02-06 19:47:55,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:55,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2025-02-06 19:47:55,571 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2025-02-06 19:47:55,571 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:55,571 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-06 19:47:55,579 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:55,590 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-06 19:47:55,625 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-06 19:47:55,625 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,625 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:55,627 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-02-06 19:47:55,628 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:55,704 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:55,708 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:55,708 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,708 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:55,708 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-06 19:47:55,709 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:55,727 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:55,728 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-02-06 19:47:55,728 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 538 states and 798 transitions. cyclomatic complexity: 267 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:55,775 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 538 states and 798 transitions. cyclomatic complexity: 267. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 560 states and 820 transitions. Complement of second has 15 states. [2025-02-06 19:47:55,776 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-02-06 19:47:55,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:55,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2025-02-06 19:47:55,776 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2025-02-06 19:47:55,777 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:55,777 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-06 19:47:55,786 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:55,798 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-06 19:47:55,833 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-06 19:47:55,833 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,833 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:55,834 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-02-06 19:47:55,836 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:55,902 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:55,905 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:55,906 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:55,906 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:55,906 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-06 19:47:55,906 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:55,924 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:55,924 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-02-06 19:47:55,924 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 538 states and 798 transitions. cyclomatic complexity: 267 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:56,005 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 538 states and 798 transitions. cyclomatic complexity: 267. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 723 states and 986 transitions. Complement of second has 19 states. [2025-02-06 19:47:56,006 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-02-06 19:47:56,006 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:56,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2025-02-06 19:47:56,006 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2025-02-06 19:47:56,008 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:56,008 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2025-02-06 19:47:56,008 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:56,008 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2025-02-06 19:47:56,008 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:56,009 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 723 states and 986 transitions. [2025-02-06 19:47:56,014 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-02-06 19:47:56,020 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 723 states to 578 states and 839 transitions. [2025-02-06 19:47:56,020 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 211 [2025-02-06 19:47:56,020 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 217 [2025-02-06 19:47:56,020 INFO L73 IsDeterministic]: Start isDeterministic. Operand 578 states and 839 transitions. [2025-02-06 19:47:56,021 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:56,021 INFO L218 hiAutomatonCegarLoop]: Abstraction has 578 states and 839 transitions. [2025-02-06 19:47:56,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 578 states and 839 transitions. [2025-02-06 19:47:56,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 578 to 568. [2025-02-06 19:47:56,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 568 states, 355 states have (on average 1.1323943661971831) internal successors, (402), 383 states have internal predecessors, (402), 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-02-06 19:47:56,039 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 568 states to 568 states and 825 transitions. [2025-02-06 19:47:56,039 INFO L240 hiAutomatonCegarLoop]: Abstraction has 568 states and 825 transitions. [2025-02-06 19:47:56,039 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 19:47:56,039 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-02-06 19:47:56,039 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=292, Unknown=0, NotChecked=0, Total=380 [2025-02-06 19:47:56,039 INFO L87 Difference]: Start difference. First operand 568 states and 825 transitions. Second operand has 20 states, 19 states have (on average 1.736842105263158) internal successors, (33), 13 states have internal predecessors, (33), 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-02-06 19:47:56,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 19:47:56,323 INFO L93 Difference]: Finished difference Result 685 states and 1026 transitions. [2025-02-06 19:47:56,323 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 685 states and 1026 transitions. [2025-02-06 19:47:56,328 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-02-06 19:47:56,334 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 685 states to 664 states and 994 transitions. [2025-02-06 19:47:56,335 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 248 [2025-02-06 19:47:56,335 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 251 [2025-02-06 19:47:56,335 INFO L73 IsDeterministic]: Start isDeterministic. Operand 664 states and 994 transitions. [2025-02-06 19:47:56,335 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:56,335 INFO L218 hiAutomatonCegarLoop]: Abstraction has 664 states and 994 transitions. [2025-02-06 19:47:56,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 664 states and 994 transitions. [2025-02-06 19:47:56,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 664 to 610. [2025-02-06 19:47:56,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 610 states, 385 states have (on average 1.1272727272727272) internal successors, (434), 413 states have internal predecessors, (434), 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-02-06 19:47:56,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 610 states to 610 states and 852 transitions. [2025-02-06 19:47:56,351 INFO L240 hiAutomatonCegarLoop]: Abstraction has 610 states and 852 transitions. [2025-02-06 19:47:56,351 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-02-06 19:47:56,351 INFO L432 stractBuchiCegarLoop]: Abstraction has 610 states and 852 transitions. [2025-02-06 19:47:56,351 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-02-06 19:47:56,353 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 610 states and 852 transitions. [2025-02-06 19:47:56,355 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-02-06 19:47:56,355 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-06 19:47:56,355 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-06 19:47:56,356 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2025-02-06 19:47:56,356 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-02-06 19:47:56,356 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;" >"#24#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-02-06 19:47:56,356 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" [2025-02-06 19:47:56,356 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:56,357 INFO L85 PathProgramCache]: Analyzing trace with hash -546939830, now seen corresponding path program 2 times [2025-02-06 19:47:56,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:56,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2112866036] [2025-02-06 19:47:56,357 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 19:47:56,357 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:56,360 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 52 statements into 2 equivalence classes. [2025-02-06 19:47:56,367 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 52 of 52 statements. [2025-02-06 19:47:56,367 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 19:47:56,368 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:56,591 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-02-06 19:47:56,592 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-06 19:47:56,592 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2112866036] [2025-02-06 19:47:56,592 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2112866036] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-06 19:47:56,592 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [91535609] [2025-02-06 19:47:56,592 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-06 19:47:56,592 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-06 19:47:56,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:56,594 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-06 19:47:56,598 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Waiting until timeout for monitored process [2025-02-06 19:47:56,619 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 52 statements into 2 equivalence classes. [2025-02-06 19:47:56,628 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 52 of 52 statements. [2025-02-06 19:47:56,629 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-06 19:47:56,629 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:56,629 INFO L256 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-06 19:47:56,631 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:56,671 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-02-06 19:47:56,671 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-06 19:47:56,841 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-02-06 19:47:56,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [91535609] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-06 19:47:56,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-06 19:47:56,842 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2025-02-06 19:47:56,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1105277290] [2025-02-06 19:47:56,842 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-06 19:47:56,842 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-02-06 19:47:56,842 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:56,842 INFO L85 PathProgramCache]: Analyzing trace with hash 1616625, now seen corresponding path program 3 times [2025-02-06 19:47:56,842 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-06 19:47:56,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [607369914] [2025-02-06 19:47:56,842 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-06 19:47:56,843 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-06 19:47:56,844 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:56,845 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:56,845 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2025-02-06 19:47:56,845 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:56,848 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-06 19:47:56,849 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:56,849 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:56,849 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:56,849 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-06 19:47:56,850 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-06 19:47:56,910 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:56,910 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:56,910 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:56,910 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:56,910 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-06 19:47:56,910 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:56,910 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:56,910 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:56,910 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2025-02-06 19:47:56,910 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:56,910 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:56,911 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:56,915 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:56,917 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:56,925 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:56,964 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:56,964 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-06 19:47:56,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:56,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:56,967 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:56,969 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2025-02-06 19:47:56,970 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:56,970 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:56,984 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:56,984 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-02-06 19:47:56,991 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2025-02-06 19:47:56,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:56,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:56,994 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:56,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2025-02-06 19:47:56,996 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:56,996 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:57,007 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-06 19:47:57,007 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-02-06 19:47:57,013 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Ended with exit code 0 [2025-02-06 19:47:57,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:57,013 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:57,015 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:57,016 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2025-02-06 19:47:57,018 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-06 19:47:57,018 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:57,042 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:57,043 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:57,043 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:57,045 INFO L229 MonitoredProcess]: Starting monitored process 44 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:57,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2025-02-06 19:47:57,049 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-06 19:47:57,049 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-06 19:47:57,187 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-06 19:47:57,194 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:57,194 INFO L204 LassoAnalysis]: Preferences: [2025-02-06 19:47:57,194 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-06 19:47:57,194 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-06 19:47:57,194 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-06 19:47:57,194 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-06 19:47:57,194 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:57,194 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-06 19:47:57,194 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-06 19:47:57,194 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2025-02-06 19:47:57,194 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-06 19:47:57,195 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-06 19:47:57,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:57,197 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:57,202 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:57,204 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-06 19:47:57,230 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-06 19:47:57,230 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-06 19:47:57,231 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:57,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:57,232 INFO L229 MonitoredProcess]: Starting monitored process 45 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:57,234 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2025-02-06 19:47:57,235 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-02-06 19:47:57,244 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:57,244 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:57,245 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:57,245 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:57,245 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:57,245 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:57,245 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:57,246 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-06 19:47:57,252 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:57,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:57,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:57,254 INFO L229 MonitoredProcess]: Starting monitored process 46 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:57,254 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Waiting until timeout for monitored process [2025-02-06 19:47:57,255 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-02-06 19:47:57,265 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-06 19:47:57,265 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-06 19:47:57,265 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-06 19:47:57,265 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-06 19:47:57,266 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-06 19:47:57,268 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-06 19:47:57,268 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-06 19:47:57,270 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-06 19:47:57,272 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-02-06 19:47:57,272 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-06 19:47:57,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-06 19:47:57,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-06 19:47:57,274 INFO L229 MonitoredProcess]: Starting monitored process 47 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-06 19:47:57,274 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2025-02-06 19:47:57,276 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-06 19:47:57,276 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-06 19:47:57,276 INFO L474 LassoAnalysis]: Proved termination. [2025-02-06 19:47:57,276 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-02-06 19:47:57,282 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Ended with exit code 0 [2025-02-06 19:47:57,282 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-06 19:47:57,289 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:57,312 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-02-06 19:47:57,365 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-02-06 19:47:57,365 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:57,365 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:57,367 INFO L256 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-06 19:47:57,369 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:57,464 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:57,467 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:57,467 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:57,467 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:57,467 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-06 19:47:57,467 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:57,503 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:57,504 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-02-06 19:47:57,504 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 610 states and 852 transitions. cyclomatic complexity: 249 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:57,567 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 610 states and 852 transitions. cyclomatic complexity: 249. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 632 states and 875 transitions. Complement of second has 18 states. [2025-02-06 19:47:57,568 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-02-06 19:47:57,569 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:57,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-02-06 19:47:57,571 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2025-02-06 19:47:57,572 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:57,572 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-06 19:47:57,588 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-06 19:47:57,615 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-02-06 19:47:57,680 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-02-06 19:47:57,680 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:57,680 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:57,682 INFO L256 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-02-06 19:47:57,688 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:57,817 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-02-06 19:47:57,820 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-02-06 19:47:57,820 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-06 19:47:57,820 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-06 19:47:57,820 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-06 19:47:57,821 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-06 19:47:57,869 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-06 19:47:57,869 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-02-06 19:47:57,869 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 610 states and 852 transitions. cyclomatic complexity: 249 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:57,939 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 610 states and 852 transitions. cyclomatic complexity: 249. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 852 states and 1192 transitions. Complement of second has 22 states. [2025-02-06 19:47:57,942 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-02-06 19:47:57,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:57,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2025-02-06 19:47:57,944 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2025-02-06 19:47:57,945 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:57,945 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2025-02-06 19:47:57,945 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:57,945 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2025-02-06 19:47:57,945 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-06 19:47:57,945 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 852 states and 1192 transitions. [2025-02-06 19:47:57,959 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-02-06 19:47:57,965 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 852 states to 782 states and 1114 transitions. [2025-02-06 19:47:57,968 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 257 [2025-02-06 19:47:57,969 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 285 [2025-02-06 19:47:57,972 INFO L73 IsDeterministic]: Start isDeterministic. Operand 782 states and 1114 transitions. [2025-02-06 19:47:57,972 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-06 19:47:57,973 INFO L218 hiAutomatonCegarLoop]: Abstraction has 782 states and 1114 transitions. [2025-02-06 19:47:57,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 782 states and 1114 transitions. [2025-02-06 19:47:57,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 782 to 762. [2025-02-06 19:47:58,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 762 states, 485 states have (on average 1.1175257731958763) internal successors, (542), 520 states have internal predecessors, (542), 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-02-06 19:47:58,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 762 states to 762 states and 1090 transitions. [2025-02-06 19:47:58,027 INFO L240 hiAutomatonCegarLoop]: Abstraction has 762 states and 1090 transitions. [2025-02-06 19:47:58,027 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-06 19:47:58,028 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-02-06 19:47:58,028 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2025-02-06 19:47:58,028 INFO L87 Difference]: Start difference. First operand 762 states and 1090 transitions. Second operand has 21 states, 20 states have (on average 1.75) internal successors, (35), 12 states have internal predecessors, (35), 10 states have call successors, (11), 11 states have call predecessors, (11), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-06 19:47:58,029 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2025-02-06 19:47:58,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-06 19:47:58,442 INFO L93 Difference]: Finished difference Result 456 states and 539 transitions. [2025-02-06 19:47:58,442 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 456 states and 539 transitions. [2025-02-06 19:47:58,453 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-02-06 19:47:58,453 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 456 states to 0 states and 0 transitions. [2025-02-06 19:47:58,453 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-02-06 19:47:58,453 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-02-06 19:47:58,453 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-02-06 19:47:58,453 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-02-06 19:47:58,453 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-06 19:47:58,453 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-06 19:47:58,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-02-06 19:47:58,458 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-06 19:47:58,458 INFO L338 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2025-02-06 19:47:58,458 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-02-06 19:47:58,458 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-02-06 19:47:58,458 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-02-06 19:47:58,469 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 06.02 07:47:58 BoogieIcfgContainer [2025-02-06 19:47:58,471 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-02-06 19:47:58,471 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-02-06 19:47:58,474 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-02-06 19:47:58,475 INFO L274 PluginConnector]: Witness Printer initialized [2025-02-06 19:47:58,475 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 06.02 07:47:49" (3/4) ... [2025-02-06 19:47:58,476 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-02-06 19:47:58,477 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-02-06 19:47:58,477 INFO L158 Benchmark]: Toolchain (without parser) took 9046.05ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 113.8MB in the beginning and 115.4MB in the end (delta: -1.6MB). Peak memory consumption was 28.0MB. Max. memory is 16.1GB. [2025-02-06 19:47:58,478 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 201.3MB. Free memory is still 123.9MB. There was no memory consumed. Max. memory is 16.1GB. [2025-02-06 19:47:58,479 INFO L158 Benchmark]: CACSL2BoogieTranslator took 180.89ms. Allocated memory is still 142.6MB. Free memory was 113.3MB in the beginning and 103.2MB in the end (delta: 10.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-06 19:47:58,483 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.80ms. Allocated memory is still 142.6MB. Free memory was 103.2MB in the beginning and 102.1MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-06 19:47:58,483 INFO L158 Benchmark]: Boogie Preprocessor took 21.30ms. Allocated memory is still 142.6MB. Free memory was 102.1MB in the beginning and 101.1MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-06 19:47:58,483 INFO L158 Benchmark]: IcfgBuilder took 177.33ms. Allocated memory is still 142.6MB. Free memory was 101.1MB in the beginning and 91.5MB in the end (delta: 9.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-06 19:47:58,483 INFO L158 Benchmark]: BuchiAutomizer took 8634.48ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 91.1MB in the beginning and 115.4MB in the end (delta: -24.4MB). Peak memory consumption was 11.2MB. Max. memory is 16.1GB. [2025-02-06 19:47:58,483 INFO L158 Benchmark]: Witness Printer took 5.98ms. Allocated memory is still 176.2MB. Free memory was 115.4MB in the beginning and 115.4MB in the end (delta: 30.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-06 19:47:58,485 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.19ms. Allocated memory is still 201.3MB. Free memory is still 123.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 180.89ms. Allocated memory is still 142.6MB. Free memory was 113.3MB in the beginning and 103.2MB in the end (delta: 10.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 19.80ms. Allocated memory is still 142.6MB. Free memory was 103.2MB in the beginning and 102.1MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 21.30ms. Allocated memory is still 142.6MB. Free memory was 102.1MB in the beginning and 101.1MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 177.33ms. Allocated memory is still 142.6MB. Free memory was 101.1MB in the beginning and 91.5MB in the end (delta: 9.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 8634.48ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 91.1MB in the beginning and 115.4MB in the end (delta: -24.4MB). Peak memory consumption was 11.2MB. Max. memory is 16.1GB. * Witness Printer took 5.98ms. Allocated memory is still 176.2MB. Free memory was 115.4MB in the beginning and 115.4MB 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.5s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 3.9s. Construction of modules took 0.9s. Büchi inclusion checks took 3.3s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s 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, 540 SdHoareTripleChecker+Valid, 1.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 516 mSDsluCounter, 673 SdHoareTripleChecker+Invalid, 1.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 444 mSDsCounter, 313 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1403 IncrementalHoareTripleChecker+Invalid, 1716 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 313 mSolverCounterUnsat, 229 mSDtfsCounter, 1403 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: 21ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 11 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-02-06 19:47:58,509 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Ended with exit code 0 [2025-02-06 19:47:58,701 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Ended with exit code 0 [2025-02-06 19:47:58,901 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2025-02-06 19:47:59,101 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-02-06 19:47:59,303 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/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