./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 e2fb8bed Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive/Fibonacci02.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-09 07:32:00,115 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-09 07:32:00,175 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-03-09 07:32:00,178 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-09 07:32:00,178 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-09 07:32:00,178 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-09 07:32:00,195 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-09 07:32:00,196 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-09 07:32:00,196 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-09 07:32:00,196 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-09 07:32:00,196 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-09 07:32:00,197 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Use SBE=true [2025-03-09 07:32:00,197 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-09 07:32:00,197 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-09 07:32:00,197 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-09 07:32:00,198 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-09 07:32:00,198 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-09 07:32:00,198 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-09 07:32:00,198 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2025-03-09 07:32:00,422 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-09 07:32:00,428 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-09 07:32:00,431 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-09 07:32:00,432 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-09 07:32:00,432 INFO L274 PluginConnector]: CDTParser initialized [2025-03-09 07:32:00,434 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci02.c [2025-03-09 07:32:01,602 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/95333d340/112aa234e17c41f5b558d8391717fbb1/FLAGaebf66d7f [2025-03-09 07:32:01,855 INFO L384 CDTParser]: Found 1 translation units. [2025-03-09 07:32:01,857 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2025-03-09 07:32:01,862 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/95333d340/112aa234e17c41f5b558d8391717fbb1/FLAGaebf66d7f [2025-03-09 07:32:01,882 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/95333d340/112aa234e17c41f5b558d8391717fbb1 [2025-03-09 07:32:01,884 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-09 07:32:01,885 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-09 07:32:01,887 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-09 07:32:01,888 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-09 07:32:01,891 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-09 07:32:01,892 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.03 07:32:01" (1/1) ... [2025-03-09 07:32:01,893 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4d34c501 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:01, skipping insertion in model container [2025-03-09 07:32:01,894 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.03 07:32:01" (1/1) ... [2025-03-09 07:32:01,903 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-09 07:32:02,007 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-09 07:32:02,018 INFO L200 MainTranslator]: Completed pre-run [2025-03-09 07:32:02,028 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-09 07:32:02,040 INFO L204 MainTranslator]: Completed translation [2025-03-09 07:32:02,040 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02 WrapperNode [2025-03-09 07:32:02,040 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-09 07:32:02,041 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-09 07:32:02,041 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-09 07:32:02,041 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-09 07:32:02,046 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,050 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,061 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2025-03-09 07:32:02,061 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-09 07:32:02,062 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-09 07:32:02,062 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-09 07:32:02,062 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-09 07:32:02,067 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,067 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,068 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,075 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-09 07:32:02,076 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,076 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,077 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,078 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,078 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,078 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,079 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-09 07:32:02,081 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-09 07:32:02,082 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-09 07:32:02,082 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-09 07:32:02,083 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (1/1) ... [2025-03-09 07:32:02,087 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,096 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,109 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,111 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2025-03-09 07:32:02,130 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-03-09 07:32:02,131 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-03-09 07:32:02,131 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-09 07:32:02,131 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-09 07:32:02,131 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-09 07:32:02,131 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-09 07:32:02,172 INFO L256 CfgBuilder]: Building ICFG [2025-03-09 07:32:02,174 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-09 07:32:02,223 INFO L1307 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-03-09 07:32:02,249 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-09 07:32:02,250 INFO L307 CfgBuilder]: Performing block encoding [2025-03-09 07:32:02,257 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-09 07:32:02,258 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-09 07:32:02,258 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.03 07:32:02 BoogieIcfgContainer [2025-03-09 07:32:02,258 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-09 07:32:02,259 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-09 07:32:02,259 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-09 07:32:02,263 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-09 07:32:02,263 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-09 07:32:02,264 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.03 07:32:01" (1/3) ... [2025-03-09 07:32:02,265 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@7b75636b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.03 07:32:02, skipping insertion in model container [2025-03-09 07:32:02,265 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-09 07:32:02,265 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 07:32:02" (2/3) ... [2025-03-09 07:32:02,266 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@7b75636b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.03 07:32:02, skipping insertion in model container [2025-03-09 07:32:02,266 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-09 07:32:02,266 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.03 07:32:02" (3/3) ... [2025-03-09 07:32:02,267 INFO L363 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2025-03-09 07:32:02,307 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-09 07:32:02,308 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-09 07:32:02,308 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-09 07:32:02,308 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-09 07:32:02,308 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-09 07:32:02,309 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-09 07:32:02,309 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-09 07:32:02,309 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-09 07:32:02,312 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-03-09 07:32:02,326 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-09 07:32:02,327 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:02,327 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:02,331 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-09 07:32:02,331 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-09 07:32:02,331 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-09 07:32:02,331 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-03-09 07:32:02,332 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-09 07:32:02,333 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:02,333 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:02,334 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-09 07:32:02,334 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-09 07:32:02,338 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< [2025-03-09 07:32:02,338 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-03-09 07:32:02,343 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:02,344 INFO L85 PathProgramCache]: Analyzing trace with hash 48633, now seen corresponding path program 1 times [2025-03-09 07:32:02,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:02,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [762462830] [2025-03-09 07:32:02,351 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:02,351 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:02,395 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 07:32:02,409 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 07:32:02,409 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:02,409 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:02,410 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:02,415 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 07:32:02,420 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 07:32:02,421 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:02,421 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:02,436 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:02,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:02,438 INFO L85 PathProgramCache]: Analyzing trace with hash 1168785, now seen corresponding path program 1 times [2025-03-09 07:32:02,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:02,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1122404721] [2025-03-09 07:32:02,438 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:02,439 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:02,441 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:02,443 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:02,444 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:02,444 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:02,444 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:02,444 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:02,446 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:02,446 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:02,446 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:02,448 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:02,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:02,452 INFO L85 PathProgramCache]: Analyzing trace with hash 1964169097, now seen corresponding path program 1 times [2025-03-09 07:32:02,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:02,452 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [403484553] [2025-03-09 07:32:02,452 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:02,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:02,458 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-03-09 07:32:02,462 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-03-09 07:32:02,464 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:02,464 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:02,464 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:02,469 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-03-09 07:32:02,476 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-03-09 07:32:02,476 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:02,476 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:02,478 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:02,606 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:02,607 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:02,607 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:02,607 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:02,607 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 07:32:02,607 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,608 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:02,608 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:02,609 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2025-03-09 07:32:02,614 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:02,614 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:02,628 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:02,648 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:02,650 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:02,652 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:02,659 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:02,753 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:02,753 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 07:32:02,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,804 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,805 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2025-03-09 07:32:02,806 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:02,806 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:02,823 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:02,823 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:02,829 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2025-03-09 07:32:02,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,833 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2025-03-09 07:32:02,840 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:02,840 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:02,875 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:02,876 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:02,881 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2025-03-09 07:32:02,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,883 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,884 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2025-03-09 07:32:02,885 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:02,885 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:02,897 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:02,897 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:02,904 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2025-03-09 07:32:02,904 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,906 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,907 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2025-03-09 07:32:02,911 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:02,911 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:02,922 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:02,922 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:02,927 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2025-03-09 07:32:02,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,929 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,930 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2025-03-09 07:32:02,936 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:02,936 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:02,957 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2025-03-09 07:32:02,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:02,957 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:02,959 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:02,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-03-09 07:32:02,965 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 07:32:02,965 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:03,010 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 07:32:03,014 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-03-09 07:32:03,014 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:03,014 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:03,014 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:03,014 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:03,014 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 07:32:03,014 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,014 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:03,015 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:03,015 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2025-03-09 07:32:03,015 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:03,015 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:03,016 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:03,018 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:03,020 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:03,022 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:03,028 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:03,068 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:03,070 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 07:32:03,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,073 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,073 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2025-03-09 07:32:03,074 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:03,085 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:03,085 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:03,085 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:03,085 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:03,085 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:03,088 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:03,090 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:03,091 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:03,097 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2025-03-09 07:32:03,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,099 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,100 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2025-03-09 07:32:03,100 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:03,111 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:03,111 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:03,111 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:03,111 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:03,111 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:03,111 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:03,111 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:03,113 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:03,119 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2025-03-09 07:32:03,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,123 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,124 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2025-03-09 07:32:03,125 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:03,134 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:03,135 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:03,135 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:03,135 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:03,135 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:03,136 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:03,136 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:03,137 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:03,143 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:03,143 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,145 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,147 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2025-03-09 07:32:03,148 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:03,158 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:03,158 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:03,158 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:03,158 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:03,158 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:03,159 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:03,159 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:03,160 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:03,166 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2025-03-09 07:32:03,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,168 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,168 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-03-09 07:32:03,177 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:03,187 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:03,187 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:03,187 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:03,187 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:03,187 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:03,188 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:03,188 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:03,190 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 07:32:03,193 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 07:32:03,195 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-09 07:32:03,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,198 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,199 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2025-03-09 07:32:03,204 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 07:32:03,204 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 07:32:03,204 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 07:32:03,204 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2025-03-09 07:32:03,210 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2025-03-09 07:32:03,212 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 07:32:03,228 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:03,240 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 07:32:03,248 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 07:32:03,248 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,248 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:03,249 INFO L256 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-09 07:32:03,250 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:03,259 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:03,263 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:03,263 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,263 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:03,264 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 07:32:03,264 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:03,296 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:03,317 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2025-03-09 07:32:03,318 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-03-09 07:32:03,386 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2025-03-09 07:32:03,414 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-03-09 07:32:03,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:03,418 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-03-09 07:32:03,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2025-03-09 07:32:03,422 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2025-03-09 07:32:03,424 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:03,426 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2025-03-09 07:32:03,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:03,426 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2025-03-09 07:32:03,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:03,428 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2025-03-09 07:32:03,430 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-09 07:32:03,434 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2025-03-09 07:32:03,435 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2025-03-09 07:32:03,435 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2025-03-09 07:32:03,435 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2025-03-09 07:32:03,436 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:03,437 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2025-03-09 07:32:03,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2025-03-09 07:32:03,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2025-03-09 07:32:03,451 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-03-09 07:32:03,452 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2025-03-09 07:32:03,453 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-03-09 07:32:03,453 INFO L432 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-03-09 07:32:03,453 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-09 07:32:03,453 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2025-03-09 07:32:03,453 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-09 07:32:03,453 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:03,453 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:03,454 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:03,454 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:03,454 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-03-09 07:32:03,454 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-03-09 07:32:03,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:03,454 INFO L85 PathProgramCache]: Analyzing trace with hash 2036174640, now seen corresponding path program 1 times [2025-03-09 07:32:03,454 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:03,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521769359] [2025-03-09 07:32:03,455 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:03,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:03,458 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-09 07:32:03,462 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-09 07:32:03,462 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,462 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:03,537 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-09 07:32:03,537 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 07:32:03,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [521769359] [2025-03-09 07:32:03,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [521769359] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-09 07:32:03,537 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-09 07:32:03,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-09 07:32:03,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [442615755] [2025-03-09 07:32:03,538 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-09 07:32:03,539 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-09 07:32:03,540 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:03,540 INFO L85 PathProgramCache]: Analyzing trace with hash -624925077, now seen corresponding path program 1 times [2025-03-09 07:32:03,540 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:03,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1687025268] [2025-03-09 07:32:03,540 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:03,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:03,543 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-09 07:32:03,545 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-09 07:32:03,545 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:03,592 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-09 07:32:03,592 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 07:32:03,592 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1687025268] [2025-03-09 07:32:03,592 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1687025268] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-09 07:32:03,592 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-09 07:32:03,592 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-09 07:32:03,593 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [391540494] [2025-03-09 07:32:03,593 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-09 07:32:03,593 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-09 07:32:03,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 07:32:03,594 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-09 07:32:03,595 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-03-09 07:32:03,596 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-03-09 07:32:03,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 07:32:03,670 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2025-03-09 07:32:03,671 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2025-03-09 07:32:03,671 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-09 07:32:03,673 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2025-03-09 07:32:03,675 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2025-03-09 07:32:03,675 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2025-03-09 07:32:03,675 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2025-03-09 07:32:03,675 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:03,675 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-09 07:32:03,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2025-03-09 07:32:03,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2025-03-09 07:32:03,676 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-03-09 07:32:03,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2025-03-09 07:32:03,678 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-09 07:32:03,678 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-09 07:32:03,679 INFO L432 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-09 07:32:03,679 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-09 07:32:03,679 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2025-03-09 07:32:03,680 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-09 07:32:03,680 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:03,680 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:03,681 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:03,681 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:03,681 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-03-09 07:32:03,681 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-03-09 07:32:03,681 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:03,681 INFO L85 PathProgramCache]: Analyzing trace with hash -1302895192, now seen corresponding path program 1 times [2025-03-09 07:32:03,681 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:03,681 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1159341829] [2025-03-09 07:32:03,681 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:03,682 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:03,684 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-09 07:32:03,687 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-09 07:32:03,687 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,687 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:03,737 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:03,737 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 07:32:03,737 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1159341829] [2025-03-09 07:32:03,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1159341829] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-09 07:32:03,737 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [653274472] [2025-03-09 07:32:03,737 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:03,737 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-09 07:32:03,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:03,739 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-09 07:32:03,741 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-09 07:32:03,760 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-09 07:32:03,768 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-09 07:32:03,768 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,768 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:03,772 INFO L256 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-09 07:32:03,774 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:03,794 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:03,794 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-09 07:32:03,880 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:03,880 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [653274472] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-09 07:32:03,880 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-09 07:32:03,880 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2025-03-09 07:32:03,881 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693204363] [2025-03-09 07:32:03,881 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-09 07:32:03,881 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-09 07:32:03,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:03,881 INFO L85 PathProgramCache]: Analyzing trace with hash 2102359501, now seen corresponding path program 1 times [2025-03-09 07:32:03,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:03,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1397818357] [2025-03-09 07:32:03,881 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:03,881 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:03,883 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:03,889 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:03,892 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,892 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:03,892 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:03,893 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:03,895 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:03,895 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:03,895 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:03,896 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:03,993 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:03,993 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:03,993 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:03,993 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:03,993 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 07:32:03,993 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:03,993 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:03,993 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:03,993 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2025-03-09 07:32:03,993 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:03,993 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:03,994 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:03,996 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,002 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,005 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,008 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,041 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:04,041 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 07:32:04,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,041 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,043 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2025-03-09 07:32:04,044 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:04,044 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:04,055 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:04,055 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:04,063 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2025-03-09 07:32:04,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,065 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,066 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2025-03-09 07:32:04,067 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:04,067 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:04,083 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2025-03-09 07:32:04,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,085 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,086 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2025-03-09 07:32:04,087 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 07:32:04,087 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:04,101 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 07:32:04,107 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2025-03-09 07:32:04,107 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:04,107 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:04,107 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:04,107 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:04,108 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 07:32:04,108 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,108 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:04,108 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:04,108 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2025-03-09 07:32:04,108 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:04,108 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:04,108 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,116 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,120 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,122 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:04,158 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:04,158 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 07:32:04,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,161 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,162 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-03-09 07:32:04,164 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:04,174 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:04,174 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:04,174 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:04,174 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:04,174 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:04,175 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:04,175 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:04,176 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:04,181 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-03-09 07:32:04,181 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,181 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,183 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,183 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2025-03-09 07:32:04,185 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:04,194 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:04,194 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:04,194 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:04,194 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:04,194 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:04,195 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:04,195 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:04,198 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 07:32:04,200 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 07:32:04,200 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-09 07:32:04,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:04,200 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,202 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2025-03-09 07:32:04,205 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 07:32:04,205 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 07:32:04,205 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 07:32:04,205 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-03-09 07:32:04,213 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2025-03-09 07:32:04,213 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 07:32:04,226 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:04,236 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-09 07:32:04,248 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-09 07:32:04,248 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:04,248 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:04,249 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-09 07:32:04,250 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:04,344 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:04,352 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:04,352 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:04,352 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:04,353 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-09 07:32:04,354 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:04,407 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2025-03-09 07:32:04,447 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:04,448 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2025-03-09 07:32:04,448 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-03-09 07:32:04,614 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-03-09 07:32:04,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:04,615 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-03-09 07:32:04,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2025-03-09 07:32:04,616 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2025-03-09 07:32:04,616 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:04,616 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2025-03-09 07:32:04,616 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:04,616 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2025-03-09 07:32:04,616 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:04,616 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2025-03-09 07:32:04,620 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-09 07:32:04,623 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2025-03-09 07:32:04,623 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2025-03-09 07:32:04,623 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2025-03-09 07:32:04,623 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2025-03-09 07:32:04,624 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:04,624 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2025-03-09 07:32:04,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2025-03-09 07:32:04,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2025-03-09 07:32:04,630 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-03-09 07:32:04,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2025-03-09 07:32:04,631 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2025-03-09 07:32:04,631 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 07:32:04,631 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-09 07:32:04,631 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-09 07:32:04,632 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-03-09 07:32:04,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 07:32:04,728 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2025-03-09 07:32:04,728 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2025-03-09 07:32:04,731 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-09 07:32:04,732 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2025-03-09 07:32:04,732 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2025-03-09 07:32:04,733 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2025-03-09 07:32:04,733 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2025-03-09 07:32:04,733 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:04,733 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2025-03-09 07:32:04,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2025-03-09 07:32:04,738 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2025-03-09 07:32:04,738 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-03-09 07:32:04,739 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2025-03-09 07:32:04,739 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2025-03-09 07:32:04,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-09 07:32:04,740 INFO L432 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2025-03-09 07:32:04,740 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-09 07:32:04,740 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2025-03-09 07:32:04,742 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-09 07:32:04,742 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:04,742 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:04,742 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:04,742 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:04,742 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-03-09 07:32:04,742 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-03-09 07:32:04,743 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:04,743 INFO L85 PathProgramCache]: Analyzing trace with hash -1833162896, now seen corresponding path program 1 times [2025-03-09 07:32:04,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:04,743 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [996340165] [2025-03-09 07:32:04,743 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:04,743 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:04,746 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-09 07:32:04,758 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-09 07:32:04,759 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:04,759 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:04,903 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-09 07:32:04,903 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 07:32:04,903 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [996340165] [2025-03-09 07:32:04,903 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [996340165] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-09 07:32:04,903 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1267551] [2025-03-09 07:32:04,903 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:04,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-09 07:32:04,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:04,905 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-09 07:32:04,906 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-09 07:32:04,927 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-09 07:32:04,934 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-09 07:32:04,934 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:04,934 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:04,935 INFO L256 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-09 07:32:04,936 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:04,986 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-09 07:32:04,986 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-09 07:32:05,234 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-09 07:32:05,235 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1267551] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-09 07:32:05,235 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-09 07:32:05,235 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 12] total 20 [2025-03-09 07:32:05,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1569904692] [2025-03-09 07:32:05,235 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-09 07:32:05,235 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-09 07:32:05,235 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:05,235 INFO L85 PathProgramCache]: Analyzing trace with hash 2102359501, now seen corresponding path program 2 times [2025-03-09 07:32:05,235 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:05,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [323633915] [2025-03-09 07:32:05,236 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 07:32:05,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:05,238 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 10 statements into 2 equivalence classes. [2025-03-09 07:32:05,240 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:05,240 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 07:32:05,240 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:05,240 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:05,240 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:05,241 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:05,241 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:05,241 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:05,242 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:05,329 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:05,329 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:05,329 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:05,329 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:05,329 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 07:32:05,329 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,329 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:05,329 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:05,329 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2025-03-09 07:32:05,329 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:05,329 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:05,329 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,331 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,333 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,334 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,336 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,365 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:05,365 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 07:32:05,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,365 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,367 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,368 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2025-03-09 07:32:05,370 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:05,370 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:05,381 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:05,381 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:05,387 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:05,387 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,387 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,389 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,390 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2025-03-09 07:32:05,391 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:05,391 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:05,405 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:05,405 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=1} Honda state: {fibonacci_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:05,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2025-03-09 07:32:05,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,413 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2025-03-09 07:32:05,415 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:05,415 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:05,430 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:05,431 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:05,436 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:05,436 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,438 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,439 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-03-09 07:32:05,440 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:05,440 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:05,451 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:05,451 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=2} Honda state: {fibonacci_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:05,457 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-03-09 07:32:05,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,460 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,462 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-03-09 07:32:05,463 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:05,463 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:05,480 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:05,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,482 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,484 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2025-03-09 07:32:05,485 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 07:32:05,485 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:05,497 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 07:32:05,503 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:05,503 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:05,503 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:05,503 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:05,503 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:05,503 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 07:32:05,503 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,503 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:05,503 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:05,503 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2025-03-09 07:32:05,503 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:05,503 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:05,504 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,508 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,509 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,511 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,513 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:05,542 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:05,542 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 07:32:05,542 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,542 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,545 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,546 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2025-03-09 07:32:05,547 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:05,557 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:05,558 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:05,558 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:05,558 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:05,558 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:05,559 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:05,559 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:05,561 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:05,566 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2025-03-09 07:32:05,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,569 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,569 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2025-03-09 07:32:05,570 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:05,580 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:05,580 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:05,580 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:05,580 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:05,580 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:05,580 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:05,580 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:05,581 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:05,588 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2025-03-09 07:32:05,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,592 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,593 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,594 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2025-03-09 07:32:05,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-03-09 07:32:05,605 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:05,605 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:05,605 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:05,605 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:05,605 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:05,605 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:05,605 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:05,606 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:05,612 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2025-03-09 07:32:05,612 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,613 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,614 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2025-03-09 07:32:05,615 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:05,624 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:05,625 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:05,625 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:05,625 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:05,625 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:05,625 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:05,625 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:05,627 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:05,632 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:05,633 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,633 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,635 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2025-03-09 07:32:05,637 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:05,646 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:05,646 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:05,647 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:05,647 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:05,647 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:05,647 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:05,647 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:05,649 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 07:32:05,651 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 07:32:05,651 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-09 07:32:05,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:05,651 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:05,653 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:05,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2025-03-09 07:32:05,654 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 07:32:05,654 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 07:32:05,654 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 07:32:05,654 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-03-09 07:32:05,660 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2025-03-09 07:32:05,661 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 07:32:05,668 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:05,684 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-09 07:32:05,706 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-09 07:32:05,706 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:05,706 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:05,707 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-09 07:32:05,709 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:05,854 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:05,861 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:05,861 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:05,861 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:05,862 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-09 07:32:05,862 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:05,924 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:05,925 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2025-03-09 07:32:05,926 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-03-09 07:32:06,121 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2025-03-09 07:32:06,125 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-03-09 07:32:06,127 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:06,127 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-03-09 07:32:06,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2025-03-09 07:32:06,128 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2025-03-09 07:32:06,128 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:06,128 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 07:32:06,137 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:06,146 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-09 07:32:06,166 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-09 07:32:06,166 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:06,166 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:06,167 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-09 07:32:06,168 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:06,309 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:06,317 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:06,317 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:06,317 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:06,317 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-09 07:32:06,318 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:06,379 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:06,379 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2025-03-09 07:32:06,380 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-03-09 07:32:06,528 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-03-09 07:32:06,528 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:06,530 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-03-09 07:32:06,530 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2025-03-09 07:32:06,530 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2025-03-09 07:32:06,530 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:06,530 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 07:32:06,540 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:06,552 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-09 07:32:06,579 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-09 07:32:06,579 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:06,579 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:06,581 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-09 07:32:06,582 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:06,713 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 07:32:06,719 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 07:32:06,720 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:06,720 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:06,720 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-09 07:32:06,721 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:06,792 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:06,793 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2025-03-09 07:32:06,793 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-03-09 07:32:06,960 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-03-09 07:32:06,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:06,962 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-03-09 07:32:06,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2025-03-09 07:32:06,962 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2025-03-09 07:32:06,963 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:06,963 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2025-03-09 07:32:06,963 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:06,963 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2025-03-09 07:32:06,964 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:06,964 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 817 states and 1129 transitions. [2025-03-09 07:32:06,974 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2025-03-09 07:32:06,988 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 817 states to 418 states and 629 transitions. [2025-03-09 07:32:06,988 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 162 [2025-03-09 07:32:06,988 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 182 [2025-03-09 07:32:06,988 INFO L73 IsDeterministic]: Start isDeterministic. Operand 418 states and 629 transitions. [2025-03-09 07:32:06,988 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:06,988 INFO L218 hiAutomatonCegarLoop]: Abstraction has 418 states and 629 transitions. [2025-03-09 07:32:06,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 418 states and 629 transitions. [2025-03-09 07:32:07,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 418 to 356. [2025-03-09 07:32:07,019 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-03-09 07:32:07,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 356 states to 356 states and 493 transitions. [2025-03-09 07:32:07,024 INFO L240 hiAutomatonCegarLoop]: Abstraction has 356 states and 493 transitions. [2025-03-09 07:32:07,024 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 07:32:07,024 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-09 07:32:07,024 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2025-03-09 07:32:07,025 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-03-09 07:32:07,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 07:32:07,317 INFO L93 Difference]: Finished difference Result 645 states and 1007 transitions. [2025-03-09 07:32:07,318 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 645 states and 1007 transitions. [2025-03-09 07:32:07,327 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2025-03-09 07:32:07,339 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 645 states to 614 states and 962 transitions. [2025-03-09 07:32:07,339 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 283 [2025-03-09 07:32:07,341 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 286 [2025-03-09 07:32:07,342 INFO L73 IsDeterministic]: Start isDeterministic. Operand 614 states and 962 transitions. [2025-03-09 07:32:07,342 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:07,342 INFO L218 hiAutomatonCegarLoop]: Abstraction has 614 states and 962 transitions. [2025-03-09 07:32:07,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 614 states and 962 transitions. [2025-03-09 07:32:07,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 614 to 538. [2025-03-09 07:32:07,360 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-03-09 07:32:07,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 538 states to 538 states and 798 transitions. [2025-03-09 07:32:07,365 INFO L240 hiAutomatonCegarLoop]: Abstraction has 538 states and 798 transitions. [2025-03-09 07:32:07,366 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-09 07:32:07,367 INFO L432 stractBuchiCegarLoop]: Abstraction has 538 states and 798 transitions. [2025-03-09 07:32:07,367 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-09 07:32:07,367 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 538 states and 798 transitions. [2025-03-09 07:32:07,370 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-09 07:32:07,371 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:07,371 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:07,372 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:07,372 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-09 07:32:07,372 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-03-09 07:32:07,372 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibonacci(~n - 1);"< [2025-03-09 07:32:07,372 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:07,372 INFO L85 PathProgramCache]: Analyzing trace with hash 1871794157, now seen corresponding path program 1 times [2025-03-09 07:32:07,372 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:07,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1673073115] [2025-03-09 07:32:07,372 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:07,372 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:07,375 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-09 07:32:07,380 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-09 07:32:07,380 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:07,380 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:07,605 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-09 07:32:07,606 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 07:32:07,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1673073115] [2025-03-09 07:32:07,606 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1673073115] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-09 07:32:07,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1003728180] [2025-03-09 07:32:07,606 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 07:32:07,606 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-09 07:32:07,606 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:07,608 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-09 07:32:07,610 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2025-03-09 07:32:07,628 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-09 07:32:07,636 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-09 07:32:07,637 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:07,637 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:07,638 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-09 07:32:07,639 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:07,684 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-09 07:32:07,684 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-09 07:32:07,848 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-09 07:32:07,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1003728180] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-09 07:32:07,848 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-09 07:32:07,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 20 [2025-03-09 07:32:07,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1013816686] [2025-03-09 07:32:07,849 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-09 07:32:07,849 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-09 07:32:07,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:07,849 INFO L85 PathProgramCache]: Analyzing trace with hash 1168785, now seen corresponding path program 2 times [2025-03-09 07:32:07,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:07,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [287882924] [2025-03-09 07:32:07,849 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 07:32:07,849 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:07,851 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:07,853 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:07,853 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-09 07:32:07,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:07,853 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:07,855 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:07,856 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:07,856 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:07,856 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:07,858 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:07,885 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:07,885 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:07,885 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:07,885 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:07,885 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 07:32:07,885 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:07,885 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:07,885 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:07,885 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2025-03-09 07:32:07,885 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:07,885 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:07,885 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:07,891 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:07,892 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:07,893 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:07,895 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:07,921 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:07,921 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 07:32:07,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:07,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:07,923 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:07,925 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2025-03-09 07:32:07,926 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:07,926 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:07,941 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2025-03-09 07:32:07,942 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:07,942 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:07,943 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:07,944 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2025-03-09 07:32:07,945 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 07:32:07,945 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:07,989 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 07:32:07,993 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2025-03-09 07:32:07,993 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:07,993 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:07,993 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:07,993 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:07,994 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 07:32:07,994 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:07,994 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:07,994 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:07,994 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2025-03-09 07:32:07,994 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:07,994 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:07,994 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:07,996 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:08,000 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:08,001 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:08,002 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:08,026 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:08,026 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 07:32:08,026 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:08,026 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:08,030 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:08,031 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2025-03-09 07:32:08,033 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:08,042 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:08,042 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:08,042 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:08,043 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:08,043 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:08,043 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:08,043 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:08,044 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:08,049 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:08,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:08,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:08,052 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:08,052 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2025-03-09 07:32:08,054 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:08,063 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:08,063 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:08,063 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:08,063 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:08,063 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:08,064 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:08,064 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:08,065 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 07:32:08,066 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-09 07:32:08,066 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 07:32:08,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:08,067 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:08,069 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:08,069 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2025-03-09 07:32:08,070 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 07:32:08,070 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 07:32:08,070 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 07:32:08,070 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2025-03-09 07:32:08,075 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:08,076 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 07:32:08,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:08,099 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-09 07:32:08,127 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-09 07:32:08,128 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:08,128 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:08,129 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-09 07:32:08,130 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:08,179 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Ended with exit code 0 [2025-03-09 07:32:08,218 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:08,221 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:08,221 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:08,221 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:08,221 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 07:32:08,222 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:08,241 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:08,241 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-09 07:32:08,241 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-03-09 07:32:08,288 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-03-09 07:32:08,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:08,290 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-03-09 07:32:08,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2025-03-09 07:32:08,290 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2025-03-09 07:32:08,290 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:08,290 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 07:32:08,298 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:08,309 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-09 07:32:08,339 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-09 07:32:08,340 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:08,340 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:08,342 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-09 07:32:08,343 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:08,410 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:08,413 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:08,413 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:08,413 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:08,414 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 07:32:08,414 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:08,431 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:08,432 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-09 07:32:08,432 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-03-09 07:32:08,479 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-03-09 07:32:08,479 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:08,480 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-03-09 07:32:08,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2025-03-09 07:32:08,480 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2025-03-09 07:32:08,480 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:08,480 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 07:32:08,489 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:08,500 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-09 07:32:08,528 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-09 07:32:08,528 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:08,528 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:08,530 INFO L256 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-09 07:32:08,531 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:08,619 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:08,622 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:08,622 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:08,622 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:08,623 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 07:32:08,623 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:08,642 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:08,642 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-09 07:32:08,642 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-03-09 07:32:08,695 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-03-09 07:32:08,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:08,696 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-03-09 07:32:08,696 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2025-03-09 07:32:08,696 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2025-03-09 07:32:08,697 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:08,697 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2025-03-09 07:32:08,697 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:08,697 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2025-03-09 07:32:08,697 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:08,698 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 723 states and 986 transitions. [2025-03-09 07:32:08,720 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-09 07:32:08,728 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 723 states to 578 states and 839 transitions. [2025-03-09 07:32:08,729 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 211 [2025-03-09 07:32:08,729 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 217 [2025-03-09 07:32:08,730 INFO L73 IsDeterministic]: Start isDeterministic. Operand 578 states and 839 transitions. [2025-03-09 07:32:08,730 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:08,730 INFO L218 hiAutomatonCegarLoop]: Abstraction has 578 states and 839 transitions. [2025-03-09 07:32:08,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 578 states and 839 transitions. [2025-03-09 07:32:08,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 578 to 568. [2025-03-09 07:32:08,745 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-03-09 07:32:08,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 568 states to 568 states and 825 transitions. [2025-03-09 07:32:08,748 INFO L240 hiAutomatonCegarLoop]: Abstraction has 568 states and 825 transitions. [2025-03-09 07:32:08,749 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 07:32:08,749 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-09 07:32:08,749 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=292, Unknown=0, NotChecked=0, Total=380 [2025-03-09 07:32:08,749 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-03-09 07:32:08,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 07:32:08,985 INFO L93 Difference]: Finished difference Result 685 states and 1026 transitions. [2025-03-09 07:32:08,985 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 685 states and 1026 transitions. [2025-03-09 07:32:08,990 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-09 07:32:08,996 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 685 states to 664 states and 994 transitions. [2025-03-09 07:32:08,996 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 248 [2025-03-09 07:32:08,996 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 251 [2025-03-09 07:32:08,996 INFO L73 IsDeterministic]: Start isDeterministic. Operand 664 states and 994 transitions. [2025-03-09 07:32:08,997 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:08,997 INFO L218 hiAutomatonCegarLoop]: Abstraction has 664 states and 994 transitions. [2025-03-09 07:32:08,997 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 664 states and 994 transitions. [2025-03-09 07:32:09,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 664 to 610. [2025-03-09 07:32:09,010 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-03-09 07:32:09,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 610 states to 610 states and 852 transitions. [2025-03-09 07:32:09,013 INFO L240 hiAutomatonCegarLoop]: Abstraction has 610 states and 852 transitions. [2025-03-09 07:32:09,017 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-09 07:32:09,017 INFO L432 stractBuchiCegarLoop]: Abstraction has 610 states and 852 transitions. [2025-03-09 07:32:09,017 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-09 07:32:09,017 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 610 states and 852 transitions. [2025-03-09 07:32:09,020 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-09 07:32:09,020 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 07:32:09,020 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 07:32:09,021 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 07:32:09,021 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-09 07:32:09,021 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9;" "call main_#t~ret6#1 := fibonacci(main_~x~0#1);"< "~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-03-09 07:32:09,021 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret4 := fibonacci(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" [2025-03-09 07:32:09,022 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:09,022 INFO L85 PathProgramCache]: Analyzing trace with hash -546939830, now seen corresponding path program 2 times [2025-03-09 07:32:09,022 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:09,022 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [425853336] [2025-03-09 07:32:09,022 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 07:32:09,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:09,025 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 52 statements into 2 equivalence classes. [2025-03-09 07:32:09,030 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 52 of 52 statements. [2025-03-09 07:32:09,030 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 07:32:09,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:09,264 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-09 07:32:09,264 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 07:32:09,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [425853336] [2025-03-09 07:32:09,264 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [425853336] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-09 07:32:09,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1468425366] [2025-03-09 07:32:09,264 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 07:32:09,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-09 07:32:09,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,266 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,268 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Waiting until timeout for monitored process [2025-03-09 07:32:09,290 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 52 statements into 2 equivalence classes. [2025-03-09 07:32:09,301 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 52 of 52 statements. [2025-03-09 07:32:09,302 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 07:32:09,302 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:09,302 INFO L256 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 07:32:09,304 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:09,352 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-09 07:32:09,353 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-09 07:32:09,521 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-09 07:32:09,521 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1468425366] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-09 07:32:09,521 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-09 07:32:09,521 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2025-03-09 07:32:09,521 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [504154383] [2025-03-09 07:32:09,521 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-09 07:32:09,522 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-09 07:32:09,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:09,522 INFO L85 PathProgramCache]: Analyzing trace with hash 1616625, now seen corresponding path program 3 times [2025-03-09 07:32:09,523 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 07:32:09,523 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [192167280] [2025-03-09 07:32:09,523 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-09 07:32:09,523 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 07:32:09,525 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:09,527 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:09,528 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2025-03-09 07:32:09,528 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:09,528 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 07:32:09,529 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:09,529 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:09,529 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:09,529 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 07:32:09,530 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 07:32:09,569 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:09,569 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:09,569 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:09,569 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:09,569 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 07:32:09,569 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,569 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:09,569 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:09,569 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2025-03-09 07:32:09,569 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:09,570 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:09,570 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,572 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,573 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,580 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,607 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:09,607 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 07:32:09,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,612 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,613 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2025-03-09 07:32:09,614 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:09,614 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:09,626 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:09,626 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:09,636 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2025-03-09 07:32:09,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,639 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,641 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2025-03-09 07:32:09,642 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:09,642 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:09,655 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 07:32:09,655 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 07:32:09,662 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:09,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,664 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,665 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2025-03-09 07:32:09,667 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 07:32:09,667 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:09,691 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:09,691 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,694 INFO L229 MonitoredProcess]: Starting monitored process 44 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,695 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2025-03-09 07:32:09,696 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 07:32:09,696 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 07:32:09,835 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 07:32:09,841 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Ended with exit code 0 [2025-03-09 07:32:09,841 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 07:32:09,841 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 07:32:09,841 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 07:32:09,841 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 07:32:09,841 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 07:32:09,841 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,841 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 07:32:09,841 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 07:32:09,841 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2025-03-09 07:32:09,842 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 07:32:09,842 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 07:32:09,842 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,844 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,849 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,851 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 07:32:09,871 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 07:32:09,871 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 07:32:09,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,873 INFO L229 MonitoredProcess]: Starting monitored process 45 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,875 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2025-03-09 07:32:09,875 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:09,885 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:09,885 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:09,885 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:09,885 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:09,885 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:09,885 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:09,885 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:09,886 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 07:32:09,892 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Ended with exit code 0 [2025-03-09 07:32:09,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,892 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,894 INFO L229 MonitoredProcess]: Starting monitored process 46 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,894 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Waiting until timeout for monitored process [2025-03-09 07:32:09,895 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-09 07:32:09,905 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 07:32:09,905 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 07:32:09,905 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 07:32:09,905 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 07:32:09,905 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 07:32:09,906 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 07:32:09,906 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 07:32:09,908 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 07:32:09,909 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-09 07:32:09,909 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 07:32:09,909 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 07:32:09,909 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 07:32:09,911 INFO L229 MonitoredProcess]: Starting monitored process 47 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-09 07:32:09,912 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2025-03-09 07:32:09,913 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 07:32:09,913 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 07:32:09,913 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 07:32:09,913 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2025-03-09 07:32:09,918 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Ended with exit code 0 [2025-03-09 07:32:09,918 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 07:32:09,925 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:09,939 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-03-09 07:32:09,972 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-03-09 07:32:09,972 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:09,972 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:09,974 INFO L256 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-09 07:32:09,975 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:10,011 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2025-03-09 07:32:10,059 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:10,062 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:10,062 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:10,062 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:10,062 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 07:32:10,063 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:10,086 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:10,086 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2025-03-09 07:32:10,086 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-03-09 07:32:10,126 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-03-09 07:32:10,127 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:10,127 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-03-09 07:32:10,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-03-09 07:32:10,127 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2025-03-09 07:32:10,127 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:10,127 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 07:32:10,136 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 07:32:10,149 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-03-09 07:32:10,187 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-03-09 07:32:10,187 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:10,187 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:10,189 INFO L256 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-09 07:32:10,191 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:10,268 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-09 07:32:10,271 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-09 07:32:10,271 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 07:32:10,271 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 07:32:10,272 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 07:32:10,272 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 07:32:10,298 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-09 07:32:10,299 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2025-03-09 07:32:10,299 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-03-09 07:32:10,363 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-03-09 07:32:10,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2025-03-09 07:32:10,363 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-03-09 07:32:10,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2025-03-09 07:32:10,364 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2025-03-09 07:32:10,364 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:10,364 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2025-03-09 07:32:10,364 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:10,364 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2025-03-09 07:32:10,364 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 07:32:10,364 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 852 states and 1192 transitions. [2025-03-09 07:32:10,371 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2025-03-09 07:32:10,378 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 852 states to 782 states and 1114 transitions. [2025-03-09 07:32:10,378 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 257 [2025-03-09 07:32:10,378 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 285 [2025-03-09 07:32:10,378 INFO L73 IsDeterministic]: Start isDeterministic. Operand 782 states and 1114 transitions. [2025-03-09 07:32:10,378 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 07:32:10,378 INFO L218 hiAutomatonCegarLoop]: Abstraction has 782 states and 1114 transitions. [2025-03-09 07:32:10,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 782 states and 1114 transitions. [2025-03-09 07:32:10,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 782 to 762. [2025-03-09 07:32:10,390 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-03-09 07:32:10,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 762 states to 762 states and 1090 transitions. [2025-03-09 07:32:10,393 INFO L240 hiAutomatonCegarLoop]: Abstraction has 762 states and 1090 transitions. [2025-03-09 07:32:10,393 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 07:32:10,393 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-09 07:32:10,394 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2025-03-09 07:32:10,394 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-03-09 07:32:10,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 07:32:10,614 INFO L93 Difference]: Finished difference Result 456 states and 539 transitions. [2025-03-09 07:32:10,614 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 456 states and 539 transitions. [2025-03-09 07:32:10,617 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-09 07:32:10,617 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 456 states to 0 states and 0 transitions. [2025-03-09 07:32:10,617 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-09 07:32:10,617 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-09 07:32:10,617 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-09 07:32:10,617 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-09 07:32:10,618 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-09 07:32:10,618 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-09 07:32:10,618 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-09 07:32:10,618 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-09 07:32:10,618 INFO L338 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2025-03-09 07:32:10,618 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-09 07:32:10,618 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-09 07:32:10,618 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-09 07:32:10,627 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.03 07:32:10 BoogieIcfgContainer [2025-03-09 07:32:10,627 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-09 07:32:10,627 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-09 07:32:10,628 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-09 07:32:10,628 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-09 07:32:10,628 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.03 07:32:02" (3/4) ... [2025-03-09 07:32:10,630 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-09 07:32:10,630 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-09 07:32:10,632 INFO L158 Benchmark]: Toolchain (without parser) took 8745.51ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 112.3MB in the beginning and 63.2MB in the end (delta: 49.1MB). Peak memory consumption was 80.6MB. Max. memory is 16.1GB. [2025-03-09 07:32:10,632 INFO L158 Benchmark]: CDTParser took 0.24ms. Allocated memory is still 201.3MB. Free memory is still 124.4MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 07:32:10,632 INFO L158 Benchmark]: CACSL2BoogieTranslator took 153.59ms. Allocated memory is still 142.6MB. Free memory was 111.8MB in the beginning and 101.6MB in the end (delta: 10.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-09 07:32:10,633 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.04ms. Allocated memory is still 142.6MB. Free memory was 101.6MB in the beginning and 100.6MB in the end (delta: 966.3kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 07:32:10,633 INFO L158 Benchmark]: Boogie Preprocessor took 17.52ms. Allocated memory is still 142.6MB. Free memory was 100.6MB in the beginning and 99.8MB in the end (delta: 883.8kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 07:32:10,633 INFO L158 Benchmark]: IcfgBuilder took 176.88ms. Allocated memory is still 142.6MB. Free memory was 99.8MB in the beginning and 89.9MB in the end (delta: 9.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-09 07:32:10,633 INFO L158 Benchmark]: BuchiAutomizer took 8368.13ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 89.9MB in the beginning and 63.2MB in the end (delta: 26.7MB). Peak memory consumption was 55.4MB. Max. memory is 16.1GB. [2025-03-09 07:32:10,633 INFO L158 Benchmark]: Witness Printer took 2.67ms. Allocated memory is still 176.2MB. Free memory was 63.2MB in the beginning and 63.2MB in the end (delta: 27.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 07:32:10,635 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.24ms. Allocated memory is still 201.3MB. Free memory is still 124.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 153.59ms. Allocated memory is still 142.6MB. Free memory was 111.8MB in the beginning and 101.6MB in the end (delta: 10.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.04ms. Allocated memory is still 142.6MB. Free memory was 101.6MB in the beginning and 100.6MB in the end (delta: 966.3kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 17.52ms. Allocated memory is still 142.6MB. Free memory was 100.6MB in the beginning and 99.8MB in the end (delta: 883.8kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 176.88ms. Allocated memory is still 142.6MB. Free memory was 99.8MB in the beginning and 89.9MB in the end (delta: 9.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * BuchiAutomizer took 8368.13ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 89.9MB in the beginning and 63.2MB in the end (delta: 26.7MB). Peak memory consumption was 55.4MB. Max. memory is 16.1GB. * Witness Printer took 2.67ms. Allocated memory is still 176.2MB. Free memory was 63.2MB in the beginning and 63.2MB in the end (delta: 27.1kB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 10 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 21 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.3s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 4.0s. Construction of modules took 0.8s. Büchi inclusion checks took 3.1s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 244 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 0/6 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 540 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 516 mSDsluCounter, 673 SdHoareTripleChecker+Invalid, 0.9s 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: 20ms 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-03-09 07:32:10,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:10,851 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:11,054 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2025-03-09 07:32:11,254 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-09 07:32:11,456 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE