./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_7-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 798a7b37 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-simple/fibo_7-2.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 40add90db9f8d501baba3978de407d6383e788a1a5fafc7225d7676b58d18c84 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-04 16:18:22,236 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-04 16:18:22,296 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-03-04 16:18:22,301 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-04 16:18:22,302 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-04 16:18:22,302 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-04 16:18:22,319 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-04 16:18:22,320 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-04 16:18:22,321 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-04 16:18:22,321 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-04 16:18:22,321 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-04 16:18:22,321 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-04 16:18:22,321 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-04 16:18:22,322 INFO L153 SettingsManager]: * Use SBE=true [2025-03-04 16:18:22,322 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-04 16:18:22,322 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-04 16:18:22,323 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-04 16:18:22,323 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-04 16:18:22,324 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-04 16:18:22,324 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-04 16:18:22,324 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-04 16:18:22,324 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-04 16:18:22,324 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-04 16:18:22,324 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-04 16:18:22,325 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-04 16:18:22,325 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-04 16:18:22,325 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 -> 40add90db9f8d501baba3978de407d6383e788a1a5fafc7225d7676b58d18c84 [2025-03-04 16:18:22,572 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-04 16:18:22,580 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-04 16:18:22,581 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-04 16:18:22,582 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-04 16:18:22,582 INFO L274 PluginConnector]: CDTParser initialized [2025-03-04 16:18:22,583 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_7-2.c [2025-03-04 16:18:23,795 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cb339af40/b025f364cb4942ac8436dc7227fa0831/FLAGb00badab5 [2025-03-04 16:18:23,991 INFO L384 CDTParser]: Found 1 translation units. [2025-03-04 16:18:23,991 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_7-2.c [2025-03-04 16:18:23,996 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cb339af40/b025f364cb4942ac8436dc7227fa0831/FLAGb00badab5 [2025-03-04 16:18:24,006 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cb339af40/b025f364cb4942ac8436dc7227fa0831 [2025-03-04 16:18:24,011 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-04 16:18:24,011 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-04 16:18:24,012 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-04 16:18:24,012 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-04 16:18:24,015 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-04 16:18:24,016 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,016 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 04.03 04:18:24, skipping insertion in model container [2025-03-04 16:18:24,016 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,024 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-04 16:18:24,111 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 16:18:24,118 INFO L200 MainTranslator]: Completed pre-run [2025-03-04 16:18:24,127 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 16:18:24,136 INFO L204 MainTranslator]: Completed translation [2025-03-04 16:18:24,137 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24 WrapperNode [2025-03-04 16:18:24,137 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-04 16:18:24,138 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-04 16:18:24,138 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-04 16:18:24,138 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-04 16:18:24,143 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,147 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,156 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2025-03-04 16:18:24,157 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-04 16:18:24,157 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-04 16:18:24,158 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-04 16:18:24,158 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-04 16:18:24,163 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,163 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,164 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,172 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-04 16:18:24,172 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,172 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,175 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,178 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,178 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,178 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,179 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-04 16:18:24,180 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-04 16:18:24,180 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-04 16:18:24,180 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-04 16:18:24,180 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (1/1) ... [2025-03-04 16:18:24,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,195 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,207 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-04 16:18:24,212 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-04 16:18:24,227 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-04 16:18:24,228 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-04 16:18:24,228 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-04 16:18:24,228 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-04 16:18:24,228 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2025-03-04 16:18:24,228 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2025-03-04 16:18:24,263 INFO L256 CfgBuilder]: Building ICFG [2025-03-04 16:18:24,264 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-04 16:18:24,313 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2025-03-04 16:18:24,319 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-04 16:18:24,320 INFO L307 CfgBuilder]: Performing block encoding [2025-03-04 16:18:24,325 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-04 16:18:24,326 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-04 16:18:24,326 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 04:18:24 BoogieIcfgContainer [2025-03-04 16:18:24,326 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-04 16:18:24,327 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-04 16:18:24,327 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-04 16:18:24,331 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-04 16:18:24,331 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-04 16:18:24,331 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 04.03 04:18:24" (1/3) ... [2025-03-04 16:18:24,332 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@262d633b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 04.03 04:18:24, skipping insertion in model container [2025-03-04 16:18:24,332 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-04 16:18:24,332 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:18:24" (2/3) ... [2025-03-04 16:18:24,332 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@262d633b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 04.03 04:18:24, skipping insertion in model container [2025-03-04 16:18:24,333 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-04 16:18:24,333 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 04:18:24" (3/3) ... [2025-03-04 16:18:24,334 INFO L363 chiAutomizerObserver]: Analyzing ICFG fibo_7-2.c [2025-03-04 16:18:24,366 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-04 16:18:24,366 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-04 16:18:24,366 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-04 16:18:24,366 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-04 16:18:24,367 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-04 16:18:24,367 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-04 16:18:24,367 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-04 16:18:24,367 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-04 16:18:24,370 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-04 16:18:24,384 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:24,385 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:24,385 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:24,388 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-04 16:18:24,388 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-04 16:18:24,388 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-04 16:18:24,389 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-04 16:18:24,390 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:24,390 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:24,390 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:24,390 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-04 16:18:24,390 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-04 16:18:24,394 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< [2025-03-04 16:18:24,394 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< [2025-03-04 16:18:24,397 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:24,398 INFO L85 PathProgramCache]: Analyzing trace with hash 39702, now seen corresponding path program 1 times [2025-03-04 16:18:24,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:24,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [832580485] [2025-03-04 16:18:24,403 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:24,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:24,444 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:18:24,455 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:18:24,455 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:24,455 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:24,456 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:24,458 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:18:24,461 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:18:24,461 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:24,461 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:24,470 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:24,472 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:24,472 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 1 times [2025-03-04 16:18:24,472 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:24,472 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1753824383] [2025-03-04 16:18:24,473 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:24,473 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:24,475 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:24,477 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:24,477 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:24,477 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:24,477 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:24,478 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:24,479 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:24,479 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:24,479 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:24,480 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:24,481 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:24,481 INFO L85 PathProgramCache]: Analyzing trace with hash -1988460259, now seen corresponding path program 1 times [2025-03-04 16:18:24,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:24,482 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [157856281] [2025-03-04 16:18:24,482 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:24,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:24,485 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-03-04 16:18:24,491 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-03-04 16:18:24,492 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:24,492 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:24,492 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:24,493 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 7 statements into 1 equivalence classes. [2025-03-04 16:18:24,501 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 7 of 7 statements. [2025-03-04 16:18:24,501 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:24,502 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:24,503 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:24,597 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:24,597 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:24,597 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:24,598 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:24,598 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:18:24,598 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,598 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:24,598 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:24,599 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration1_Loop [2025-03-04 16:18:24,599 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:24,599 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:24,608 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,614 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,616 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,619 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,621 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,685 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:24,685 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:18:24,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,686 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,688 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-04 16:18:24,689 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-04 16:18:24,692 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:24,692 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:24,705 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:24,705 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:24,713 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-04 16:18:24,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,715 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-04 16:18:24,717 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-04 16:18:24,718 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:24,718 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:24,729 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:24,729 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:24,735 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-04 16:18:24,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,737 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-04 16:18:24,741 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-04 16:18:24,741 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:24,741 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:24,752 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:24,753 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:24,758 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-04 16:18:24,758 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,758 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,760 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-04 16:18:24,761 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-04 16:18:24,762 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:24,762 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:24,773 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:24,773 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:24,780 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-04 16:18:24,782 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,782 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,784 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-04 16:18:24,787 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-04 16:18:24,788 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:24,788 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:24,808 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-04 16:18:24,808 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,809 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,811 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-04 16:18:24,812 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-04 16:18:24,813 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:18:24,813 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:24,856 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:18:24,860 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-04 16:18:24,861 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:24,861 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:24,861 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:24,861 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:24,861 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:18:24,861 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,861 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:24,861 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:24,861 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration1_Loop [2025-03-04 16:18:24,861 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:24,861 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:24,862 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,866 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,870 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,873 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,875 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:24,925 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:24,928 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:18:24,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,933 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-04 16:18:24,935 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-04 16:18:24,936 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-04 16:18:24,948 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:24,948 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:24,949 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:24,949 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:24,949 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:24,952 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:24,952 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:24,954 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:24,959 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-04 16:18:24,960 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,960 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,962 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-04 16:18:24,962 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-04 16:18:24,963 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-04 16:18:24,973 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:24,973 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:24,973 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:24,973 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:24,973 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:24,974 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:24,974 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:24,976 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:24,981 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-04 16:18:24,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:24,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:24,983 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-04 16:18:24,985 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-04 16:18:24,986 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-04 16:18:24,995 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:24,996 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:24,996 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:24,996 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:24,996 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:24,996 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:24,996 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:24,998 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:25,003 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2025-03-04 16:18:25,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,004 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,006 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-04 16:18:25,007 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-04 16:18:25,008 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-04 16:18:25,017 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:25,017 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:25,018 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:25,018 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:25,018 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:25,018 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:25,018 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:25,019 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:25,025 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-04 16:18:25,025 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,025 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,027 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-04 16:18:25,028 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-04 16:18:25,029 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-04 16:18:25,039 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:25,039 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:25,039 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:25,039 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:25,039 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:25,040 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:25,040 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:25,044 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:18:25,047 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:18:25,049 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-04 16:18:25,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,052 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-04 16:18:25,054 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-04 16:18:25,055 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:18:25,055 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:18:25,056 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:18:25,056 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2025-03-04 16:18:25,062 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-04 16:18:25,065 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:18:25,085 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:25,093 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:18:25,100 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:18:25,100 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,100 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:25,101 INFO L256 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-04 16:18:25,102 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:25,116 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:25,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:25,124 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,124 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:25,125 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:18:25,126 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:25,159 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-04 16:18:25,179 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-04 16:18:25,181 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 16:18:25,241 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:25,272 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 41 states and 54 transitions. Complement of second has 16 states. [2025-03-04 16:18:25,274 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-04 16:18:25,277 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-04 16:18:25,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2025-03-04 16:18:25,283 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2025-03-04 16:18:25,284 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:25,287 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2025-03-04 16:18:25,287 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:25,287 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2025-03-04 16:18:25,287 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:25,288 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2025-03-04 16:18:25,290 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:25,293 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2025-03-04 16:18:25,293 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2025-03-04 16:18:25,294 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2025-03-04 16:18:25,294 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2025-03-04 16:18:25,294 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:25,295 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2025-03-04 16:18:25,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2025-03-04 16:18:25,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2025-03-04 16:18:25,311 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-04 16:18:25,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2025-03-04 16:18:25,313 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-03-04 16:18:25,313 INFO L432 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-03-04 16:18:25,313 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-04 16:18:25,313 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2025-03-04 16:18:25,313 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:25,313 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:25,313 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:25,314 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:25,314 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:25,315 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#27#return;" [2025-03-04 16:18:25,315 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#27#return;" [2025-03-04 16:18:25,315 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:25,315 INFO L85 PathProgramCache]: Analyzing trace with hash 1475604923, now seen corresponding path program 1 times [2025-03-04 16:18:25,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:25,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642659379] [2025-03-04 16:18:25,315 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:25,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:25,319 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-04 16:18:25,323 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-04 16:18:25,324 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,324 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:25,401 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-04 16:18:25,402 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:25,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [642659379] [2025-03-04 16:18:25,402 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [642659379] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 16:18:25,402 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 16:18:25,402 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-04 16:18:25,403 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1637311176] [2025-03-04 16:18:25,403 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 16:18:25,404 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-04 16:18:25,404 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:25,405 INFO L85 PathProgramCache]: Analyzing trace with hash 93365724, now seen corresponding path program 1 times [2025-03-04 16:18:25,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:25,405 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [44863818] [2025-03-04 16:18:25,405 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:25,405 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:25,410 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-04 16:18:25,416 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-04 16:18:25,417 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,418 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:25,458 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-04 16:18:25,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:25,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [44863818] [2025-03-04 16:18:25,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [44863818] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 16:18:25,459 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 16:18:25,459 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-04 16:18:25,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1104867810] [2025-03-04 16:18:25,459 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 16:18:25,459 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-04 16:18:25,459 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:18:25,460 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-04 16:18:25,461 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-03-04 16:18:25,462 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-04 16:18:25,520 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:18:25,521 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2025-03-04 16:18:25,521 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2025-03-04 16:18:25,522 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:25,522 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2025-03-04 16:18:25,522 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2025-03-04 16:18:25,522 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2025-03-04 16:18:25,522 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2025-03-04 16:18:25,522 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:25,522 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-04 16:18:25,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2025-03-04 16:18:25,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2025-03-04 16:18:25,526 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-04 16:18:25,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2025-03-04 16:18:25,528 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-04 16:18:25,528 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-04 16:18:25,529 INFO L432 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-04 16:18:25,529 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-04 16:18:25,529 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2025-03-04 16:18:25,530 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:25,530 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:25,530 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:25,531 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:25,531 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:25,532 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" [2025-03-04 16:18:25,532 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" [2025-03-04 16:18:25,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:25,533 INFO L85 PathProgramCache]: Analyzing trace with hash -1500686953, now seen corresponding path program 1 times [2025-03-04 16:18:25,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:25,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556950403] [2025-03-04 16:18:25,533 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:25,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:25,536 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-04 16:18:25,540 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-04 16:18:25,542 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,542 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:25,604 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-04 16:18:25,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:25,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1556950403] [2025-03-04 16:18:25,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1556950403] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:25,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1402354774] [2025-03-04 16:18:25,605 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:25,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:25,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,607 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-04 16:18:25,609 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-04 16:18:25,629 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-04 16:18:25,636 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-04 16:18:25,636 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,636 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:25,636 INFO L256 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-04 16:18:25,637 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:25,659 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-04 16:18:25,660 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:25,736 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-04 16:18:25,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1402354774] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:25,737 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:25,737 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2025-03-04 16:18:25,737 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [504539528] [2025-03-04 16:18:25,737 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:25,737 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-04 16:18:25,737 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:25,738 INFO L85 PathProgramCache]: Analyzing trace with hash -1400429162, now seen corresponding path program 1 times [2025-03-04 16:18:25,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:25,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [492250325] [2025-03-04 16:18:25,738 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:25,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:25,741 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-04 16:18:25,745 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-04 16:18:25,746 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,746 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:25,746 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:25,747 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-04 16:18:25,748 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-04 16:18:25,750 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:25,750 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:25,751 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:25,842 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:25,843 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:25,843 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:25,843 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:25,843 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:18:25,843 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,843 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:25,843 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:25,843 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration3_Loop [2025-03-04 16:18:25,843 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:25,843 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:25,844 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:25,846 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:25,848 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:25,856 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:25,860 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:25,898 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:25,898 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:18:25,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,898 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,900 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-04 16:18:25,901 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-04 16:18:25,901 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:25,901 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:25,912 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:25,912 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#in~n=2} Honda state: {fibo_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:25,917 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-04 16:18:25,918 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,918 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,919 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-04 16:18:25,920 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-04 16:18:25,921 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:25,921 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:25,932 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:25,932 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:25,938 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-04 16:18:25,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,940 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-04 16:18:25,941 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-04 16:18:25,943 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:25,943 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:25,953 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:25,953 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:25,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:25,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,960 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-04 16:18:25,961 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-04 16:18:25,962 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:25,962 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:25,972 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:25,972 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:25,977 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-04 16:18:25,977 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,977 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,978 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-04 16:18:25,979 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-04 16:18:25,980 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:25,980 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:25,995 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-04 16:18:25,996 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:25,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:25,997 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-04 16:18:25,998 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-04 16:18:25,999 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:18:25,999 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:26,010 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:18:26,017 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-04 16:18:26,017 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:26,017 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:26,017 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:26,017 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:26,017 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:18:26,017 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,017 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:26,017 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:26,017 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration3_Loop [2025-03-04 16:18:26,017 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:26,017 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:26,018 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:26,021 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:26,024 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:26,025 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:26,027 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:26,060 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:26,060 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:18:26,060 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,060 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,062 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:18:26,063 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2025-03-04 16:18:26,065 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-04 16:18:26,075 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:26,075 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:26,075 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:26,075 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:26,075 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:26,076 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:26,076 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:26,077 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:26,083 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2025-03-04 16:18:26,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,085 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-04 16:18:26,086 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-04 16:18:26,086 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-04 16:18:26,096 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:26,096 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:26,096 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:26,096 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:26,096 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:26,097 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:26,097 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:26,098 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:26,104 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2025-03-04 16:18:26,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,106 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-04 16:18:26,108 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-04 16:18:26,109 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-04 16:18:26,118 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:26,118 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:26,119 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:26,119 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:26,119 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:26,119 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:26,119 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:26,120 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:26,125 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:26,125 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,126 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,127 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-04 16:18:26,128 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-04 16:18:26,129 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-04 16:18:26,138 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:26,138 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:26,138 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:26,138 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:26,138 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:26,139 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:26,139 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:26,140 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:26,145 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2025-03-04 16:18:26,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,147 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-04 16:18:26,148 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-04 16:18:26,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-04 16:18:26,158 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:26,158 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:26,158 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:26,158 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:26,158 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:26,159 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:26,159 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:26,160 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:18:26,162 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:18:26,162 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-04 16:18:26,163 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:26,163 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,165 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-04 16:18:26,166 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-04 16:18:26,167 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:18:26,167 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:18:26,167 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:18:26,167 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2025-03-04 16:18:26,173 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-04 16:18:26,174 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:18:26,183 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:26,188 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-04 16:18:26,202 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-04 16:18:26,203 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:26,203 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:26,203 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-04 16:18:26,204 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:26,287 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2025-03-04 16:18:26,299 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-04 16:18:26,310 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-04 16:18:26,310 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:26,310 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:26,311 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-04 16:18:26,313 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:26,399 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-04 16:18:26,399 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-04 16:18:26,400 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-04 16:18:26,575 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-04 16:18:26,575 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-04 16:18:26,576 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-04 16:18:26,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2025-03-04 16:18:26,576 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2025-03-04 16:18:26,577 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:26,577 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2025-03-04 16:18:26,577 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:26,577 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2025-03-04 16:18:26,577 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:26,577 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2025-03-04 16:18:26,581 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-04 16:18:26,583 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2025-03-04 16:18:26,584 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2025-03-04 16:18:26,584 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2025-03-04 16:18:26,584 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2025-03-04 16:18:26,584 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:26,584 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2025-03-04 16:18:26,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2025-03-04 16:18:26,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2025-03-04 16:18:26,590 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-04 16:18:26,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2025-03-04 16:18:26,592 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2025-03-04 16:18:26,592 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:18:26,592 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-04 16:18:26,592 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-04 16:18:26,592 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-04 16:18:26,681 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:18:26,682 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2025-03-04 16:18:26,682 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2025-03-04 16:18:26,684 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-04 16:18:26,686 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2025-03-04 16:18:26,686 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2025-03-04 16:18:26,686 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2025-03-04 16:18:26,686 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2025-03-04 16:18:26,686 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:26,686 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2025-03-04 16:18:26,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2025-03-04 16:18:26,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2025-03-04 16:18:26,692 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-04 16:18:26,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2025-03-04 16:18:26,693 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2025-03-04 16:18:26,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-04 16:18:26,694 INFO L432 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2025-03-04 16:18:26,694 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-04 16:18:26,694 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2025-03-04 16:18:26,695 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-04 16:18:26,695 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:26,695 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:26,696 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:26,696 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-03-04 16:18:26,696 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" [2025-03-04 16:18:26,696 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" [2025-03-04 16:18:26,696 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:26,696 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 1 times [2025-03-04 16:18:26,696 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:26,696 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [266791468] [2025-03-04 16:18:26,696 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:26,696 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:26,700 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 16:18:26,706 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:18:26,706 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:26,706 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:26,842 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-04 16:18:26,842 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:26,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [266791468] [2025-03-04 16:18:26,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [266791468] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:26,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1663613993] [2025-03-04 16:18:26,843 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:26,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:26,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:26,844 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:18:26,845 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (27)] Waiting until timeout for monitored process [2025-03-04 16:18:26,862 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 16:18:26,870 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:18:26,870 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:26,870 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:26,871 INFO L256 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-04 16:18:26,872 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:26,914 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-04 16:18:26,914 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:27,116 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-04 16:18:27,116 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1663613993] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:27,116 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:27,116 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 12] total 16 [2025-03-04 16:18:27,116 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [936446625] [2025-03-04 16:18:27,116 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:27,117 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-04 16:18:27,117 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:27,117 INFO L85 PathProgramCache]: Analyzing trace with hash -1547808212, now seen corresponding path program 1 times [2025-03-04 16:18:27,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:27,117 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [911354875] [2025-03-04 16:18:27,117 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:27,117 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:27,120 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-04 16:18:27,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-04 16:18:27,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:27,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:27,167 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-03-04 16:18:27,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:27,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [911354875] [2025-03-04 16:18:27,167 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [911354875] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:27,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [425546235] [2025-03-04 16:18:27,167 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:27,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:27,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:27,170 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:18:27,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (28)] Waiting until timeout for monitored process [2025-03-04 16:18:27,189 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-04 16:18:27,193 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-04 16:18:27,193 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:27,193 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:27,195 INFO L256 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-04 16:18:27,196 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:27,217 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-03-04 16:18:27,218 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:27,334 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-03-04 16:18:27,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [425546235] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:27,334 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:27,334 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2025-03-04 16:18:27,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [380109628] [2025-03-04 16:18:27,334 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:27,334 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-04 16:18:27,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:18:27,335 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-04 16:18:27,335 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2025-03-04 16:18:27,335 INFO L87 Difference]: Start difference. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 9 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:27,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:18:27,435 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2025-03-04 16:18:27,435 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2025-03-04 16:18:27,436 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:27,437 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2025-03-04 16:18:27,437 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2025-03-04 16:18:27,437 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2025-03-04 16:18:27,437 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2025-03-04 16:18:27,437 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:27,437 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2025-03-04 16:18:27,437 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2025-03-04 16:18:27,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2025-03-04 16:18:27,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2025-03-04 16:18:27,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2025-03-04 16:18:27,446 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2025-03-04 16:18:27,448 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-04 16:18:27,448 INFO L432 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2025-03-04 16:18:27,448 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-04 16:18:27,448 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2025-03-04 16:18:27,449 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:27,449 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:27,449 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:27,450 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:27,450 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2025-03-04 16:18:27,450 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" [2025-03-04 16:18:27,450 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" [2025-03-04 16:18:27,451 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:27,451 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 2 times [2025-03-04 16:18:27,451 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:27,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1862764751] [2025-03-04 16:18:27,451 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:18:27,451 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:27,455 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-04 16:18:27,458 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:18:27,459 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:18:27,459 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:27,575 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-04 16:18:27,575 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:27,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1862764751] [2025-03-04 16:18:27,575 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1862764751] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:27,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1475274463] [2025-03-04 16:18:27,576 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:18:27,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:27,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:27,578 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:18:27,583 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Waiting until timeout for monitored process [2025-03-04 16:18:27,606 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-04 16:18:27,614 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:18:27,614 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:18:27,614 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:27,615 INFO L256 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-04 16:18:27,616 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:27,647 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-04 16:18:27,647 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:27,844 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-04 16:18:27,845 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1475274463] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:27,845 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:27,845 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 12] total 16 [2025-03-04 16:18:27,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [352628338] [2025-03-04 16:18:27,845 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:27,845 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-04 16:18:27,846 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:27,846 INFO L85 PathProgramCache]: Analyzing trace with hash -2065716406, now seen corresponding path program 1 times [2025-03-04 16:18:27,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:27,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [897346067] [2025-03-04 16:18:27,847 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:27,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:27,849 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-04 16:18:27,854 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-04 16:18:27,855 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:27,855 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:27,938 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 29 proven. 7 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2025-03-04 16:18:27,939 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:27,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [897346067] [2025-03-04 16:18:27,939 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [897346067] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:27,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [908221394] [2025-03-04 16:18:27,939 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:18:27,939 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:27,939 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:27,941 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:18:27,943 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Waiting until timeout for monitored process [2025-03-04 16:18:27,963 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-04 16:18:27,971 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-04 16:18:27,971 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:27,971 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:27,972 INFO L256 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-04 16:18:27,973 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:28,011 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2025-03-04 16:18:28,012 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:28,221 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 13 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-04 16:18:28,223 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [908221394] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:28,223 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:28,223 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 14 [2025-03-04 16:18:28,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1825339702] [2025-03-04 16:18:28,223 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:28,224 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-04 16:18:28,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:18:28,224 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-04 16:18:28,224 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2025-03-04 16:18:28,225 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 17 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 9 states have call successors, (10), 5 states have call predecessors, (10), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-04 16:18:28,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:18:28,431 INFO L93 Difference]: Finished difference Result 82 states and 97 transitions. [2025-03-04 16:18:28,431 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 82 states and 97 transitions. [2025-03-04 16:18:28,432 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:28,433 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 82 states to 75 states and 90 transitions. [2025-03-04 16:18:28,434 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 56 [2025-03-04 16:18:28,434 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 56 [2025-03-04 16:18:28,434 INFO L73 IsDeterministic]: Start isDeterministic. Operand 75 states and 90 transitions. [2025-03-04 16:18:28,434 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:28,434 INFO L218 hiAutomatonCegarLoop]: Abstraction has 75 states and 90 transitions. [2025-03-04 16:18:28,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states and 90 transitions. [2025-03-04 16:18:28,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2025-03-04 16:18:28,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 48 states have (on average 1.0625) internal successors, (51), 50 states have internal predecessors, (51), 17 states have call successors, (17), 10 states have call predecessors, (17), 10 states have return successors, (22), 14 states have call predecessors, (22), 14 states have call successors, (22) [2025-03-04 16:18:28,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 90 transitions. [2025-03-04 16:18:28,443 INFO L240 hiAutomatonCegarLoop]: Abstraction has 75 states and 90 transitions. [2025-03-04 16:18:28,444 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-04 16:18:28,444 INFO L432 stractBuchiCegarLoop]: Abstraction has 75 states and 90 transitions. [2025-03-04 16:18:28,446 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-04 16:18:28,447 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 75 states and 90 transitions. [2025-03-04 16:18:28,447 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2025-03-04 16:18:28,447 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:28,447 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:28,452 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 7, 6, 6, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:18:28,452 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2025-03-04 16:18:28,452 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" [2025-03-04 16:18:28,452 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" [2025-03-04 16:18:28,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:28,452 INFO L85 PathProgramCache]: Analyzing trace with hash -35507947, now seen corresponding path program 3 times [2025-03-04 16:18:28,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:28,453 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1184118277] [2025-03-04 16:18:28,453 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-04 16:18:28,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:28,460 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 40 statements into 8 equivalence classes. [2025-03-04 16:18:28,469 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) and asserted 40 of 40 statements. [2025-03-04 16:18:28,470 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2025-03-04 16:18:28,470 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:28,470 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:28,474 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-04 16:18:28,481 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-04 16:18:28,481 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:28,481 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:28,483 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:28,487 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:28,487 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 2 times [2025-03-04 16:18:28,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:28,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1519611124] [2025-03-04 16:18:28,487 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:18:28,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:28,489 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 22 statements into 2 equivalence classes. [2025-03-04 16:18:28,490 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:18:28,490 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:18:28,490 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:28,490 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:28,491 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:18:28,492 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:18:28,492 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:28,492 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:28,494 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:28,494 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:28,494 INFO L85 PathProgramCache]: Analyzing trace with hash 103714372, now seen corresponding path program 4 times [2025-03-04 16:18:28,494 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:28,494 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [611965853] [2025-03-04 16:18:28,494 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-04 16:18:28,494 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:28,497 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 62 statements into 2 equivalence classes. [2025-03-04 16:18:28,501 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 61 of 62 statements. [2025-03-04 16:18:28,502 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-04 16:18:28,502 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:28,683 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 70 proven. 100 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2025-03-04 16:18:28,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:28,684 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [611965853] [2025-03-04 16:18:28,684 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [611965853] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:28,684 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1532866870] [2025-03-04 16:18:28,684 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-04 16:18:28,684 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:28,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:28,686 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:18:28,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Waiting until timeout for monitored process [2025-03-04 16:18:28,709 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 62 statements into 2 equivalence classes. [2025-03-04 16:18:28,719 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 61 of 62 statements. [2025-03-04 16:18:28,720 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-04 16:18:28,720 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:28,720 INFO L256 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-04 16:18:28,722 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:28,777 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 88 proven. 103 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-04 16:18:28,777 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:28,928 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 88 proven. 103 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-04 16:18:28,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1532866870] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:28,929 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:28,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 16] total 19 [2025-03-04 16:18:28,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1956318801] [2025-03-04 16:18:28,929 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:29,063 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:29,064 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:29,064 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:29,064 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:29,064 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:18:29,064 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:29,064 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:29,064 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:29,064 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration6_Loop [2025-03-04 16:18:29,064 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:29,064 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:29,065 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,069 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,071 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,075 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,080 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,111 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:29,111 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:18:29,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:29,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:29,118 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-04 16:18:29,119 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-04 16:18:29,120 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:29,120 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:29,139 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-04 16:18:29,139 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:29,139 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:29,141 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-04 16:18:29,143 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-04 16:18:29,144 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:18:29,144 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:29,156 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:18:29,162 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-04 16:18:29,162 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:29,162 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:29,162 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:29,162 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:29,162 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:18:29,162 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:29,162 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:29,163 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:29,163 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration6_Loop [2025-03-04 16:18:29,163 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:29,163 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:29,163 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,167 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,169 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,171 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,172 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:29,195 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:29,195 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:18:29,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:29,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:29,198 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:18:29,199 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2025-03-04 16:18:29,201 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-04 16:18:29,211 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:29,211 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:29,211 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:29,211 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:29,211 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:29,212 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:29,212 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:29,214 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:18:29,215 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-04 16:18:29,215 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-04 16:18:29,215 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:29,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:29,217 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-04 16:18:29,218 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-04 16:18:29,219 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:18:29,219 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:18:29,219 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:18:29,219 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2025-03-04 16:18:29,224 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2025-03-04 16:18:29,225 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:18:29,234 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:29,245 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-04 16:18:29,270 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-04 16:18:29,283 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-04 16:18:29,283 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:29,283 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:29,284 INFO L256 TraceCheckSpWp]: Trace formula consists of 326 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-04 16:18:29,286 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:29,453 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:18:29,467 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:18:29,467 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:29,467 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:29,468 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-04 16:18:29,469 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:29,572 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-04 16:18:29,573 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:18:29,573 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 75 states and 90 transitions. cyclomatic complexity: 17 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:18:29,648 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 75 states and 90 transitions. cyclomatic complexity: 17. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 82 states and 97 transitions. Complement of second has 11 states. [2025-03-04 16:18:29,648 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-04 16:18:29,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:18:29,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2025-03-04 16:18:29,650 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 40 letters. Loop has 22 letters. [2025-03-04 16:18:29,650 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:29,650 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:18:29,658 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:29,669 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-04 16:18:29,695 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-04 16:18:29,695 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:29,695 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:29,696 INFO L256 TraceCheckSpWp]: Trace formula consists of 326 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-04 16:18:29,698 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:29,833 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:18:29,860 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:18:29,860 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:29,860 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:29,864 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-04 16:18:29,865 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:29,950 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-04 16:18:29,951 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:18:29,951 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 75 states and 90 transitions. cyclomatic complexity: 17 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:18:30,020 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 75 states and 90 transitions. cyclomatic complexity: 17. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 82 states and 97 transitions. Complement of second has 11 states. [2025-03-04 16:18:30,020 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-04 16:18:30,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:18:30,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2025-03-04 16:18:30,021 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 40 letters. Loop has 22 letters. [2025-03-04 16:18:30,021 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:30,021 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:18:30,034 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:30,045 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-04 16:18:30,071 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-04 16:18:30,071 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:30,071 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:30,073 INFO L256 TraceCheckSpWp]: Trace formula consists of 326 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-04 16:18:30,074 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:30,208 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:18:30,221 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:18:30,221 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:30,222 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:30,223 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-04 16:18:30,224 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:30,311 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-04 16:18:30,312 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:18:30,312 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 75 states and 90 transitions. cyclomatic complexity: 17 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:18:30,517 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 75 states and 90 transitions. cyclomatic complexity: 17. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 434 states and 561 transitions. Complement of second has 132 states. [2025-03-04 16:18:30,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2025-03-04 16:18:30,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:18:30,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2025-03-04 16:18:30,520 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 40 letters. Loop has 22 letters. [2025-03-04 16:18:30,522 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:30,522 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 62 letters. Loop has 22 letters. [2025-03-04 16:18:30,522 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:30,522 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 40 letters. Loop has 44 letters. [2025-03-04 16:18:30,525 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:30,525 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 434 states and 561 transitions. [2025-03-04 16:18:30,533 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2025-03-04 16:18:30,540 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 434 states to 291 states and 399 transitions. [2025-03-04 16:18:30,541 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 132 [2025-03-04 16:18:30,541 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 150 [2025-03-04 16:18:30,541 INFO L73 IsDeterministic]: Start isDeterministic. Operand 291 states and 399 transitions. [2025-03-04 16:18:30,543 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:30,544 INFO L218 hiAutomatonCegarLoop]: Abstraction has 291 states and 399 transitions. [2025-03-04 16:18:30,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 291 states and 399 transitions. [2025-03-04 16:18:30,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 291 to 242. [2025-03-04 16:18:30,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 242 states, 148 states have (on average 1.114864864864865) internal successors, (165), 158 states have internal predecessors, (165), 55 states have call successors, (59), 30 states have call predecessors, (59), 39 states have return successors, (94), 53 states have call predecessors, (94), 49 states have call successors, (94) [2025-03-04 16:18:30,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 242 states to 242 states and 318 transitions. [2025-03-04 16:18:30,569 INFO L240 hiAutomatonCegarLoop]: Abstraction has 242 states and 318 transitions. [2025-03-04 16:18:30,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:18:30,569 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-04 16:18:30,570 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=269, Unknown=0, NotChecked=0, Total=342 [2025-03-04 16:18:30,570 INFO L87 Difference]: Start difference. First operand 242 states and 318 transitions. Second operand has 19 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 13 states have internal predecessors, (36), 10 states have call successors, (13), 7 states have call predecessors, (13), 2 states have return successors, (7), 4 states have call predecessors, (7), 5 states have call successors, (7) [2025-03-04 16:18:30,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:18:30,808 INFO L93 Difference]: Finished difference Result 248 states and 305 transitions. [2025-03-04 16:18:30,808 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 248 states and 305 transitions. [2025-03-04 16:18:30,810 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-04 16:18:30,813 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 248 states to 225 states and 274 transitions. [2025-03-04 16:18:30,813 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 109 [2025-03-04 16:18:30,814 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 119 [2025-03-04 16:18:30,814 INFO L73 IsDeterministic]: Start isDeterministic. Operand 225 states and 274 transitions. [2025-03-04 16:18:30,814 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:18:30,814 INFO L218 hiAutomatonCegarLoop]: Abstraction has 225 states and 274 transitions. [2025-03-04 16:18:30,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states and 274 transitions. [2025-03-04 16:18:30,821 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 218. [2025-03-04 16:18:30,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 136 states have (on average 1.0735294117647058) internal successors, (146), 143 states have internal predecessors, (146), 49 states have call successors, (52), 29 states have call predecessors, (52), 33 states have return successors, (69), 45 states have call predecessors, (69), 41 states have call successors, (69) [2025-03-04 16:18:30,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 267 transitions. [2025-03-04 16:18:30,825 INFO L240 hiAutomatonCegarLoop]: Abstraction has 218 states and 267 transitions. [2025-03-04 16:18:30,825 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-04 16:18:30,826 INFO L432 stractBuchiCegarLoop]: Abstraction has 218 states and 267 transitions. [2025-03-04 16:18:30,826 INFO L338 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2025-03-04 16:18:30,826 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 218 states and 267 transitions. [2025-03-04 16:18:30,827 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-04 16:18:30,827 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:18:30,827 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:18:30,828 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [11, 9, 8, 8, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1] [2025-03-04 16:18:30,828 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2025-03-04 16:18:30,828 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(11, 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 := 7;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#25#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#27#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< [2025-03-04 16:18:30,828 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< [2025-03-04 16:18:30,829 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:30,829 INFO L85 PathProgramCache]: Analyzing trace with hash 90660880, now seen corresponding path program 5 times [2025-03-04 16:18:30,829 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:30,829 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1578242122] [2025-03-04 16:18:30,830 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-04 16:18:30,830 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:30,835 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 57 statements into 9 equivalence classes. [2025-03-04 16:18:30,838 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 33 of 57 statements. [2025-03-04 16:18:30,839 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-04 16:18:30,839 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:30,904 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 103 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2025-03-04 16:18:30,905 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:18:30,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1578242122] [2025-03-04 16:18:30,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1578242122] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:18:30,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [872806675] [2025-03-04 16:18:30,905 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-04 16:18:30,905 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:18:30,905 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:30,907 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:18:30,910 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (36)] Waiting until timeout for monitored process [2025-03-04 16:18:30,938 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 57 statements into 9 equivalence classes. [2025-03-04 16:18:30,945 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 33 of 57 statements. [2025-03-04 16:18:30,945 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-04 16:18:30,945 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:30,945 INFO L256 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:18:30,947 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:30,986 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 103 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2025-03-04 16:18:30,987 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:18:31,124 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 103 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2025-03-04 16:18:31,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [872806675] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:18:31,124 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:18:31,124 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 14 [2025-03-04 16:18:31,124 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [901799661] [2025-03-04 16:18:31,124 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:18:31,125 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-04 16:18:31,125 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:31,125 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 2 times [2025-03-04 16:18:31,125 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:18:31,125 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [333642402] [2025-03-04 16:18:31,125 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:18:31,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:18:31,127 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:31,127 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:31,127 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-04 16:18:31,127 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:31,127 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:18:31,128 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:31,128 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:31,128 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:31,128 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:18:31,129 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:18:31,161 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:31,161 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:31,161 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:31,161 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:31,161 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:18:31,161 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,161 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:31,161 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:31,161 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration7_Loop [2025-03-04 16:18:31,161 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:31,161 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:31,162 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,163 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,164 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,165 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,166 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,205 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:31,205 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:18:31,205 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,207 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-04 16:18:31,208 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-04 16:18:31,209 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:31,209 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:31,220 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:31,220 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:31,225 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2025-03-04 16:18:31,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,227 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-04 16:18:31,228 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-04 16:18:31,228 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:31,228 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:31,239 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:31,239 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:31,244 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2025-03-04 16:18:31,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,246 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-04 16:18:31,247 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-04 16:18:31,248 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:31,248 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:31,258 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:31,258 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:31,263 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-04 16:18:31,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,265 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:18:31,266 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2025-03-04 16:18:31,266 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:31,266 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:31,277 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:18:31,277 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:18:31,282 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Ended with exit code 0 [2025-03-04 16:18:31,282 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,284 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-04 16:18:31,285 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-04 16:18:31,286 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:18:31,286 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:31,301 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-04 16:18:31,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,303 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-04 16:18:31,304 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-04 16:18:31,305 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:18:31,305 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:18:31,346 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:18:31,350 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Ended with exit code 0 [2025-03-04 16:18:31,350 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:18:31,350 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:18:31,350 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:18:31,350 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:18:31,350 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:18:31,350 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,350 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:18:31,350 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:18:31,350 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration7_Loop [2025-03-04 16:18:31,350 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:18:31,351 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:18:31,351 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,353 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,354 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,355 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,356 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:18:31,382 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:18:31,382 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:18:31,382 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,382 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,386 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-04 16:18:31,388 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-04 16:18:31,389 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-04 16:18:31,398 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:31,398 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:31,398 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:31,398 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:31,399 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:31,399 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:31,399 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:31,400 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:31,405 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-04 16:18:31,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,407 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-04 16:18:31,408 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-04 16:18:31,409 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-04 16:18:31,419 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:31,419 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:31,419 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:31,419 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:31,419 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:31,419 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:31,419 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:31,420 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:31,425 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-04 16:18:31,426 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,426 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,428 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-04 16:18:31,429 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-04 16:18:31,430 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-04 16:18:31,439 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:31,440 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:31,440 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:31,440 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:31,440 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:31,440 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:31,440 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:31,441 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:31,446 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:31,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,448 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-04 16:18:31,448 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-04 16:18:31,449 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-04 16:18:31,459 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:31,459 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:31,459 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:31,459 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:31,459 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:31,459 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:31,459 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:31,460 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:18:31,465 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-04 16:18:31,465 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,465 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,467 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-04 16:18:31,467 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-04 16:18:31,468 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-04 16:18:31,478 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:18:31,478 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:18:31,478 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:18:31,478 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:18:31,478 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:18:31,479 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:18:31,479 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:18:31,480 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:18:31,482 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:18:31,482 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-04 16:18:31,482 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:18:31,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:18:31,484 INFO L229 MonitoredProcess]: Starting monitored process 48 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-04 16:18:31,484 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Waiting until timeout for monitored process [2025-03-04 16:18:31,485 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:18:31,485 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:18:31,485 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:18:31,485 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2025-03-04 16:18:31,490 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-04 16:18:31,491 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:18:31,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:31,516 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-04 16:18:31,557 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-04 16:18:31,557 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:31,557 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:31,559 INFO L256 TraceCheckSpWp]: Trace formula consists of 475 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-04 16:18:31,561 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:31,775 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:31,778 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:31,778 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:31,778 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:31,779 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:18:31,780 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:31,797 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-04 16:18:31,798 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-04 16:18:31,798 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 218 states and 267 transitions. cyclomatic complexity: 52 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:31,841 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 218 states and 267 transitions. cyclomatic complexity: 52. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 234 states and 283 transitions. Complement of second has 15 states. [2025-03-04 16:18:31,841 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-04 16:18:31,842 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:31,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2025-03-04 16:18:31,842 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2025-03-04 16:18:31,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:31,843 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:18:31,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:31,871 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-04 16:18:31,907 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-04 16:18:31,907 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:31,908 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:31,909 INFO L256 TraceCheckSpWp]: Trace formula consists of 475 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-04 16:18:31,911 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:32,030 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Ended with exit code 0 [2025-03-04 16:18:32,122 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:32,126 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:32,126 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:32,126 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:32,126 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:18:32,126 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:32,142 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-04 16:18:32,143 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-04 16:18:32,143 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 218 states and 267 transitions. cyclomatic complexity: 52 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:32,180 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 218 states and 267 transitions. cyclomatic complexity: 52. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 234 states and 283 transitions. Complement of second has 15 states. [2025-03-04 16:18:32,181 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-04 16:18:32,182 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:32,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2025-03-04 16:18:32,182 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2025-03-04 16:18:32,182 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:32,182 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:18:32,191 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:18:32,205 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-04 16:18:32,241 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-04 16:18:32,241 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:32,241 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:32,243 INFO L256 TraceCheckSpWp]: Trace formula consists of 475 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-04 16:18:32,244 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:32,435 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 4 statements into 1 equivalence classes. [2025-03-04 16:18:32,438 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 4 of 4 statements. [2025-03-04 16:18:32,439 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:18:32,439 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:18:32,439 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:18:32,439 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:18:32,459 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-04 16:18:32,460 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-04 16:18:32,460 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 218 states and 267 transitions. cyclomatic complexity: 52 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:32,516 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 218 states and 267 transitions. cyclomatic complexity: 52. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 283 states and 332 transitions. Complement of second has 19 states. [2025-03-04 16:18:32,516 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-04 16:18:32,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-04 16:18:32,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2025-03-04 16:18:32,517 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 57 letters. Loop has 4 letters. [2025-03-04 16:18:32,517 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:32,517 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 4 letters. [2025-03-04 16:18:32,517 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:32,517 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 57 letters. Loop has 8 letters. [2025-03-04 16:18:32,518 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:18:32,518 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 283 states and 332 transitions. [2025-03-04 16:18:32,522 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-04 16:18:32,522 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 283 states to 0 states and 0 transitions. [2025-03-04 16:18:32,522 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-04 16:18:32,522 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-04 16:18:32,522 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-04 16:18:32,522 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-04 16:18:32,522 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:18:32,522 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:18:32,523 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-04 16:18:32,523 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=130, Unknown=0, NotChecked=0, Total=182 [2025-03-04 16:18:32,523 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2025-03-04 16:18:32,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:18:32,523 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-04 16:18:32,523 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-04 16:18:32,523 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-04 16:18:32,523 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-04 16:18:32,523 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:18:32,523 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-04 16:18:32,524 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:18:32,524 INFO L338 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2025-03-04 16:18:32,524 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-04 16:18:32,524 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-04 16:18:32,524 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-04 16:18:32,534 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 04.03 04:18:32 BoogieIcfgContainer [2025-03-04 16:18:32,534 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-04 16:18:32,535 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-04 16:18:32,535 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-04 16:18:32,535 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-04 16:18:32,535 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 04:18:24" (3/4) ... [2025-03-04 16:18:32,537 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-04 16:18:32,537 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-04 16:18:32,538 INFO L158 Benchmark]: Toolchain (without parser) took 8526.38ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 105.9MB in the beginning and 57.6MB in the end (delta: 48.3MB). Peak memory consumption was 78.7MB. Max. memory is 16.1GB. [2025-03-04 16:18:32,538 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 201.3MB. Free memory is still 119.0MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:18:32,538 INFO L158 Benchmark]: CACSL2BoogieTranslator took 124.78ms. Allocated memory is still 142.6MB. Free memory was 105.9MB in the beginning and 95.5MB in the end (delta: 10.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-04 16:18:32,538 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.54ms. Allocated memory is still 142.6MB. Free memory was 95.5MB in the beginning and 94.3MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:18:32,538 INFO L158 Benchmark]: Boogie Preprocessor took 21.64ms. Allocated memory is still 142.6MB. Free memory was 94.3MB in the beginning and 93.4MB in the end (delta: 850.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:18:32,539 INFO L158 Benchmark]: IcfgBuilder took 146.59ms. Allocated memory is still 142.6MB. Free memory was 93.4MB in the beginning and 84.0MB in the end (delta: 9.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-04 16:18:32,539 INFO L158 Benchmark]: BuchiAutomizer took 8207.10ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 83.6MB in the beginning and 57.6MB in the end (delta: 26.0MB). Peak memory consumption was 53.6MB. Max. memory is 16.1GB. [2025-03-04 16:18:32,539 INFO L158 Benchmark]: Witness Printer took 2.82ms. Allocated memory is still 176.2MB. Free memory is still 57.6MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:18:32,542 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.16ms. Allocated memory is still 201.3MB. Free memory is still 119.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 124.78ms. Allocated memory is still 142.6MB. Free memory was 105.9MB in the beginning and 95.5MB in the end (delta: 10.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 19.54ms. Allocated memory is still 142.6MB. Free memory was 95.5MB in the beginning and 94.3MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 21.64ms. Allocated memory is still 142.6MB. Free memory was 94.3MB in the beginning and 93.4MB in the end (delta: 850.1kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 146.59ms. Allocated memory is still 142.6MB. Free memory was 93.4MB in the beginning and 84.0MB in the end (delta: 9.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 8207.10ms. Allocated memory was 142.6MB in the beginning and 176.2MB in the end (delta: 33.6MB). Free memory was 83.6MB in the beginning and 57.6MB in the end (delta: 26.0MB). Peak memory consumption was 53.6MB. Max. memory is 16.1GB. * Witness Printer took 2.82ms. Allocated memory is still 176.2MB. Free memory is still 57.6MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (6 trivial, 2 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function n and consists of 11 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 6 modules have a trivial ranking function, the largest among these consists of 19 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.1s and 8 iterations. TraceHistogramMax:11. Analysis of lassos took 4.3s. Construction of modules took 0.5s. Büchi inclusion checks took 3.1s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 8. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 78 StatesRemovedByMinimization, 5 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 401 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 383 mSDsluCounter, 503 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 327 mSDsCounter, 258 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 969 IncrementalHoareTripleChecker+Invalid, 1227 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 258 mSolverCounterUnsat, 176 mSDtfsCounter, 969 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT1 SILN0 SILU0 SILI3 SILT2 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp78 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf91 smp82 dnf100 smp100 tf113 neg100 sie105 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 25ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 12 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.3s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-04 16:18:32,552 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (36)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:32,767 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Ended with exit code 0 [2025-03-04 16:18:32,956 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:33,157 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Forceful destruction successful, exit code 0 [2025-03-04 16:18:33,356 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (28)] Ended with exit code 0 [2025-03-04 16:18:33,557 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (27)] Ended with exit code 0 [2025-03-04 16:18:33,758 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-04 16:18:33,958 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE