./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version fca748b1 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05.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 97829031814878890268a6b8dbba5c3e987e2ec78ab2dc94181f9e68090060bd --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dd.update-z3-fca748b-m [2024-11-20 22:54:37,390 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-20 22:54:37,472 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-20 22:54:37,483 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-20 22:54:37,484 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-20 22:54:37,516 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-20 22:54:37,517 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-20 22:54:37,517 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-20 22:54:37,518 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-20 22:54:37,521 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-20 22:54:37,522 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-20 22:54:37,522 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-20 22:54:37,523 INFO L153 SettingsManager]: * Use SBE=true [2024-11-20 22:54:37,523 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-20 22:54:37,525 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-20 22:54:37,525 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-20 22:54:37,526 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-20 22:54:37,526 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-20 22:54:37,526 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-20 22:54:37,527 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-20 22:54:37,530 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-20 22:54:37,531 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-20 22:54:37,531 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-20 22:54:37,531 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-20 22:54:37,531 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-20 22:54:37,531 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-20 22:54:37,532 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-20 22:54:37,532 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-20 22:54:37,532 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-20 22:54:37,532 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-20 22:54:37,532 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-20 22:54:37,533 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-20 22:54:37,533 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-20 22:54:37,533 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-20 22:54:37,533 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-20 22:54:37,534 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-20 22:54:37,534 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-20 22:54:37,536 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-20 22:54:37,536 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-20 22:54:37,536 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 97829031814878890268a6b8dbba5c3e987e2ec78ab2dc94181f9e68090060bd [2024-11-20 22:54:37,810 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-20 22:54:37,830 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-20 22:54:37,834 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-20 22:54:37,836 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-20 22:54:37,836 INFO L274 PluginConnector]: CDTParser initialized [2024-11-20 22:54:37,838 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05.c [2024-11-20 22:54:39,257 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-20 22:54:39,465 INFO L384 CDTParser]: Found 1 translation units. [2024-11-20 22:54:39,466 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05.c [2024-11-20 22:54:39,474 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6fc32922d/542d0eb341ce410991b6384d882c9bef/FLAG61c1221c9 [2024-11-20 22:54:39,490 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6fc32922d/542d0eb341ce410991b6384d882c9bef [2024-11-20 22:54:39,493 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-20 22:54:39,494 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-20 22:54:39,497 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-20 22:54:39,498 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-20 22:54:39,503 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-20 22:54:39,504 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,505 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@37a9b420 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39, skipping insertion in model container [2024-11-20 22:54:39,506 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,525 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-20 22:54:39,700 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-20 22:54:39,710 INFO L200 MainTranslator]: Completed pre-run [2024-11-20 22:54:39,722 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-20 22:54:39,738 INFO L204 MainTranslator]: Completed translation [2024-11-20 22:54:39,739 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39 WrapperNode [2024-11-20 22:54:39,739 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-20 22:54:39,740 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-20 22:54:39,740 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-20 22:54:39,740 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-20 22:54:39,747 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,753 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,768 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2024-11-20 22:54:39,768 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-20 22:54:39,769 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-20 22:54:39,769 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-20 22:54:39,771 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-20 22:54:39,779 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,780 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,781 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,789 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-20 22:54:39,790 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,790 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,792 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,794 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,794 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,795 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,796 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-20 22:54:39,797 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-20 22:54:39,797 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-20 22:54:39,797 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-20 22:54:39,798 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (1/1) ... [2024-11-20 22:54:39,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,836 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:39,842 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-20 22:54:39,895 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-11-20 22:54:39,895 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-11-20 22:54:39,895 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-20 22:54:39,896 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-20 22:54:39,896 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-20 22:54:39,896 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-20 22:54:39,952 INFO L238 CfgBuilder]: Building ICFG [2024-11-20 22:54:39,954 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-20 22:54:40,055 INFO L? ?]: Removed 8 outVars from TransFormulas that were not future-live. [2024-11-20 22:54:40,056 INFO L287 CfgBuilder]: Performing block encoding [2024-11-20 22:54:40,070 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-20 22:54:40,070 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-20 22:54:40,071 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:54:40 BoogieIcfgContainer [2024-11-20 22:54:40,071 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-20 22:54:40,072 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-20 22:54:40,072 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-20 22:54:40,077 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-20 22:54:40,078 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:54:40,078 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 20.11 10:54:39" (1/3) ... [2024-11-20 22:54:40,079 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@7c7eec22 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 20.11 10:54:40, skipping insertion in model container [2024-11-20 22:54:40,079 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:54:40,080 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:39" (2/3) ... [2024-11-20 22:54:40,080 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@7c7eec22 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 20.11 10:54:40, skipping insertion in model container [2024-11-20 22:54:40,080 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:54:40,080 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:54:40" (3/3) ... [2024-11-20 22:54:40,081 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci05.c [2024-11-20 22:54:40,124 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-20 22:54:40,124 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-20 22:54:40,124 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-20 22:54:40,124 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-20 22:54:40,125 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-20 22:54:40,125 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-20 22:54:40,125 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-20 22:54:40,125 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-20 22:54:40,128 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-20 22:54:40,153 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:40,154 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:40,154 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:40,159 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:54:40,159 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:40,160 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-20 22:54:40,160 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-20 22:54:40,162 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:40,162 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:40,162 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:40,163 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:54:40,163 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:40,172 INFO L745 eck$LassoCheckResult]: Stem: 17#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 12#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 8#L29true call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 14#$Ultimate##0true [2024-11-20 22:54:40,173 INFO L747 eck$LassoCheckResult]: Loop: 14#$Ultimate##0true ~n := #in~n; 4#L17true assume !(~n < 1); 18#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 14#$Ultimate##0true [2024-11-20 22:54:40,178 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:40,178 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-11-20 22:54:40,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:40,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [984385517] [2024-11-20 22:54:40,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:40,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:40,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:40,271 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:40,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:40,303 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:40,307 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:40,307 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-11-20 22:54:40,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:40,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [611176345] [2024-11-20 22:54:40,308 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:40,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:40,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:40,326 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:40,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:40,334 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:40,337 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:40,337 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-11-20 22:54:40,337 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:40,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874719034] [2024-11-20 22:54:40,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:40,338 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:40,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:40,351 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:40,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:40,360 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:40,468 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:40,468 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:40,469 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:40,469 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:40,469 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:40,469 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,469 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:40,469 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:40,470 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration1_Loop [2024-11-20 22:54:40,470 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:40,470 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:40,484 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,491 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,494 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,497 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,507 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,568 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:40,568 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:40,570 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,570 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,572 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,573 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-20 22:54:40,574 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:40,574 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:40,591 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:40,591 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:40,600 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-20 22:54:40,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,603 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,605 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-20 22:54:40,606 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:40,606 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:40,619 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:40,619 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:40,626 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:40,627 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,629 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,630 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-20 22:54:40,631 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:40,631 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:40,643 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:40,643 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:40,650 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:40,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,651 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,652 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-20 22:54:40,655 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:40,655 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:40,674 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 [2024-11-20 22:54:40,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,678 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,679 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-20 22:54:40,680 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:40,681 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:40,734 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:40,739 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:40,740 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:40,740 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:40,740 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:40,740 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:40,740 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:40,740 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,740 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:40,740 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:40,741 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration1_Loop [2024-11-20 22:54:40,741 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:40,741 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:40,742 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,746 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,750 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,754 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,766 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:40,894 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:40,899 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:40,900 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,900 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,903 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,905 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-20 22:54:40,908 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:40,919 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:40,919 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:40,920 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:40,920 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:40,920 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:40,921 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:40,922 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:40,924 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:40,931 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:40,931 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,931 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,932 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,934 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-20 22:54:40,934 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:40,944 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:40,944 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:40,944 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:40,944 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:40,945 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:40,945 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:40,945 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:40,949 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:40,957 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 [2024-11-20 22:54:40,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,960 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,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 [2024-11-20 22:54:40,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 [2024-11-20 22:54:40,975 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:40,975 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:40,976 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:40,976 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:40,976 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:40,977 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:40,977 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:40,981 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:40,989 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 [2024-11-20 22:54:40,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:40,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:40,992 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:40,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-20 22:54:40,994 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:41,005 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:41,005 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:41,005 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:41,005 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:41,005 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:41,007 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:41,007 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:41,010 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:41,013 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:41,013 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:41,014 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:41,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:41,017 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:41,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-20 22:54:41,019 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:41,020 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:41,020 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:41,020 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-11-20 22:54:41,026 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:41,029 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:41,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,072 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,074 INFO L255 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-20 22:54:41,075 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:41,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,095 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:41,096 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:41,151 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:41,184 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-20 22:54:41,186 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-20 22:54:41,283 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 40 states and 53 transitions. Complement of second has 16 states. [2024-11-20 22:54:41,287 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:41,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-20 22:54:41,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-20 22:54:41,293 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-20 22:54:41,294 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:41,294 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-20 22:54:41,295 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:41,295 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-20 22:54:41,295 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:41,296 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-11-20 22:54:41,301 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:41,307 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-11-20 22:54:41,310 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-20 22:54:41,310 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-20 22:54:41,311 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-20 22:54:41,312 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:41,313 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-20 22:54:41,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-20 22:54:41,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-20 22:54:41,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-20 22:54:41,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-20 22:54:41,338 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-20 22:54:41,338 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-20 22:54:41,338 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-20 22:54:41,338 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-20 22:54:41,339 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:41,339 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:41,339 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:41,340 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:41,340 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:41,341 INFO L745 eck$LassoCheckResult]: Stem: 130#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 131#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 120#L29 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 132#$Ultimate##0 ~n := #in~n; 126#L17 assume !(~n < 1); 127#L19 assume !(1 == ~n); 119#L22 call #t~ret4 := fibonacci(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 123#L17 assume ~n < 1;#res := 0; 124#fibonacciFINAL assume true; 129#fibonacciEXIT >#31#return; 118#L22-1 [2024-11-20 22:54:41,341 INFO L747 eck$LassoCheckResult]: Loop: 118#L22-1 call #t~ret5 := fibonacci(~n - 2);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume !(~n < 1); 136#L19 assume !(1 == ~n); 121#L22 call #t~ret4 := fibonacci(~n - 1);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume ~n < 1;#res := 0; 134#fibonacciFINAL assume true; 135#fibonacciEXIT >#31#return; 118#L22-1 [2024-11-20 22:54:41,341 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,341 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-11-20 22:54:41,342 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:41,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [325744360] [2024-11-20 22:54:41,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,342 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:41,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,469 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-20 22:54:41,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,522 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-20 22:54:41,522 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:41,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [325744360] [2024-11-20 22:54:41,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [325744360] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:54:41,523 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-20 22:54:41,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-20 22:54:41,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1540000211] [2024-11-20 22:54:41,526 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:54:41,528 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:54:41,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,528 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-11-20 22:54:41,529 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:41,529 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1688944517] [2024-11-20 22:54:41,529 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:41,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,593 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-20 22:54:41,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,631 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-20 22:54:41,632 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:41,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1688944517] [2024-11-20 22:54:41,632 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1688944517] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:54:41,633 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-20 22:54:41,633 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-20 22:54:41,633 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1116793443] [2024-11-20 22:54:41,633 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:54:41,634 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-20 22:54:41,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:41,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-20 22:54:41,637 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-20 22:54:41,638 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-20 22:54:41,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:41,725 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-20 22:54:41,726 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-20 22:54:41,727 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:41,729 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-20 22:54:41,730 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-20 22:54:41,731 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-20 22:54:41,731 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-20 22:54:41,731 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:41,731 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-20 22:54:41,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-20 22:54:41,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-20 22:54:41,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-20 22:54:41,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-20 22:54:41,736 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-20 22:54:41,737 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-20 22:54:41,737 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-20 22:54:41,738 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-20 22:54:41,738 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-20 22:54:41,738 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:41,740 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:41,740 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:41,741 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:41,741 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-20 22:54:41,741 INFO L745 eck$LassoCheckResult]: Stem: 202#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 203#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 191#L29 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 201#$Ultimate##0 ~n := #in~n; 196#L17 assume !(~n < 1); 197#L19 assume !(1 == ~n); 192#L22 call #t~ret4 := fibonacci(~n - 1);< 198#$Ultimate##0 ~n := #in~n; 194#L17 assume !(~n < 1); 195#L19 assume 1 == ~n;#res := 1; 205#fibonacciFINAL assume true; 208#fibonacciEXIT >#31#return; 189#L22-1 [2024-11-20 22:54:41,742 INFO L747 eck$LassoCheckResult]: Loop: 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume 1 == ~n;#res := 1; 210#fibonacciFINAL assume true; 207#fibonacciEXIT >#31#return; 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume ~n < 1;#res := 0; 212#fibonacciFINAL assume true; 199#fibonacciEXIT >#33#return; 200#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 204#fibonacciFINAL assume true; 206#fibonacciEXIT >#31#return; 189#L22-1 [2024-11-20 22:54:41,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,742 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-11-20 22:54:41,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:41,743 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1351969698] [2024-11-20 22:54:41,743 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,743 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:41,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:41,755 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:41,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:41,774 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:41,775 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,775 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-11-20 22:54:41,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:41,776 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1702465440] [2024-11-20 22:54:41,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,776 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:41,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:41,784 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:41,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:41,797 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:41,801 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,802 INFO L85 PathProgramCache]: Analyzing trace with hash 998757605, now seen corresponding path program 1 times [2024-11-20 22:54:41,802 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:41,802 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [761117748] [2024-11-20 22:54:41,802 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,803 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:41,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,896 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-20 22:54:41,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,928 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-20 22:54:41,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,946 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:41,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:41,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,960 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 22 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-20 22:54:41,961 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:41,961 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [761117748] [2024-11-20 22:54:41,961 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [761117748] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:41,961 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [383632669] [2024-11-20 22:54:41,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,963 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:41,963 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:41,965 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:54:41,966 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-20 22:54:42,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,014 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,018 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:42,070 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 38 proven. 1 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-20 22:54:42,072 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:42,194 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 22 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-20 22:54:42,194 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [383632669] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:42,194 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:42,195 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2024-11-20 22:54:42,195 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1550906213] [2024-11-20 22:54:42,195 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:42,338 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-11-20 22:54:42,475 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:42,475 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:42,475 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:42,476 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:42,476 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:42,476 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,476 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:42,476 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:42,476 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration3_Loop [2024-11-20 22:54:42,476 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:42,476 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:42,477 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,480 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,483 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,487 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,489 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,532 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:42,532 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:42,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,538 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,539 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-20 22:54:42,540 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:42,540 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,552 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:42,552 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:42,558 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-20 22:54:42,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,558 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,561 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,562 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-20 22:54:42,562 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:42,562 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,574 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:42,574 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:42,580 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-20 22:54:42,580 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,581 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,582 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,582 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-20 22:54:42,584 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:42,584 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,601 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-20 22:54:42,602 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,602 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,603 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,606 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-20 22:54:42,607 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:42,607 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,621 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:42,631 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-20 22:54:42,632 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:42,632 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:42,632 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:42,632 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:42,632 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:42,632 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,633 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:42,633 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:42,633 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration3_Loop [2024-11-20 22:54:42,633 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:42,633 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:42,634 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,643 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,645 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,651 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,653 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,701 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:42,701 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:42,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,704 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,705 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-20 22:54:42,707 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:42,719 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:42,720 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:42,720 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:42,720 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:42,720 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:42,721 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:42,721 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:42,722 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:42,728 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 [2024-11-20 22:54:42,729 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,729 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,730 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) [2024-11-20 22:54:42,731 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 [2024-11-20 22:54:42,733 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:42,742 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:42,743 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:42,743 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:42,743 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:42,743 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:42,743 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:42,744 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:42,745 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:42,753 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 [2024-11-20 22:54:42,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,756 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,759 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-20 22:54:42,759 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:42,770 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:42,770 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:42,770 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:42,770 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:42,770 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:42,771 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:42,771 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:42,773 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:42,776 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:42,776 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:42,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,779 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,780 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-20 22:54:42,781 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:42,781 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:42,782 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:42,782 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-20 22:54:42,788 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:42,789 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:42,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:42,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,825 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,826 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:42,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,930 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,932 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:43,079 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:43,080 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-20 22:54:43,080 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-20 22:54:43,331 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 152 states and 210 transitions. Complement of second has 54 states. [2024-11-20 22:54:43,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:43,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-20 22:54:43,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-20 22:54:43,335 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-20 22:54:43,336 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:43,336 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-20 22:54:43,337 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:43,337 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-20 22:54:43,340 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:43,342 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-20 22:54:43,349 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-20 22:54:43,353 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-20 22:54:43,354 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-20 22:54:43,354 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-20 22:54:43,354 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-20 22:54:43,355 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:43,355 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-20 22:54:43,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-20 22:54:43,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-20 22:54:43,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 70 states have internal predecessors, (81), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (35), 22 states have call predecessors, (35), 23 states have call successors, (35) [2024-11-20 22:54:43,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-20 22:54:43,369 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-20 22:54:43,369 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:43,369 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-20 22:54:43,370 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2024-11-20 22:54:43,370 INFO L87 Difference]: Start difference. First operand 106 states and 142 transitions. Second operand has 9 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-20 22:54:43,426 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:43,427 INFO L93 Difference]: Finished difference Result 44 states and 57 transitions. [2024-11-20 22:54:43,427 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 44 states and 57 transitions. [2024-11-20 22:54:43,429 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:43,430 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 44 states to 41 states and 53 transitions. [2024-11-20 22:54:43,430 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 34 [2024-11-20 22:54:43,431 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 34 [2024-11-20 22:54:43,431 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 53 transitions. [2024-11-20 22:54:43,431 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:43,431 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 53 transitions. [2024-11-20 22:54:43,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 53 transitions. [2024-11-20 22:54:43,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 38. [2024-11-20 22:54:43,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 25 states have (on average 1.12) internal successors, (28), 27 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 6 states have return successors, (12), 5 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-20 22:54:43,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2024-11-20 22:54:43,435 INFO L240 hiAutomatonCegarLoop]: Abstraction has 38 states and 47 transitions. [2024-11-20 22:54:43,436 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-20 22:54:43,436 INFO L425 stractBuchiCegarLoop]: Abstraction has 38 states and 47 transitions. [2024-11-20 22:54:43,437 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-20 22:54:43,437 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 38 states and 47 transitions. [2024-11-20 22:54:43,438 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:43,438 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:43,438 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:43,440 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:43,440 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-20 22:54:43,440 INFO L745 eck$LassoCheckResult]: Stem: 959#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 960#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 952#L29 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 961#$Ultimate##0 ~n := #in~n; 951#L17 assume !(~n < 1); 953#L19 assume !(1 == ~n); 955#L22 call #t~ret4 := fibonacci(~n - 1);< 956#$Ultimate##0 ~n := #in~n; 967#L17 assume !(~n < 1); 981#L19 assume !(1 == ~n); 962#L22 call #t~ret4 := fibonacci(~n - 1);< 956#$Ultimate##0 ~n := #in~n; 966#L17 assume !(~n < 1); 964#L19 assume 1 == ~n;#res := 1; 965#fibonacciFINAL assume true; 979#fibonacciEXIT >#31#return; 976#L22-1 call #t~ret5 := fibonacci(~n - 2);< 977#$Ultimate##0 ~n := #in~n; 980#L17 assume ~n < 1;#res := 0; 978#fibonacciFINAL assume true; 975#fibonacciEXIT >#33#return; 974#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 973#fibonacciFINAL assume true; 972#fibonacciEXIT >#31#return; 947#L22-1 [2024-11-20 22:54:43,440 INFO L747 eck$LassoCheckResult]: Loop: 947#L22-1 call #t~ret5 := fibonacci(~n - 2);< 954#$Ultimate##0 ~n := #in~n; 970#L17 assume !(~n < 1); 968#L19 assume !(1 == ~n); 946#L22 call #t~ret4 := fibonacci(~n - 1);< 954#$Ultimate##0 ~n := #in~n; 970#L17 assume !(~n < 1); 968#L19 assume !(1 == ~n); 946#L22 call #t~ret4 := fibonacci(~n - 1);< 954#$Ultimate##0 ~n := #in~n; 970#L17 assume !(~n < 1); 968#L19 assume 1 == ~n;#res := 1; 969#fibonacciFINAL assume true; 982#fibonacciEXIT >#31#return; 945#L22-1 call #t~ret5 := fibonacci(~n - 2);< 948#$Ultimate##0 ~n := #in~n; 949#L17 assume ~n < 1;#res := 0; 950#fibonacciFINAL assume true; 957#fibonacciEXIT >#33#return; 958#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 963#fibonacciFINAL assume true; 971#fibonacciEXIT >#31#return; 947#L22-1 [2024-11-20 22:54:43,441 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:43,441 INFO L85 PathProgramCache]: Analyzing trace with hash 62997961, now seen corresponding path program 2 times [2024-11-20 22:54:43,441 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:43,441 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1601095724] [2024-11-20 22:54:43,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:43,441 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:43,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:43,449 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:43,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:43,457 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:43,457 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:43,458 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 2 times [2024-11-20 22:54:43,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:43,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1803506388] [2024-11-20 22:54:43,458 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:43,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:43,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:43,464 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:43,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:43,469 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:43,469 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:43,469 INFO L85 PathProgramCache]: Analyzing trace with hash 969547889, now seen corresponding path program 3 times [2024-11-20 22:54:43,470 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:43,470 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303055430] [2024-11-20 22:54:43,470 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:43,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:43,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,582 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-20 22:54:43,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,626 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:43,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,639 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:43,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,645 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-20 22:54:43,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,651 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:43,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:43,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,657 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 16 proven. 46 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2024-11-20 22:54:43,657 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:43,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1303055430] [2024-11-20 22:54:43,657 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1303055430] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:43,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [25048415] [2024-11-20 22:54:43,657 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-20 22:54:43,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:43,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:43,660 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:54:43,678 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-20 22:54:43,695 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 [2024-11-20 22:54:43,726 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-20 22:54:43,727 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-20 22:54:43,728 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-20 22:54:43,731 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:43,829 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 35 proven. 47 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-20 22:54:43,829 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:44,192 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 35 proven. 49 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-11-20 22:54:44,192 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [25048415] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:44,192 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:44,192 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 12] total 21 [2024-11-20 22:54:44,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [322983774] [2024-11-20 22:54:44,193 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:44,382 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:44,382 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:44,382 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:44,382 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:44,382 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:44,382 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,383 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:44,383 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:44,383 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration4_Loop [2024-11-20 22:54:44,383 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:44,383 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:44,383 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,388 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,389 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,395 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,400 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,433 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:44,433 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:44,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,434 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,435 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,436 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-20 22:54:44,437 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:44,437 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,448 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:44,448 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:44,454 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,455 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,456 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-20 22:54:44,458 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:44,458 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,468 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:44,469 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:44,474 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,475 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,475 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,476 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-20 22:54:44,478 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:44,478 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,495 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,495 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,497 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) [2024-11-20 22:54:44,498 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 [2024-11-20 22:54:44,499 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:44,499 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,511 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:44,517 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,517 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:44,517 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:44,517 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:44,518 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:44,518 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:44,518 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,518 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:44,518 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:44,518 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration4_Loop [2024-11-20 22:54:44,518 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:44,518 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:44,519 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,525 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,529 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,531 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,536 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,576 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:44,576 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:44,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,578 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,580 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-20 22:54:44,581 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:44,591 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:44,591 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:44,591 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:44,591 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:44,591 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:44,592 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:44,592 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:44,593 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:44,599 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,599 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,600 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,602 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-20 22:54:44,602 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:44,613 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:44,613 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:44,613 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:44,614 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:44,614 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:44,614 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:44,614 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:44,617 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:44,620 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:54:44,621 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:54:44,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,623 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-20 22:54:44,626 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:44,626 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:44,626 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:44,626 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-20 22:54:44,634 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,635 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:44,646 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:44,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:44,677 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-20 22:54:44,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:44,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:44,898 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-20 22:54:44,903 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,031 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:45,032 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-20 22:54:45,033 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 38 states and 47 transitions. cyclomatic complexity: 11 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-20 22:54:45,097 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-11-20 22:54:45,160 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 38 states and 47 transitions. cyclomatic complexity: 11. 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 45 states and 54 transitions. Complement of second has 11 states. [2024-11-20 22:54:45,160 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:45,161 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-20 22:54:45,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-20 22:54:45,163 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 24 letters. Loop has 22 letters. [2024-11-20 22:54:45,163 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:45,163 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:45,173 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:45,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:45,207 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-20 22:54:45,209 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:45,383 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-20 22:54:45,384 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,508 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:45,509 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 [2024-11-20 22:54:45,509 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 38 states and 47 transitions. cyclomatic complexity: 11 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-20 22:54:45,592 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 38 states and 47 transitions. cyclomatic complexity: 11. 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 45 states and 54 transitions. Complement of second has 11 states. [2024-11-20 22:54:45,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:45,593 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-20 22:54:45,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-20 22:54:45,593 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 24 letters. Loop has 22 letters. [2024-11-20 22:54:45,594 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:45,594 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:45,604 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:45,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:45,635 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-20 22:54:45,636 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:45,802 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-20 22:54:45,803 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,919 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:45,920 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 [2024-11-20 22:54:45,920 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 38 states and 47 transitions. cyclomatic complexity: 11 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-20 22:54:46,161 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 38 states and 47 transitions. cyclomatic complexity: 11. 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 331 states and 432 transitions. Complement of second has 134 states. [2024-11-20 22:54:46,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:46,163 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, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-20 22:54:46,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-20 22:54:46,164 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 24 letters. Loop has 22 letters. [2024-11-20 22:54:46,164 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:46,164 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 46 letters. Loop has 22 letters. [2024-11-20 22:54:46,165 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:46,165 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 24 letters. Loop has 44 letters. [2024-11-20 22:54:46,166 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:46,167 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 331 states and 432 transitions. [2024-11-20 22:54:46,172 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:46,194 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 331 states to 215 states and 294 transitions. [2024-11-20 22:54:46,194 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 97 [2024-11-20 22:54:46,196 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 113 [2024-11-20 22:54:46,196 INFO L73 IsDeterministic]: Start isDeterministic. Operand 215 states and 294 transitions. [2024-11-20 22:54:46,197 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:46,197 INFO L218 hiAutomatonCegarLoop]: Abstraction has 215 states and 294 transitions. [2024-11-20 22:54:46,197 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states and 294 transitions. [2024-11-20 22:54:46,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 173. [2024-11-20 22:54:46,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 107 states have (on average 1.1401869158878504) internal successors, (122), 113 states have internal predecessors, (122), 38 states have call successors, (42), 23 states have call predecessors, (42), 28 states have return successors, (61), 36 states have call predecessors, (61), 36 states have call successors, (61) [2024-11-20 22:54:46,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 225 transitions. [2024-11-20 22:54:46,218 INFO L240 hiAutomatonCegarLoop]: Abstraction has 173 states and 225 transitions. [2024-11-20 22:54:46,219 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:46,219 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-20 22:54:46,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2024-11-20 22:54:46,219 INFO L87 Difference]: Start difference. First operand 173 states and 225 transitions. Second operand has 21 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 18 states have internal predecessors, (49), 13 states have call successors, (17), 3 states have call predecessors, (17), 7 states have return successors, (16), 10 states have call predecessors, (16), 11 states have call successors, (16) [2024-11-20 22:54:46,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:46,488 INFO L93 Difference]: Finished difference Result 344 states and 500 transitions. [2024-11-20 22:54:46,488 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 344 states and 500 transitions. [2024-11-20 22:54:46,497 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:46,504 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 344 states to 334 states and 487 transitions. [2024-11-20 22:54:46,504 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 170 [2024-11-20 22:54:46,505 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 190 [2024-11-20 22:54:46,505 INFO L73 IsDeterministic]: Start isDeterministic. Operand 334 states and 487 transitions. [2024-11-20 22:54:46,505 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:46,505 INFO L218 hiAutomatonCegarLoop]: Abstraction has 334 states and 487 transitions. [2024-11-20 22:54:46,506 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states and 487 transitions. [2024-11-20 22:54:46,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 265. [2024-11-20 22:54:46,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 265 states, 164 states have (on average 1.1341463414634145) internal successors, (186), 166 states have internal predecessors, (186), 60 states have call successors, (72), 35 states have call predecessors, (72), 41 states have return successors, (136), 63 states have call predecessors, (136), 58 states have call successors, (136) [2024-11-20 22:54:46,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 265 states to 265 states and 394 transitions. [2024-11-20 22:54:46,542 INFO L240 hiAutomatonCegarLoop]: Abstraction has 265 states and 394 transitions. [2024-11-20 22:54:46,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-20 22:54:46,543 INFO L425 stractBuchiCegarLoop]: Abstraction has 265 states and 394 transitions. [2024-11-20 22:54:46,546 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-20 22:54:46,546 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 265 states and 394 transitions. [2024-11-20 22:54:46,548 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:46,548 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:46,548 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:46,552 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 10, 9, 7, 7, 5, 5, 4, 4, 3, 2, 1, 1, 1] [2024-11-20 22:54:46,552 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:46,552 INFO L745 eck$LassoCheckResult]: Stem: 2933#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 2934#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 2935#L29 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 2936#$Ultimate##0 ~n := #in~n; 2982#L17 assume !(~n < 1); 2980#L19 assume !(1 == ~n); 2972#L22 call #t~ret4 := fibonacci(~n - 1);< 2975#$Ultimate##0 ~n := #in~n; 2981#L17 assume !(~n < 1); 2979#L19 assume !(1 == ~n); 2973#L22 call #t~ret4 := fibonacci(~n - 1);< 2975#$Ultimate##0 ~n := #in~n; 2981#L17 assume !(~n < 1); 2979#L19 assume !(1 == ~n); 2973#L22 call #t~ret4 := fibonacci(~n - 1);< 2975#$Ultimate##0 ~n := #in~n; 2981#L17 assume !(~n < 1); 2979#L19 assume !(1 == ~n); 2973#L22 call #t~ret4 := fibonacci(~n - 1);< 2975#$Ultimate##0 ~n := #in~n; 2983#L17 assume !(~n < 1); 3109#L19 assume 1 == ~n;#res := 1; 3107#fibonacciFINAL assume true; 3104#fibonacciEXIT >#31#return; 3101#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3102#$Ultimate##0 ~n := #in~n; 3108#L17 assume ~n < 1;#res := 0; 3106#fibonacciFINAL assume true; 3100#fibonacciEXIT >#33#return; 3098#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3097#fibonacciFINAL assume true; 3094#fibonacciEXIT >#31#return; 3006#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3007#$Ultimate##0 ~n := #in~n; 3053#L17 assume !(~n < 1); 3021#L19 assume 1 == ~n;#res := 1; 2960#fibonacciFINAL assume true; 3004#fibonacciEXIT >#33#return; 3002#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2997#fibonacciFINAL assume true; 2988#fibonacciEXIT >#31#return; 2987#L22-1 call #t~ret5 := fibonacci(~n - 2);< 2990#$Ultimate##0 ~n := #in~n; 3064#L17 assume !(~n < 1); 3019#L19 assume !(1 == ~n); 3020#L22 call #t~ret4 := fibonacci(~n - 1);< 3167#$Ultimate##0 ~n := #in~n; 3113#L17 assume !(~n < 1); 3115#L19 assume 1 == ~n;#res := 1; 3168#fibonacciFINAL assume true; 3165#fibonacciEXIT >#31#return; 2950#L22-1 call #t~ret5 := fibonacci(~n - 2);< 2949#$Ultimate##0 ~n := #in~n; 2952#L17 assume ~n < 1;#res := 0; 3009#fibonacciFINAL assume true; 3000#fibonacciEXIT >#33#return; 3001#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2996#fibonacciFINAL assume true; 2986#fibonacciEXIT >#33#return; 2974#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2977#fibonacciFINAL assume true; 2971#fibonacciEXIT >#31#return; 2965#L22-1 call #t~ret5 := fibonacci(~n - 2);< 2966#$Ultimate##0 ~n := #in~n; 3172#L17 assume !(~n < 1); 3171#L19 assume !(1 == ~n); 3127#L22 call #t~ret4 := fibonacci(~n - 1);< 3166#$Ultimate##0 ~n := #in~n; 3142#L17 assume !(~n < 1); 3143#L19 assume !(1 == ~n); 3122#L22 call #t~ret4 := fibonacci(~n - 1);< 3128#$Ultimate##0 [2024-11-20 22:54:46,552 INFO L747 eck$LassoCheckResult]: Loop: 3128#$Ultimate##0 ~n := #in~n; 3140#L17 assume !(~n < 1); 3138#L19 assume !(1 == ~n); 3124#L22 call #t~ret4 := fibonacci(~n - 1);< 3128#$Ultimate##0 [2024-11-20 22:54:46,553 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:46,553 INFO L85 PathProgramCache]: Analyzing trace with hash -627327765, now seen corresponding path program 4 times [2024-11-20 22:54:46,553 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:46,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [630012561] [2024-11-20 22:54:46,553 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:46,553 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:46,569 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:46,570 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:46,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:46,593 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:46,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:46,593 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-11-20 22:54:46,594 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:46,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [919455231] [2024-11-20 22:54:46,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:46,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:46,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:46,597 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:46,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:46,599 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:46,599 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:46,599 INFO L85 PathProgramCache]: Analyzing trace with hash 2068668293, now seen corresponding path program 5 times [2024-11-20 22:54:46,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:46,600 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [830490294] [2024-11-20 22:54:46,600 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:46,600 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:46,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:46,808 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-20 22:54:46,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:46,889 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:46,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:46,951 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:46,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:46,984 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:46,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:47,006 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:47,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:47,010 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-20 22:54:47,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:47,018 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-20 22:54:47,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:47,026 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:47,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:47,028 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:47,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:47,030 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 115 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-20 22:54:47,030 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:47,030 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [830490294] [2024-11-20 22:54:47,030 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [830490294] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:47,030 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [98839522] [2024-11-20 22:54:47,030 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-20 22:54:47,031 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:47,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:47,034 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) [2024-11-20 22:54:47,035 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Waiting until timeout for monitored process [2024-11-20 22:54:47,105 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2024-11-20 22:54:47,106 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-20 22:54:47,107 INFO L255 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-20 22:54:47,109 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:47,185 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 115 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-20 22:54:47,186 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:47,757 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 130 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2024-11-20 22:54:47,758 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [98839522] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:47,758 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:47,758 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12, 15] total 20 [2024-11-20 22:54:47,758 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1410611797] [2024-11-20 22:54:47,758 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:47,796 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:47,797 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:47,797 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:47,797 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:47,797 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:47,797 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,797 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:47,797 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:47,797 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration5_Loop [2024-11-20 22:54:47,797 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:47,797 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:47,798 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,800 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,802 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,804 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,809 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,840 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:47,840 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:47,841 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:47,843 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:47,845 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-20 22:54:47,846 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:47,846 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:47,862 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:47,862 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:47,869 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:47,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,870 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:47,871 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:47,872 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-20 22:54:47,873 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:47,873 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:47,884 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:47,884 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:47,889 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:47,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,890 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:47,891 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:47,892 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-20 22:54:47,893 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:47,893 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:47,904 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:47,904 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:47,909 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:47,910 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,910 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:47,911 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:47,912 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-20 22:54:47,913 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:47,913 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:47,929 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:47,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,929 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:47,930 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) [2024-11-20 22:54:47,931 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 [2024-11-20 22:54:47,932 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:47,932 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:47,954 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:47,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:47,958 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:47,958 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:47,958 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:47,958 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:47,958 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:47,958 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:47,958 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:47,958 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:47,958 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration5_Loop [2024-11-20 22:54:47,959 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:47,959 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:47,959 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,963 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,965 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,967 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:47,974 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:48,006 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:48,006 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:48,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:48,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:48,010 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:48,011 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-20 22:54:48,015 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:48,027 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:48,028 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:48,028 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:48,028 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:48,028 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:48,028 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:48,028 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:48,030 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:48,038 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:48,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:48,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:48,040 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:48,041 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-20 22:54:48,044 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:48,056 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:48,056 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:48,057 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:48,057 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:48,057 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:48,057 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:48,057 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:48,059 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:48,066 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2024-11-20 22:54:48,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:48,067 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:48,069 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:48,070 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-20 22:54:48,071 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:48,083 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:48,083 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:48,084 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:48,084 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:48,084 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:48,084 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:48,084 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:48,085 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:48,093 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:48,093 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:48,094 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:48,096 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:48,097 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-20 22:54:48,098 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:48,110 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:48,110 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:48,110 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:48,110 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:48,111 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:48,111 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:48,111 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:48,113 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:48,116 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:54:48,116 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:54:48,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:48,116 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:48,119 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:48,120 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-20 22:54:48,121 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:48,121 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:48,121 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:48,121 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-11-20 22:54:48,129 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 [2024-11-20 22:54:48,130 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:48,148 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:48,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:48,224 INFO L255 TraceCheckSpWp]: Trace formula consists of 532 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-20 22:54:48,226 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:48,513 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:48,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:48,684 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:48,685 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:48,715 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:48,716 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:54:48,717 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 265 states and 394 transitions. cyclomatic complexity: 133 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) [2024-11-20 22:54:48,776 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 265 states and 394 transitions. cyclomatic complexity: 133. 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 287 states and 420 transitions. Complement of second has 17 states. [2024-11-20 22:54:48,779 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:48,779 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) [2024-11-20 22:54:48,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-20 22:54:48,780 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 71 letters. Loop has 4 letters. [2024-11-20 22:54:48,780 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:48,780 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:48,792 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:48,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:48,868 INFO L255 TraceCheckSpWp]: Trace formula consists of 532 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-20 22:54:48,872 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:49,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:49,313 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:49,314 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:49,337 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:49,337 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:54:49,337 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 265 states and 394 transitions. cyclomatic complexity: 133 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) [2024-11-20 22:54:49,398 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 265 states and 394 transitions. cyclomatic complexity: 133. 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 287 states and 420 transitions. Complement of second has 17 states. [2024-11-20 22:54:49,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:49,400 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) [2024-11-20 22:54:49,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-20 22:54:49,400 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 71 letters. Loop has 4 letters. [2024-11-20 22:54:49,400 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:49,400 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:49,410 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:49,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:49,507 INFO L255 TraceCheckSpWp]: Trace formula consists of 532 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-20 22:54:49,509 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:49,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:49,939 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:49,939 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:49,959 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:49,959 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:54:49,960 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 265 states and 394 transitions. cyclomatic complexity: 133 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) [2024-11-20 22:54:50,029 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 265 states and 394 transitions. cyclomatic complexity: 133. 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 340 states and 477 transitions. Complement of second has 19 states. [2024-11-20 22:54:50,030 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:50,031 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) [2024-11-20 22:54:50,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-20 22:54:50,031 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 71 letters. Loop has 4 letters. [2024-11-20 22:54:50,031 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:50,032 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 75 letters. Loop has 4 letters. [2024-11-20 22:54:50,032 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:50,032 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 71 letters. Loop has 8 letters. [2024-11-20 22:54:50,032 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:50,032 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 340 states and 477 transitions. [2024-11-20 22:54:50,038 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:50,044 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 340 states to 279 states and 410 transitions. [2024-11-20 22:54:50,046 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 132 [2024-11-20 22:54:50,047 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 137 [2024-11-20 22:54:50,047 INFO L73 IsDeterministic]: Start isDeterministic. Operand 279 states and 410 transitions. [2024-11-20 22:54:50,047 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:50,047 INFO L218 hiAutomatonCegarLoop]: Abstraction has 279 states and 410 transitions. [2024-11-20 22:54:50,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 279 states and 410 transitions. [2024-11-20 22:54:50,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 279 to 271. [2024-11-20 22:54:50,069 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 271 states, 169 states have (on average 1.1301775147928994) internal successors, (191), 171 states have internal predecessors, (191), 61 states have call successors, (73), 36 states have call predecessors, (73), 41 states have return successors, (138), 63 states have call predecessors, (138), 59 states have call successors, (138) [2024-11-20 22:54:50,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 271 states to 271 states and 402 transitions. [2024-11-20 22:54:50,073 INFO L240 hiAutomatonCegarLoop]: Abstraction has 271 states and 402 transitions. [2024-11-20 22:54:50,073 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:50,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-20 22:54:50,073 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=275, Unknown=0, NotChecked=0, Total=380 [2024-11-20 22:54:50,074 INFO L87 Difference]: Start difference. First operand 271 states and 402 transitions. Second operand has 20 states, 15 states have (on average 3.0) internal successors, (45), 16 states have internal predecessors, (45), 16 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) [2024-11-20 22:54:50,262 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:50,262 INFO L93 Difference]: Finished difference Result 483 states and 750 transitions. [2024-11-20 22:54:50,262 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 483 states and 750 transitions. [2024-11-20 22:54:50,268 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:50,275 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 483 states to 478 states and 743 transitions. [2024-11-20 22:54:50,275 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 247 [2024-11-20 22:54:50,276 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 254 [2024-11-20 22:54:50,276 INFO L73 IsDeterministic]: Start isDeterministic. Operand 478 states and 743 transitions. [2024-11-20 22:54:50,279 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:50,279 INFO L218 hiAutomatonCegarLoop]: Abstraction has 478 states and 743 transitions. [2024-11-20 22:54:50,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 478 states and 743 transitions. [2024-11-20 22:54:50,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 478 to 362. [2024-11-20 22:54:50,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 362 states, 225 states have (on average 1.1511111111111112) internal successors, (259), 225 states have internal predecessors, (259), 83 states have call successors, (99), 48 states have call predecessors, (99), 54 states have return successors, (218), 88 states have call predecessors, (218), 81 states have call successors, (218) [2024-11-20 22:54:50,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 362 states to 362 states and 576 transitions. [2024-11-20 22:54:50,305 INFO L240 hiAutomatonCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-11-20 22:54:50,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-20 22:54:50,306 INFO L425 stractBuchiCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-11-20 22:54:50,307 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-20 22:54:50,307 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 362 states and 576 transitions. [2024-11-20 22:54:50,310 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:50,310 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:50,310 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:50,312 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [20, 17, 15, 12, 11, 8, 8, 7, 7, 5, 3, 1, 1, 1] [2024-11-20 22:54:50,313 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:50,314 INFO L745 eck$LassoCheckResult]: Stem: 6250#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 6251#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 6252#L29 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 6253#$Ultimate##0 ~n := #in~n; 6314#L17 assume !(~n < 1); 6312#L19 assume !(1 == ~n); 6247#L22 call #t~ret4 := fibonacci(~n - 1);< 6310#$Ultimate##0 ~n := #in~n; 6308#L17 assume !(~n < 1); 6306#L19 assume !(1 == ~n); 6221#L22 call #t~ret4 := fibonacci(~n - 1);< 6291#$Ultimate##0 ~n := #in~n; 6309#L17 assume !(~n < 1); 6307#L19 assume !(1 == ~n); 6222#L22 call #t~ret4 := fibonacci(~n - 1);< 6291#$Ultimate##0 ~n := #in~n; 6309#L17 assume !(~n < 1); 6307#L19 assume !(1 == ~n); 6222#L22 call #t~ret4 := fibonacci(~n - 1);< 6291#$Ultimate##0 ~n := #in~n; 6309#L17 assume !(~n < 1); 6307#L19 assume !(1 == ~n); 6222#L22 call #t~ret4 := fibonacci(~n - 1);< 6291#$Ultimate##0 ~n := #in~n; 6309#L17 assume !(~n < 1); 6307#L19 assume !(1 == ~n); 6222#L22 call #t~ret4 := fibonacci(~n - 1);< 6291#$Ultimate##0 ~n := #in~n; 6311#L17 assume !(~n < 1); 6258#L19 assume 1 == ~n;#res := 1; 6259#fibonacciFINAL assume true; 6559#fibonacciEXIT >#31#return; 6220#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6223#$Ultimate##0 ~n := #in~n; 6577#L17 assume ~n < 1;#res := 0; 6576#fibonacciFINAL assume true; 6574#fibonacciEXIT >#33#return; 6254#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6255#fibonacciFINAL assume true; 6246#fibonacciEXIT >#31#return; 6236#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6362#$Ultimate##0 ~n := #in~n; 6378#L17 assume !(~n < 1); 6368#L19 assume 1 == ~n;#res := 1; 6271#fibonacciFINAL assume true; 6360#fibonacciEXIT >#33#return; 6357#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6352#fibonacciFINAL assume true; 6305#fibonacciEXIT >#31#return; 6239#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6301#$Ultimate##0 ~n := #in~n; 6390#L17 assume !(~n < 1); 6391#L19 assume !(1 == ~n); 6326#L22 call #t~ret4 := fibonacci(~n - 1);< 6478#$Ultimate##0 ~n := #in~n; 6476#L17 assume !(~n < 1); 6351#L19 assume 1 == ~n;#res := 1; 6350#fibonacciFINAL assume true; 6324#fibonacciEXIT >#31#return; 6318#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6323#$Ultimate##0 ~n := #in~n; 6374#L17 assume ~n < 1;#res := 0; 6373#fibonacciFINAL assume true; 6315#fibonacciEXIT >#33#return; 6313#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6303#fibonacciFINAL assume true; 6299#fibonacciEXIT >#33#return; 6295#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6293#fibonacciFINAL assume true; 6289#fibonacciEXIT >#31#return; 6238#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6288#$Ultimate##0 ~n := #in~n; 6285#L17 assume !(~n < 1); 6286#L19 assume !(1 == ~n); 6273#L22 call #t~ret4 := fibonacci(~n - 1);< 6428#$Ultimate##0 ~n := #in~n; 6429#L17 assume !(~n < 1); 6425#L19 assume !(1 == ~n); 6407#L22 call #t~ret4 := fibonacci(~n - 1);< 6412#$Ultimate##0 ~n := #in~n; 6394#L17 assume !(~n < 1); 6413#L19 assume 1 == ~n;#res := 1; 6410#fibonacciFINAL assume true; 6406#fibonacciEXIT >#31#return; 6398#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6404#$Ultimate##0 ~n := #in~n; 6409#L17 assume ~n < 1;#res := 0; 6405#fibonacciFINAL assume true; 6396#fibonacciEXIT >#33#return; 6402#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6580#fibonacciFINAL assume true; 6578#fibonacciEXIT >#31#return; 6361#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6362#$Ultimate##0 ~n := #in~n; 6378#L17 assume !(~n < 1); 6368#L19 assume 1 == ~n;#res := 1; 6271#fibonacciFINAL assume true; 6360#fibonacciEXIT >#33#return; 6357#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6352#fibonacciFINAL assume true; 6305#fibonacciEXIT >#33#return; 6290#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 6432#fibonacciFINAL assume true; 6296#fibonacciEXIT >#31#return; 6240#L22-1 call #t~ret5 := fibonacci(~n - 2);< 6280#$Ultimate##0 ~n := #in~n; 6287#L17 assume !(~n < 1); 6477#L19 assume !(1 == ~n); 6261#L22 call #t~ret4 := fibonacci(~n - 1);< 6485#$Ultimate##0 ~n := #in~n; 6486#L17 assume !(~n < 1); 6260#L19 assume !(1 == ~n); 6263#L22 call #t~ret4 := fibonacci(~n - 1);< 6234#$Ultimate##0 ~n := #in~n; 6488#L17 assume !(~n < 1); 6516#L19 assume !(1 == ~n); 6487#L22 [2024-11-20 22:54:50,314 INFO L747 eck$LassoCheckResult]: Loop: 6487#L22 call #t~ret4 := fibonacci(~n - 1);< 6234#$Ultimate##0 ~n := #in~n; 6488#L17 assume !(~n < 1); 6516#L19 assume !(1 == ~n); 6487#L22 [2024-11-20 22:54:50,314 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:50,314 INFO L85 PathProgramCache]: Analyzing trace with hash 664454499, now seen corresponding path program 6 times [2024-11-20 22:54:50,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:50,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1750706661] [2024-11-20 22:54:50,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:50,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:50,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:50,335 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:50,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:50,356 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:50,357 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:50,357 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-11-20 22:54:50,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:50,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1926665416] [2024-11-20 22:54:50,358 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:50,358 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:50,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:50,362 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:50,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:50,364 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:50,364 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:50,364 INFO L85 PathProgramCache]: Analyzing trace with hash -1473183863, now seen corresponding path program 7 times [2024-11-20 22:54:50,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:50,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947487553] [2024-11-20 22:54:50,365 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:50,365 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:50,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,608 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-20 22:54:50,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,700 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,750 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,788 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,825 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,835 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:50,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,838 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-20 22:54:50,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,841 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-20 22:54:50,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,850 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,852 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:50,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,854 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-11-20 22:54:50,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,866 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,871 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:50,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,873 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:50,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,875 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-20 22:54:50,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,877 INFO L134 CoverageAnalysis]: Checked inductivity of 898 backedges. 260 proven. 268 refuted. 0 times theorem prover too weak. 370 trivial. 0 not checked. [2024-11-20 22:54:50,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:50,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947487553] [2024-11-20 22:54:50,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1947487553] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:50,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [296024424] [2024-11-20 22:54:50,878 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-20 22:54:50,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:50,879 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:50,881 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:54:50,882 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Waiting until timeout for monitored process [2024-11-20 22:54:50,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:50,943 INFO L255 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-20 22:54:50,974 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:51,067 INFO L134 CoverageAnalysis]: Checked inductivity of 898 backedges. 260 proven. 268 refuted. 0 times theorem prover too weak. 370 trivial. 0 not checked. [2024-11-20 22:54:51,067 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:51,874 INFO L134 CoverageAnalysis]: Checked inductivity of 898 backedges. 260 proven. 294 refuted. 0 times theorem prover too weak. 344 trivial. 0 not checked. [2024-11-20 22:54:51,874 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [296024424] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:51,875 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:51,875 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13, 17] total 23 [2024-11-20 22:54:51,875 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2013785120] [2024-11-20 22:54:51,875 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:51,918 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:51,918 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:51,918 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:51,918 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:51,918 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:51,918 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:51,918 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:51,918 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:51,918 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration6_Loop [2024-11-20 22:54:51,918 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:51,919 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:51,919 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:51,925 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:51,928 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:51,931 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:51,957 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:51,958 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:51,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:51,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:51,962 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:51,963 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-20 22:54:51,964 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:51,964 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:51,988 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-11-20 22:54:51,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:51,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:51,990 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:51,991 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-20 22:54:51,992 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:51,992 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:52,129 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:52,135 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:52,136 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:52,136 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:52,136 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:52,136 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:52,136 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:52,136 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:52,136 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:52,136 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:52,136 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration6_Loop [2024-11-20 22:54:52,136 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:52,136 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:52,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:52,138 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:52,143 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:52,150 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:52,179 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:52,180 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:52,180 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:52,180 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:52,203 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) [2024-11-20 22:54:52,205 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 [2024-11-20 22:54:52,206 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:52,215 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:52,216 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:52,216 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:52,216 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:52,216 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:52,217 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:52,217 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:52,221 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:52,228 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2024-11-20 22:54:52,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:52,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:52,232 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) [2024-11-20 22:54:52,234 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 [2024-11-20 22:54:52,235 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:52,245 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:52,245 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:52,245 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:52,245 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:52,245 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:52,246 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:52,246 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:52,247 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:52,253 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:52,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:52,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:52,255 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) [2024-11-20 22:54:52,256 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 [2024-11-20 22:54:52,256 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:52,266 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:52,266 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:52,266 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:52,266 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:52,266 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:52,268 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:52,268 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:52,269 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:52,272 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:52,272 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:52,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:52,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:52,273 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) [2024-11-20 22:54:52,274 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 [2024-11-20 22:54:52,275 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:52,275 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:52,275 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:52,275 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-20 22:54:52,281 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 [2024-11-20 22:54:52,282 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:52,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:52,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:52,402 INFO L255 TraceCheckSpWp]: Trace formula consists of 819 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-20 22:54:52,405 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:52,677 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:53,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:53,085 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:53,085 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:53,109 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:53,110 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-20 22:54:53,110 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 362 states and 576 transitions. cyclomatic complexity: 218 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-20 22:54:53,163 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 362 states and 576 transitions. cyclomatic complexity: 218. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 369 states and 584 transitions. Complement of second has 18 states. [2024-11-20 22:54:53,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:53,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-20 22:54:53,164 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-20 22:54:53,165 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 116 letters. Loop has 4 letters. [2024-11-20 22:54:53,165 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:53,165 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:53,178 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:53,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:53,295 INFO L255 TraceCheckSpWp]: Trace formula consists of 819 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-20 22:54:53,298 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:53,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:53,953 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:53,953 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:53,984 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:53,985 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-20 22:54:53,985 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 362 states and 576 transitions. cyclomatic complexity: 218 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-20 22:54:54,073 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 362 states and 576 transitions. cyclomatic complexity: 218. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 377 states and 592 transitions. Complement of second has 17 states. [2024-11-20 22:54:54,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:54,075 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-20 22:54:54,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-20 22:54:54,075 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 116 letters. Loop has 4 letters. [2024-11-20 22:54:54,075 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:54,075 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:54,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:54,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:54,197 INFO L255 TraceCheckSpWp]: Trace formula consists of 819 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-20 22:54:54,201 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:54,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:54,762 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:54,762 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:54,790 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:54,791 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 4 loop predicates [2024-11-20 22:54:54,791 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 362 states and 576 transitions. cyclomatic complexity: 218 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-20 22:54:54,844 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 362 states and 576 transitions. cyclomatic complexity: 218. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 425 states and 667 transitions. Complement of second has 21 states. [2024-11-20 22:54:54,844 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:54,845 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-20 22:54:54,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 20 transitions. [2024-11-20 22:54:54,845 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 116 letters. Loop has 4 letters. [2024-11-20 22:54:54,846 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:54,846 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 120 letters. Loop has 4 letters. [2024-11-20 22:54:54,846 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:54,846 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 116 letters. Loop has 8 letters. [2024-11-20 22:54:54,847 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:54,847 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 425 states and 667 transitions. [2024-11-20 22:54:54,854 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-20 22:54:54,859 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 425 states to 362 states and 576 transitions. [2024-11-20 22:54:54,860 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 155 [2024-11-20 22:54:54,860 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 177 [2024-11-20 22:54:54,860 INFO L73 IsDeterministic]: Start isDeterministic. Operand 362 states and 576 transitions. [2024-11-20 22:54:54,860 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:54,860 INFO L218 hiAutomatonCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-11-20 22:54:54,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 362 states and 576 transitions. [2024-11-20 22:54:54,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 362 to 362. [2024-11-20 22:54:54,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 362 states, 225 states have (on average 1.1511111111111112) internal successors, (259), 225 states have internal predecessors, (259), 83 states have call successors, (99), 48 states have call predecessors, (99), 54 states have return successors, (218), 88 states have call predecessors, (218), 81 states have call successors, (218) [2024-11-20 22:54:54,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 362 states to 362 states and 576 transitions. [2024-11-20 22:54:54,874 INFO L240 hiAutomatonCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-11-20 22:54:54,874 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:54,874 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-20 22:54:54,875 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=402, Unknown=0, NotChecked=0, Total=552 [2024-11-20 22:54:54,875 INFO L87 Difference]: Start difference. First operand 362 states and 576 transitions. Second operand has 24 states, 18 states have (on average 2.9444444444444446) internal successors, (53), 19 states have internal predecessors, (53), 19 states have call successors, (21), 5 states have call predecessors, (21), 6 states have return successors, (23), 10 states have call predecessors, (23), 15 states have call successors, (23) [2024-11-20 22:54:55,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:55,083 INFO L93 Difference]: Finished difference Result 542 states and 862 transitions. [2024-11-20 22:54:55,083 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 542 states and 862 transitions. [2024-11-20 22:54:55,089 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:54:55,090 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 542 states to 0 states and 0 transitions. [2024-11-20 22:54:55,090 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-20 22:54:55,090 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-20 22:54:55,090 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-20 22:54:55,090 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-20 22:54:55,090 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:54:55,090 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:54:55,091 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-20 22:54:55,091 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:54:55,091 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-20 22:54:55,091 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-20 22:54:55,091 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:54:55,091 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-20 22:54:55,098 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 20.11 10:54:55 BoogieIcfgContainer [2024-11-20 22:54:55,098 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-20 22:54:55,099 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-20 22:54:55,099 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-20 22:54:55,099 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-20 22:54:55,099 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:54:40" (3/4) ... [2024-11-20 22:54:55,101 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-20 22:54:55,102 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-20 22:54:55,103 INFO L158 Benchmark]: Toolchain (without parser) took 15608.62ms. Allocated memory was 155.2MB in the beginning and 287.3MB in the end (delta: 132.1MB). Free memory was 101.0MB in the beginning and 160.5MB in the end (delta: -59.5MB). Peak memory consumption was 73.3MB. Max. memory is 16.1GB. [2024-11-20 22:54:55,103 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 155.2MB. Free memory is still 119.3MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:54:55,103 INFO L158 Benchmark]: CACSL2BoogieTranslator took 241.91ms. Allocated memory is still 155.2MB. Free memory was 100.5MB in the beginning and 89.1MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-20 22:54:55,104 INFO L158 Benchmark]: Boogie Procedure Inliner took 28.72ms. Allocated memory is still 155.2MB. Free memory was 89.1MB in the beginning and 87.3MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-20 22:54:55,104 INFO L158 Benchmark]: Boogie Preprocessor took 27.05ms. Allocated memory is still 155.2MB. Free memory was 87.3MB in the beginning and 85.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-20 22:54:55,104 INFO L158 Benchmark]: RCFGBuilder took 273.99ms. Allocated memory is still 155.2MB. Free memory was 85.8MB in the beginning and 75.3MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-20 22:54:55,104 INFO L158 Benchmark]: BuchiAutomizer took 15026.42ms. Allocated memory was 155.2MB in the beginning and 287.3MB in the end (delta: 132.1MB). Free memory was 75.3MB in the beginning and 160.5MB in the end (delta: -85.2MB). Peak memory consumption was 48.1MB. Max. memory is 16.1GB. [2024-11-20 22:54:55,105 INFO L158 Benchmark]: Witness Printer took 3.72ms. Allocated memory is still 287.3MB. Free memory is still 160.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:54:55,106 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.17ms. Allocated memory is still 155.2MB. Free memory is still 119.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 241.91ms. Allocated memory is still 155.2MB. Free memory was 100.5MB in the beginning and 89.1MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 28.72ms. Allocated memory is still 155.2MB. Free memory was 89.1MB in the beginning and 87.3MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 27.05ms. Allocated memory is still 155.2MB. Free memory was 87.3MB in the beginning and 85.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 273.99ms. Allocated memory is still 155.2MB. Free memory was 85.8MB in the beginning and 75.3MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 15026.42ms. Allocated memory was 155.2MB in the beginning and 287.3MB in the end (delta: 132.1MB). Free memory was 75.3MB in the beginning and 160.5MB in the end (delta: -85.2MB). Peak memory consumption was 48.1MB. Max. memory is 16.1GB. * Witness Printer took 3.72ms. Allocated memory is still 287.3MB. Free memory is still 160.5MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One 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. One nondeterministic module has affine ranking function n and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 24 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 14.9s and 7 iterations. TraceHistogramMax:20. Analysis of lassos took 6.9s. Construction of modules took 0.8s. Büchi inclusion checks took 6.9s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 260 StatesRemovedByMinimization, 7 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 489 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 441 mSDsluCounter, 478 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 287 mSDsCounter, 439 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 877 IncrementalHoareTripleChecker+Invalid, 1316 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 439 mSolverCounterUnsat, 191 mSDtfsCounter, 877 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT4 SILN0 SILU0 SILI1 SILT0 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp82 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf92 smp80 dnf100 smp100 tf112 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 24ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.5s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-20 22:54:55,128 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Ended with exit code 0 [2024-11-20 22:54:55,327 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:55,527 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-20 22:54:55,727 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-20 22:54:55,929 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