./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 a046e57d 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-tmp.dk.eval-mul-div-a046e57-m [2024-10-13 17:41:24,683 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-13 17:41:24,739 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-13 17:41:24,755 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-13 17:41:24,755 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-13 17:41:24,780 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-13 17:41:24,780 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-13 17:41:24,781 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-13 17:41:24,781 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-13 17:41:24,781 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-13 17:41:24,782 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-13 17:41:24,782 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-13 17:41:24,782 INFO L153 SettingsManager]: * Use SBE=true [2024-10-13 17:41:24,783 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-13 17:41:24,783 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-13 17:41:24,783 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-13 17:41:24,783 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-13 17:41:24,784 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-13 17:41:24,784 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-13 17:41:24,784 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-13 17:41:24,785 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-13 17:41:24,785 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-13 17:41:24,785 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-13 17:41:24,786 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-13 17:41:24,786 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-13 17:41:24,786 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-13 17:41:24,786 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-13 17:41:24,787 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-13 17:41:24,787 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-13 17:41:24,787 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-13 17:41:24,787 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-13 17:41:24,788 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-13 17:41:24,791 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-13 17:41:24,792 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-13 17:41:24,792 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-13 17:41:24,792 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-13 17:41:24,792 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-13 17:41:24,792 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-13 17:41:24,793 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-13 17:41:24,793 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-10-13 17:41:24,979 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-13 17:41:25,010 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-13 17:41:25,012 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-13 17:41:25,013 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-13 17:41:25,016 INFO L274 PluginConnector]: CDTParser initialized [2024-10-13 17:41:25,017 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05.c [2024-10-13 17:41:26,398 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-13 17:41:26,530 INFO L384 CDTParser]: Found 1 translation units. [2024-10-13 17:41:26,531 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci05.c [2024-10-13 17:41:26,536 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1e3d03924/f10d2b947e064ee1815fb18a8d8e8a8c/FLAGdfe392f65 [2024-10-13 17:41:26,943 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1e3d03924/f10d2b947e064ee1815fb18a8d8e8a8c [2024-10-13 17:41:26,946 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-13 17:41:26,947 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-13 17:41:26,948 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:26,948 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-13 17:41:26,952 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-13 17:41:26,952 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,953 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6ff6e7ce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:26, skipping insertion in model container [2024-10-13 17:41:26,953 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:26" (1/1) ... [2024-10-13 17:41:26,968 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-13 17:41:27,096 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:27,104 INFO L200 MainTranslator]: Completed pre-run [2024-10-13 17:41:27,114 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:27,125 INFO L204 MainTranslator]: Completed translation [2024-10-13 17:41:27,126 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27 WrapperNode [2024-10-13 17:41:27,126 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:27,127 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:27,127 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-13 17:41:27,127 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-13 17:41:27,132 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,140 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,153 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2024-10-13 17:41:27,154 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:27,155 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-13 17:41:27,155 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-13 17:41:27,155 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-13 17:41:27,163 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,163 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,165 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,172 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-13 17:41:27,173 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,173 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,174 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,176 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,176 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,177 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,178 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-13 17:41:27,183 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-13 17:41:27,183 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-13 17:41:27,183 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-13 17:41:27,183 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (1/1) ... [2024-10-13 17:41:27,187 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,218 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-10-13 17:41:27,220 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-10-13 17:41:27,252 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-10-13 17:41:27,252 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-10-13 17:41:27,252 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-13 17:41:27,252 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-13 17:41:27,252 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-13 17:41:27,253 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-13 17:41:27,297 INFO L238 CfgBuilder]: Building ICFG [2024-10-13 17:41:27,299 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-13 17:41:27,359 INFO L? ?]: Removed 8 outVars from TransFormulas that were not future-live. [2024-10-13 17:41:27,359 INFO L287 CfgBuilder]: Performing block encoding [2024-10-13 17:41:27,368 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-13 17:41:27,368 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-13 17:41:27,369 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:27 BoogieIcfgContainer [2024-10-13 17:41:27,369 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-13 17:41:27,369 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-13 17:41:27,370 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-13 17:41:27,372 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-13 17:41:27,373 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:27,373 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 13.10 05:41:26" (1/3) ... [2024-10-13 17:41:27,374 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@156d1032 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:27, skipping insertion in model container [2024-10-13 17:41:27,374 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:27,374 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:27" (2/3) ... [2024-10-13 17:41:27,374 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@156d1032 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:27, skipping insertion in model container [2024-10-13 17:41:27,374 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:27,374 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:27" (3/3) ... [2024-10-13 17:41:27,376 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci05.c [2024-10-13 17:41:27,414 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-13 17:41:27,414 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-13 17:41:27,414 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-13 17:41:27,414 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-13 17:41:27,415 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-13 17:41:27,415 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-13 17:41:27,415 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-13 17:41:27,415 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-13 17:41:27,420 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-10-13 17:41:27,432 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:27,433 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:27,433 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:27,437 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:27,437 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:27,437 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-13 17:41:27,437 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-10-13 17:41:27,438 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:27,439 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:27,439 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:27,439 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:27,439 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:27,444 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-10-13 17:41:27,444 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-10-13 17:41:27,448 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,448 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-10-13 17:41:27,454 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:27,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1288913971] [2024-10-13 17:41:27,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:27,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:27,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,514 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:27,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,531 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:27,533 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,533 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-10-13 17:41:27,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:27,534 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [474227465] [2024-10-13 17:41:27,534 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:27,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:27,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,541 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:27,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,545 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:27,546 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:27,546 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-10-13 17:41:27,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:27,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1076477711] [2024-10-13 17:41:27,547 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:27,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:27,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,554 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:27,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:27,560 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:27,666 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:27,666 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:27,666 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:27,666 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:27,667 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:27,667 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,667 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:27,667 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:27,667 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration1_Loop [2024-10-13 17:41:27,667 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:27,667 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:27,679 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,686 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,688 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,698 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,754 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:27,754 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:27,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,758 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-10-13 17:41:27,763 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-10-13 17:41:27,765 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,765 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,781 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:27,782 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:27,792 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-10-13 17:41:27,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,794 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-10-13 17:41:27,796 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-10-13 17:41:27,797 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,798 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,813 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:27,813 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-10-13 17:41:27,824 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-10-13 17:41:27,824 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,825 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,830 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-10-13 17:41:27,832 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-10-13 17:41:27,833 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,833 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,845 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:27,845 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:27,863 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-10-13 17:41:27,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,864 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,867 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-10-13 17:41:27,875 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-10-13 17:41:27,880 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:27,881 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,902 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:27,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:27,904 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-10-13 17:41:27,905 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-10-13 17:41:27,906 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:27,906 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:27,960 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:27,964 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-10-13 17:41:27,965 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:27,965 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:27,965 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:27,965 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:27,965 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:27,966 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:27,966 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:27,966 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:27,966 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration1_Loop [2024-10-13 17:41:27,966 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:27,966 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:27,967 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,974 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,981 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,984 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:27,996 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:28,058 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:28,065 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:28,070 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:28,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,071 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-10-13 17:41:28,072 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-10-13 17:41:28,074 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:28,084 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:28,085 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:28,085 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:28,085 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:28,085 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:28,087 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:28,087 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:28,089 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:28,100 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-13 17:41:28,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:28,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,102 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-10-13 17:41:28,104 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-10-13 17:41:28,105 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-10-13 17:41:28,115 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:28,115 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:28,115 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:28,115 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:28,115 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:28,116 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:28,116 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:28,117 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:28,129 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:28,130 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:28,130 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,131 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-10-13 17:41:28,132 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-10-13 17:41:28,134 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-10-13 17:41:28,143 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:28,144 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:28,144 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:28,144 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:28,144 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:28,144 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:28,145 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:28,146 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:28,156 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-10-13 17:41:28,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:28,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,158 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-10-13 17:41:28,159 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-10-13 17:41:28,161 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-10-13 17:41:28,170 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:28,171 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:28,171 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:28,171 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:28,171 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:28,172 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:28,172 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:28,174 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:28,176 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:28,176 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:28,178 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:28,178 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,201 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-10-13 17:41:28,202 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-10-13 17:41:28,203 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:28,204 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:28,204 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:28,204 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-13 17:41:28,215 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-10-13 17:41:28,219 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:28,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,251 INFO L255 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-13 17:41:28,252 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:28,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,267 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:28,269 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:28,325 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-10-13 17:41:28,368 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:28,402 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-10-13 17:41:28,404 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-10-13 17:41:28,470 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-10-13 17:41:28,472 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-10-13 17:41:28,476 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-10-13 17:41:28,476 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-13 17:41:28,477 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-13 17:41:28,478 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:28,478 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-13 17:41:28,478 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:28,479 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-13 17:41:28,479 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:28,479 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-10-13 17:41:28,482 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,486 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-10-13 17:41:28,486 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-13 17:41:28,487 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-13 17:41:28,487 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-13 17:41:28,488 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:28,488 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-13 17:41:28,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-13 17:41:28,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-13 17:41:28,506 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-10-13 17:41:28,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-13 17:41:28,508 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:41:28,508 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:41:28,508 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-13 17:41:28,508 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-13 17:41:28,509 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,509 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:28,509 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:28,509 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:28,510 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:28,510 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-10-13 17:41:28,510 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-10-13 17:41:28,510 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,510 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-10-13 17:41:28,511 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,511 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [850227864] [2024-10-13 17:41:28,511 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,511 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,593 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:28,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,647 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:41:28,648 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:28,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [850227864] [2024-10-13 17:41:28,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [850227864] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:28,648 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:28,649 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:41:28,649 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [134930471] [2024-10-13 17:41:28,650 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:28,651 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:28,651 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,651 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-10-13 17:41:28,652 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,652 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1584968287] [2024-10-13 17:41:28,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,652 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,688 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:41:28,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,711 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:41:28,711 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:28,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1584968287] [2024-10-13 17:41:28,712 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1584968287] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:28,712 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:28,712 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:41:28,712 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [833320728] [2024-10-13 17:41:28,712 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:28,712 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:41:28,713 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:28,714 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-13 17:41:28,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-13 17:41:28,716 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-10-13 17:41:28,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:28,763 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-13 17:41:28,764 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-13 17:41:28,765 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,765 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-13 17:41:28,766 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-13 17:41:28,766 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-13 17:41:28,766 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-13 17:41:28,766 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:28,766 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:28,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-13 17:41:28,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-13 17:41:28,768 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-10-13 17:41:28,769 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-13 17:41:28,769 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:28,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-13 17:41:28,770 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:28,770 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-13 17:41:28,770 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-13 17:41:28,771 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:28,771 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:28,771 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:28,772 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:28,772 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-13 17:41:28,772 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-10-13 17:41:28,772 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-10-13 17:41:28,772 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,773 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-10-13 17:41:28,773 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,773 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1640697427] [2024-10-13 17:41:28,773 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,773 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:28,779 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:28,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:28,786 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:28,786 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,786 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-10-13 17:41:28,786 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2142211205] [2024-10-13 17:41:28,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,787 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:28,795 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:28,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:28,805 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:28,809 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,809 INFO L85 PathProgramCache]: Analyzing trace with hash 998757605, now seen corresponding path program 1 times [2024-10-13 17:41:28,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777724405] [2024-10-13 17:41:28,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:28,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,906 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:28,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,936 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-10-13 17:41:28,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,951 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:28,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,957 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:28,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:28,963 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 22 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-10-13 17:41:28,964 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:28,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [777724405] [2024-10-13 17:41:28,965 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [777724405] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:28,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [628598790] [2024-10-13 17:41:28,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:28,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,968 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-10-13 17:41:28,980 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-10-13 17:41:29,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:29,018 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:29,019 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:29,045 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 38 proven. 1 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-10-13 17:41:29,046 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:29,114 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 22 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-10-13 17:41:29,115 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [628598790] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:29,115 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:29,115 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2024-10-13 17:41:29,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [776138266] [2024-10-13 17:41:29,115 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:29,270 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:29,270 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:29,270 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:29,270 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:29,270 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:29,270 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,270 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:29,270 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:29,270 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration3_Loop [2024-10-13 17:41:29,270 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:29,271 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:29,271 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,274 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,275 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,279 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,281 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,310 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:29,311 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:29,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,318 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-10-13 17:41:29,319 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-10-13 17:41:29,320 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,320 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,333 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:29,334 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-10-13 17:41:29,344 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:29,345 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,345 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,346 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-10-13 17:41:29,351 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-10-13 17:41:29,351 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,351 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,362 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:29,362 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-10-13 17:41:29,372 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:29,373 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,373 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,374 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-10-13 17:41:29,375 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-10-13 17:41:29,376 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,376 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,397 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:29,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,399 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-10-13 17:41:29,400 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-10-13 17:41:29,402 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:29,402 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,414 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:29,426 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:29,426 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:29,426 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:29,427 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:29,427 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:29,427 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:29,427 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,427 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:29,427 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:29,427 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration3_Loop [2024-10-13 17:41:29,427 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:29,427 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:29,429 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,435 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,436 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,444 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,456 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,580 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:29,580 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:29,580 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,580 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,581 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-10-13 17:41:29,587 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-10-13 17:41:29,588 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-10-13 17:41:29,597 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:29,597 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:29,597 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:29,597 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:29,597 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:29,598 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:29,598 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:29,600 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:29,610 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-10-13 17:41:29,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,611 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,615 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-10-13 17:41:29,615 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-10-13 17:41:29,616 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-10-13 17:41:29,626 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:29,626 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:29,626 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:29,626 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:29,626 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:29,627 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:29,627 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:29,628 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:29,639 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-10-13 17:41:29,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,640 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-10-13 17:41:29,642 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-10-13 17:41:29,643 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-10-13 17:41:29,653 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:29,653 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:29,653 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:29,653 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:29,653 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:29,654 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:29,655 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:29,656 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:29,659 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:29,660 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:29,660 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,660 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,662 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-10-13 17:41:29,665 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-10-13 17:41:29,666 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:29,666 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:29,666 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:29,666 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-13 17:41:29,677 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-10-13 17:41:29,677 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:29,687 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:29,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:29,703 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:29,704 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:29,770 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-10-13 17:41:29,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:29,817 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:29,818 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:29,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-10-13 17:41:29,919 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-10-13 17:41:29,919 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-10-13 17:41:30,121 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-10-13 17:41:30,125 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-10-13 17:41:30,126 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-10-13 17:41:30,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-10-13 17:41:30,127 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-10-13 17:41:30,128 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,131 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-10-13 17:41:30,132 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,132 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-10-13 17:41:30,132 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,133 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-10-13 17:41:30,141 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-13 17:41:30,148 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-10-13 17:41:30,148 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-10-13 17:41:30,148 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-13 17:41:30,148 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-10-13 17:41:30,149 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:30,149 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-10-13 17:41:30,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-10-13 17:41:30,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-10-13 17:41:30,168 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-10-13 17:41:30,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-10-13 17:41:30,169 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-10-13 17:41:30,169 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:30,170 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-13 17:41:30,170 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2024-10-13 17:41:30,170 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-10-13 17:41:30,248 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:30,248 INFO L93 Difference]: Finished difference Result 44 states and 57 transitions. [2024-10-13 17:41:30,248 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 44 states and 57 transitions. [2024-10-13 17:41:30,249 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:30,250 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 44 states to 41 states and 53 transitions. [2024-10-13 17:41:30,250 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 34 [2024-10-13 17:41:30,250 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 34 [2024-10-13 17:41:30,250 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 53 transitions. [2024-10-13 17:41:30,250 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:30,251 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 53 transitions. [2024-10-13 17:41:30,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 53 transitions. [2024-10-13 17:41:30,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 38. [2024-10-13 17:41:30,256 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-10-13 17:41:30,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2024-10-13 17:41:30,257 INFO L240 hiAutomatonCegarLoop]: Abstraction has 38 states and 47 transitions. [2024-10-13 17:41:30,257 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-13 17:41:30,258 INFO L425 stractBuchiCegarLoop]: Abstraction has 38 states and 47 transitions. [2024-10-13 17:41:30,258 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-13 17:41:30,258 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 38 states and 47 transitions. [2024-10-13 17:41:30,258 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:30,258 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:30,258 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:30,260 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:30,260 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-13 17:41:30,260 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-10-13 17:41:30,260 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-10-13 17:41:30,260 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,260 INFO L85 PathProgramCache]: Analyzing trace with hash 62997961, now seen corresponding path program 2 times [2024-10-13 17:41:30,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [183879173] [2024-10-13 17:41:30,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,260 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,267 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:30,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,273 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:30,274 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,274 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 2 times [2024-10-13 17:41:30,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1252314872] [2024-10-13 17:41:30,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,278 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:30,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,282 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:30,283 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,283 INFO L85 PathProgramCache]: Analyzing trace with hash 969547889, now seen corresponding path program 3 times [2024-10-13 17:41:30,283 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,283 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1715073333] [2024-10-13 17:41:30,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,283 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,348 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:30,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:30,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:30,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-13 17:41:30,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,399 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:30,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,401 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:30,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,403 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 16 proven. 46 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2024-10-13 17:41:30,403 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:30,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1715073333] [2024-10-13 17:41:30,403 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1715073333] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:30,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [639689005] [2024-10-13 17:41:30,403 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-13 17:41:30,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:30,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,407 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-10-13 17:41:30,410 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-10-13 17:41:30,450 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-10-13 17:41:30,451 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:30,452 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:30,453 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:30,533 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 35 proven. 47 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-10-13 17:41:30,533 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:30,825 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 35 proven. 49 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-10-13 17:41:30,826 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [639689005] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:30,826 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:30,826 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 12] total 21 [2024-10-13 17:41:30,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1622919579] [2024-10-13 17:41:30,826 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:30,973 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:30,973 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:30,973 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:30,973 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:30,973 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:30,973 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,973 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:30,974 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:30,974 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration4_Loop [2024-10-13 17:41:30,974 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:30,974 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:30,975 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,977 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,979 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,983 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,987 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,017 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:31,017 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:31,017 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,017 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,021 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-10-13 17:41:31,023 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-10-13 17:41:31,024 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:31,024 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,039 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:31,039 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-10-13 17:41:31,050 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-10-13 17:41:31,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,052 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-10-13 17:41:31,053 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-10-13 17:41:31,053 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:31,054 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,065 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:31,066 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:31,077 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2024-10-13 17:41:31,078 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,078 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,079 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-10-13 17:41:31,080 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-10-13 17:41:31,080 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:31,080 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,103 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2024-10-13 17:41:31,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,105 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-10-13 17:41:31,108 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-10-13 17:41:31,109 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:31,109 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:31,135 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:31,156 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-10-13 17:41:31,157 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:31,157 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:31,157 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:31,157 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:31,157 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:31,157 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,157 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:31,157 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:31,157 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration4_Loop [2024-10-13 17:41:31,157 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:31,157 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:31,158 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,164 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,171 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,173 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,179 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:31,221 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:31,221 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:31,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,223 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-10-13 17:41:31,227 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-10-13 17:41:31,228 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-10-13 17:41:31,238 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:31,238 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:31,238 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:31,238 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:31,238 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:31,239 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:31,239 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:31,241 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:31,251 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-10-13 17:41:31,251 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,252 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-10-13 17:41:31,253 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-10-13 17:41:31,254 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-10-13 17:41:31,265 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:31,265 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:31,265 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:31,265 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:31,265 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:31,270 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:31,270 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:31,272 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:31,274 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-13 17:41:31,274 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:31,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:31,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:31,279 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-10-13 17:41:31,281 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-10-13 17:41:31,281 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:31,281 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:31,281 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:31,281 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-13 17:41:31,291 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-10-13 17:41:31,292 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:31,301 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:31,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:31,340 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-13 17:41:31,341 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:31,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:31,602 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:31,603 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:31,767 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:31,767 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-10-13 17:41:31,768 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-10-13 17:41:31,877 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-10-13 17:41:31,877 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-10-13 17:41:31,878 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-10-13 17:41:31,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-10-13 17:41:31,879 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 24 letters. Loop has 22 letters. [2024-10-13 17:41:31,879 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:31,879 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:31,889 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:31,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:31,918 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-13 17:41:31,918 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:32,067 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:32,068 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,164 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:32,165 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-10-13 17:41:32,165 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-10-13 17:41:32,237 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-10-13 17:41:32,237 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-10-13 17:41:32,238 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-10-13 17:41:32,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-10-13 17:41:32,238 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 24 letters. Loop has 22 letters. [2024-10-13 17:41:32,238 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,239 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:32,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:32,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:32,268 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-13 17:41:32,269 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,373 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-10-13 17:41:32,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:32,421 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:32,422 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:32,511 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:32,512 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-10-13 17:41:32,512 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-10-13 17:41:32,720 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-10-13 17:41:32,727 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-10-13 17:41:32,728 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-10-13 17:41:32,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-10-13 17:41:32,729 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 24 letters. Loop has 22 letters. [2024-10-13 17:41:32,729 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,729 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 46 letters. Loop has 22 letters. [2024-10-13 17:41:32,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,730 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 24 letters. Loop has 44 letters. [2024-10-13 17:41:32,731 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:32,735 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 331 states and 432 transitions. [2024-10-13 17:41:32,744 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:32,752 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 331 states to 215 states and 294 transitions. [2024-10-13 17:41:32,752 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 97 [2024-10-13 17:41:32,752 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 113 [2024-10-13 17:41:32,753 INFO L73 IsDeterministic]: Start isDeterministic. Operand 215 states and 294 transitions. [2024-10-13 17:41:32,753 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:32,753 INFO L218 hiAutomatonCegarLoop]: Abstraction has 215 states and 294 transitions. [2024-10-13 17:41:32,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states and 294 transitions. [2024-10-13 17:41:32,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 173. [2024-10-13 17:41:32,775 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-10-13 17:41:32,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 225 transitions. [2024-10-13 17:41:32,778 INFO L240 hiAutomatonCegarLoop]: Abstraction has 173 states and 225 transitions. [2024-10-13 17:41:32,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:32,778 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-13 17:41:32,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2024-10-13 17:41:32,780 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-10-13 17:41:33,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:33,007 INFO L93 Difference]: Finished difference Result 344 states and 500 transitions. [2024-10-13 17:41:33,007 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 344 states and 500 transitions. [2024-10-13 17:41:33,010 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:33,017 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 344 states to 334 states and 487 transitions. [2024-10-13 17:41:33,017 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 170 [2024-10-13 17:41:33,018 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 190 [2024-10-13 17:41:33,018 INFO L73 IsDeterministic]: Start isDeterministic. Operand 334 states and 487 transitions. [2024-10-13 17:41:33,018 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:33,018 INFO L218 hiAutomatonCegarLoop]: Abstraction has 334 states and 487 transitions. [2024-10-13 17:41:33,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states and 487 transitions. [2024-10-13 17:41:33,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 265. [2024-10-13 17:41:33,036 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-10-13 17:41:33,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 265 states to 265 states and 394 transitions. [2024-10-13 17:41:33,038 INFO L240 hiAutomatonCegarLoop]: Abstraction has 265 states and 394 transitions. [2024-10-13 17:41:33,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-10-13 17:41:33,039 INFO L425 stractBuchiCegarLoop]: Abstraction has 265 states and 394 transitions. [2024-10-13 17:41:33,039 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-13 17:41:33,039 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 265 states and 394 transitions. [2024-10-13 17:41:33,041 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:33,041 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:33,041 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:33,042 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 10, 9, 7, 7, 5, 5, 4, 4, 3, 2, 1, 1, 1] [2024-10-13 17:41:33,042 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:33,042 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-10-13 17:41:33,042 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-10-13 17:41:33,043 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:33,043 INFO L85 PathProgramCache]: Analyzing trace with hash -627327765, now seen corresponding path program 4 times [2024-10-13 17:41:33,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:33,043 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [363972274] [2024-10-13 17:41:33,043 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:33,043 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:33,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:33,055 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:33,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:33,066 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:33,066 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:33,066 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-10-13 17:41:33,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:33,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [944602843] [2024-10-13 17:41:33,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:33,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:33,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:33,069 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:33,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:33,070 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:33,070 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:33,070 INFO L85 PathProgramCache]: Analyzing trace with hash 2068668293, now seen corresponding path program 5 times [2024-10-13 17:41:33,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:33,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1056626861] [2024-10-13 17:41:33,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:33,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:33,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,167 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:33,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,223 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:33,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,252 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:33,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,282 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:33,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,289 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:33,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,293 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-13 17:41:33,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,296 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-13 17:41:33,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,320 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:33,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,322 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:33,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:33,324 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 115 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-10-13 17:41:33,325 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:33,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1056626861] [2024-10-13 17:41:33,325 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1056626861] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:33,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [787347804] [2024-10-13 17:41:33,325 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-10-13 17:41:33,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:33,325 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:33,327 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-10-13 17:41:33,328 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-10-13 17:41:33,369 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2024-10-13 17:41:33,369 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:33,370 INFO L255 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:33,371 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:33,423 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 115 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-10-13 17:41:33,423 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:33,854 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 130 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2024-10-13 17:41:33,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [787347804] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:33,855 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:33,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12, 15] total 20 [2024-10-13 17:41:33,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [341004129] [2024-10-13 17:41:33,855 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:33,887 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:33,887 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:33,887 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:33,887 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:33,887 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:33,887 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:33,887 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:33,888 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:33,888 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration5_Loop [2024-10-13 17:41:33,888 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:33,888 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:33,888 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:33,890 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:33,892 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:33,894 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:33,899 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:33,925 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:33,925 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:33,925 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:33,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:33,931 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-10-13 17:41:33,932 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-10-13 17:41:33,933 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:33,933 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:33,945 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:33,945 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-10-13 17:41:33,955 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-10-13 17:41:33,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:33,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:33,956 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-10-13 17:41:33,957 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-10-13 17:41:33,958 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:33,958 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:33,969 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:33,969 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:33,979 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-10-13 17:41:33,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:33,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:33,981 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-10-13 17:41:33,982 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-10-13 17:41:33,984 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:33,984 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:33,995 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:33,996 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:34,006 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-10-13 17:41:34,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,007 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-10-13 17:41:34,008 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-10-13 17:41:34,009 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:34,010 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,030 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-10-13 17:41:34,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,032 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-10-13 17:41:34,033 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-10-13 17:41:34,033 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:34,033 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,061 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:34,065 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2024-10-13 17:41:34,065 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:34,065 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:34,065 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:34,065 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:34,066 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:34,066 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,066 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:34,066 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:34,066 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration5_Loop [2024-10-13 17:41:34,066 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:34,066 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:34,066 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,069 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,070 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,071 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,076 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:34,099 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:34,099 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:34,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,100 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-10-13 17:41:34,105 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-10-13 17:41:34,106 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-10-13 17:41:34,125 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,126 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,126 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,126 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,126 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,126 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,126 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,127 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:34,144 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-10-13 17:41:34,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,148 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-10-13 17:41:34,152 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-10-13 17:41:34,153 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-10-13 17:41:34,163 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,163 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,163 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,163 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,163 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,163 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,163 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,165 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:34,176 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:34,179 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,180 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-10-13 17:41:34,181 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-10-13 17:41:34,182 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-10-13 17:41:34,192 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,192 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,192 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,192 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,192 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,193 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,193 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,194 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:34,206 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-10-13 17:41:34,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,207 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-10-13 17:41:34,209 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-10-13 17:41:34,209 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-10-13 17:41:34,219 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:34,219 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:34,219 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:34,219 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:34,219 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:34,220 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:34,220 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:34,222 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:34,223 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-13 17:41:34,223 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:34,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:34,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:34,225 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-10-13 17:41:34,226 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-10-13 17:41:34,226 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:34,226 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:34,226 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:34,226 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-13 17:41:34,237 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-10-13 17:41:34,238 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:34,245 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:34,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,321 INFO L255 TraceCheckSpWp]: Trace formula consists of 532 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,324 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:34,587 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-10-13 17:41:34,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,690 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,690 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:34,707 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:34,708 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-10-13 17:41:34,708 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-10-13 17:41:34,753 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-10-13 17:41:34,754 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-10-13 17:41:34,754 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-10-13 17:41:34,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-13 17:41:34,754 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 71 letters. Loop has 4 letters. [2024-10-13 17:41:34,755 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:34,755 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:34,764 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:34,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:34,819 INFO L255 TraceCheckSpWp]: Trace formula consists of 532 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-10-13 17:41:34,821 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:35,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,146 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:35,147 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:35,164 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:35,165 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-10-13 17:41:35,165 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-10-13 17:41:35,209 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-10-13 17:41:35,210 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-10-13 17:41:35,210 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-10-13 17:41:35,211 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-13 17:41:35,211 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 71 letters. Loop has 4 letters. [2024-10-13 17:41:35,211 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,211 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:35,219 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:35,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,278 INFO L255 TraceCheckSpWp]: Trace formula consists of 532 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-10-13 17:41:35,280 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:35,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:35,659 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:35,659 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:35,675 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:35,676 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-10-13 17:41:35,676 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-10-13 17:41:35,728 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-10-13 17:41:35,729 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-10-13 17:41:35,729 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-10-13 17:41:35,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-10-13 17:41:35,729 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 71 letters. Loop has 4 letters. [2024-10-13 17:41:35,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,730 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 75 letters. Loop has 4 letters. [2024-10-13 17:41:35,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,730 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 71 letters. Loop has 8 letters. [2024-10-13 17:41:35,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:35,730 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 340 states and 477 transitions. [2024-10-13 17:41:35,733 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:35,736 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 340 states to 279 states and 410 transitions. [2024-10-13 17:41:35,736 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 132 [2024-10-13 17:41:35,736 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 137 [2024-10-13 17:41:35,736 INFO L73 IsDeterministic]: Start isDeterministic. Operand 279 states and 410 transitions. [2024-10-13 17:41:35,736 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:35,736 INFO L218 hiAutomatonCegarLoop]: Abstraction has 279 states and 410 transitions. [2024-10-13 17:41:35,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 279 states and 410 transitions. [2024-10-13 17:41:35,742 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 279 to 271. [2024-10-13 17:41:35,742 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-10-13 17:41:35,744 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 271 states to 271 states and 402 transitions. [2024-10-13 17:41:35,744 INFO L240 hiAutomatonCegarLoop]: Abstraction has 271 states and 402 transitions. [2024-10-13 17:41:35,744 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:35,744 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-13 17:41:35,744 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=275, Unknown=0, NotChecked=0, Total=380 [2024-10-13 17:41:35,745 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-10-13 17:41:35,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:35,879 INFO L93 Difference]: Finished difference Result 483 states and 750 transitions. [2024-10-13 17:41:35,879 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 483 states and 750 transitions. [2024-10-13 17:41:35,883 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:35,888 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 483 states to 478 states and 743 transitions. [2024-10-13 17:41:35,888 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 247 [2024-10-13 17:41:35,888 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 254 [2024-10-13 17:41:35,889 INFO L73 IsDeterministic]: Start isDeterministic. Operand 478 states and 743 transitions. [2024-10-13 17:41:35,889 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:35,889 INFO L218 hiAutomatonCegarLoop]: Abstraction has 478 states and 743 transitions. [2024-10-13 17:41:35,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 478 states and 743 transitions. [2024-10-13 17:41:35,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 478 to 362. [2024-10-13 17:41:35,901 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-10-13 17:41:35,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 362 states to 362 states and 576 transitions. [2024-10-13 17:41:35,903 INFO L240 hiAutomatonCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-10-13 17:41:35,903 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-13 17:41:35,905 INFO L425 stractBuchiCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-10-13 17:41:35,905 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-13 17:41:35,905 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 362 states and 576 transitions. [2024-10-13 17:41:35,907 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:35,907 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:35,907 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:35,910 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [20, 17, 15, 12, 11, 8, 8, 7, 7, 5, 3, 1, 1, 1] [2024-10-13 17:41:35,911 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:35,911 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; 6270#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; 6395#L17 assume !(~n < 1); 6367#L19 assume !(1 == ~n); 6327#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; 6286#L17 assume !(~n < 1); 6269#L19 assume !(1 == ~n); 6271#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; 6270#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); 6285#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-10-13 17:41:35,911 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-10-13 17:41:35,912 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:35,912 INFO L85 PathProgramCache]: Analyzing trace with hash 664454499, now seen corresponding path program 6 times [2024-10-13 17:41:35,912 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:35,912 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752327107] [2024-10-13 17:41:35,912 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:35,912 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:35,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:35,926 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:35,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:35,947 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:35,947 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:35,947 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-10-13 17:41:35,947 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:35,947 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [34509993] [2024-10-13 17:41:35,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:35,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:35,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:35,957 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:35,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:35,959 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:35,959 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:35,959 INFO L85 PathProgramCache]: Analyzing trace with hash -1473183863, now seen corresponding path program 7 times [2024-10-13 17:41:35,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:35,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1699980183] [2024-10-13 17:41:35,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:35,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:35,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,174 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-13 17:41:36,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,264 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,305 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,333 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,357 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:36,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,367 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-13 17:41:36,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-13 17:41:36,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,376 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,377 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:36,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,379 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-13 17:41:36,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,386 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:36,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,390 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:36,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,392 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-13 17:41:36,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,393 INFO L134 CoverageAnalysis]: Checked inductivity of 898 backedges. 260 proven. 268 refuted. 0 times theorem prover too weak. 370 trivial. 0 not checked. [2024-10-13 17:41:36,394 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:36,394 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1699980183] [2024-10-13 17:41:36,394 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1699980183] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:36,394 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2088879484] [2024-10-13 17:41:36,394 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-10-13 17:41:36,394 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:36,394 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:36,398 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-10-13 17:41:36,403 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-10-13 17:41:36,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:36,458 INFO L255 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-10-13 17:41:36,460 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:36,522 INFO L134 CoverageAnalysis]: Checked inductivity of 898 backedges. 260 proven. 268 refuted. 0 times theorem prover too weak. 370 trivial. 0 not checked. [2024-10-13 17:41:36,522 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:37,154 INFO L134 CoverageAnalysis]: Checked inductivity of 898 backedges. 260 proven. 294 refuted. 0 times theorem prover too weak. 344 trivial. 0 not checked. [2024-10-13 17:41:37,155 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2088879484] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:37,155 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:37,155 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13, 17] total 23 [2024-10-13 17:41:37,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1853560913] [2024-10-13 17:41:37,155 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:37,194 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:37,194 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:37,194 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:37,194 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:37,194 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:37,194 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,194 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:37,194 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:37,194 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration6_Loop [2024-10-13 17:41:37,194 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:37,194 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:37,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,201 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,202 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,204 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:37,229 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:37,229 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:37,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:37,233 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-10-13 17:41:37,234 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-10-13 17:41:37,235 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:37,235 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:37,275 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:37,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:37,275 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:37,276 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-10-13 17:41:37,278 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-10-13 17:41:37,279 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:37,279 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:38,480 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:38,485 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-10-13 17:41:38,486 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:38,486 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:38,486 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:38,486 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:38,486 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:38,486 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:38,486 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:38,486 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:38,486 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci05.c_Iteration6_Loop [2024-10-13 17:41:38,486 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:38,487 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:38,487 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:38,489 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:38,490 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:38,496 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:38,520 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:38,521 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:38,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:38,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:38,522 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-10-13 17:41:38,527 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-10-13 17:41:38,527 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-10-13 17:41:38,537 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:38,537 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:38,537 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:38,538 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:38,538 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:38,538 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:38,538 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:38,539 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:38,550 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:38,550 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:38,551 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:38,552 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-10-13 17:41:38,555 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-10-13 17:41:38,556 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-10-13 17:41:38,565 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:38,566 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:38,566 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:38,566 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:38,566 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:38,566 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:38,566 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:38,570 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:38,585 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-10-13 17:41:38,585 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:38,585 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:38,586 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-10-13 17:41:38,587 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-10-13 17:41:38,588 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-10-13 17:41:38,600 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:38,600 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:38,600 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:38,600 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:38,600 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:38,601 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:38,602 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:38,604 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:38,611 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:38,611 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:38,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:38,611 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:38,612 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-10-13 17:41:38,640 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-10-13 17:41:38,641 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:38,641 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:38,641 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:38,641 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-13 17:41:38,652 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-10-13 17:41:38,652 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:38,661 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:38,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:38,746 INFO L255 TraceCheckSpWp]: Trace formula consists of 819 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-10-13 17:41:38,748 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:39,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:39,265 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:39,266 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:39,290 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:39,290 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-10-13 17:41:39,290 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-10-13 17:41:39,327 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-10-13 17:41:39,328 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-10-13 17:41:39,328 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-10-13 17:41:39,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-13 17:41:39,328 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 116 letters. Loop has 4 letters. [2024-10-13 17:41:39,329 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:39,329 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:39,336 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:39,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:39,419 INFO L255 TraceCheckSpWp]: Trace formula consists of 819 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-10-13 17:41:39,422 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:39,561 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Ended with exit code 0 [2024-10-13 17:41:39,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:39,964 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:39,964 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:39,987 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:39,988 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-10-13 17:41:39,988 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-10-13 17:41:40,047 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-10-13 17:41:40,048 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-10-13 17:41:40,048 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-10-13 17:41:40,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-10-13 17:41:40,049 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 116 letters. Loop has 4 letters. [2024-10-13 17:41:40,049 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:40,049 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:40,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:40,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:40,144 INFO L255 TraceCheckSpWp]: Trace formula consists of 819 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-10-13 17:41:40,146 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:40,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:40,724 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:40,724 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:40,747 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:40,748 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-10-13 17:41:40,748 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-10-13 17:41:40,793 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-10-13 17:41:40,793 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-10-13 17:41:40,794 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-10-13 17:41:40,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 20 transitions. [2024-10-13 17:41:40,794 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 116 letters. Loop has 4 letters. [2024-10-13 17:41:40,794 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:40,794 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 120 letters. Loop has 4 letters. [2024-10-13 17:41:40,794 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:40,795 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 116 letters. Loop has 8 letters. [2024-10-13 17:41:40,795 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:40,795 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 425 states and 667 transitions. [2024-10-13 17:41:40,798 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:40,801 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 425 states to 362 states and 576 transitions. [2024-10-13 17:41:40,802 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 155 [2024-10-13 17:41:40,802 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 177 [2024-10-13 17:41:40,802 INFO L73 IsDeterministic]: Start isDeterministic. Operand 362 states and 576 transitions. [2024-10-13 17:41:40,802 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:40,802 INFO L218 hiAutomatonCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-10-13 17:41:40,802 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 362 states and 576 transitions. [2024-10-13 17:41:40,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 362 to 362. [2024-10-13 17:41:40,808 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-10-13 17:41:40,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 362 states to 362 states and 576 transitions. [2024-10-13 17:41:40,810 INFO L240 hiAutomatonCegarLoop]: Abstraction has 362 states and 576 transitions. [2024-10-13 17:41:40,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:40,810 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-13 17:41:40,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=402, Unknown=0, NotChecked=0, Total=552 [2024-10-13 17:41:40,810 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-10-13 17:41:40,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:40,979 INFO L93 Difference]: Finished difference Result 542 states and 862 transitions. [2024-10-13 17:41:40,979 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 542 states and 862 transitions. [2024-10-13 17:41:40,984 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:41:40,984 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 542 states to 0 states and 0 transitions. [2024-10-13 17:41:40,984 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-13 17:41:40,984 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-13 17:41:40,984 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-13 17:41:40,984 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-13 17:41:40,984 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:40,984 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:40,984 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-13 17:41:40,985 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:40,985 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-13 17:41:40,985 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-13 17:41:40,985 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:41:40,985 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-13 17:41:40,991 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 13.10 05:41:40 BoogieIcfgContainer [2024-10-13 17:41:40,991 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-13 17:41:40,991 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-13 17:41:40,991 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-13 17:41:40,991 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-13 17:41:40,992 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:27" (3/4) ... [2024-10-13 17:41:40,993 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-13 17:41:40,994 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-13 17:41:40,994 INFO L158 Benchmark]: Toolchain (without parser) took 14047.64ms. Allocated memory was 180.4MB in the beginning and 375.4MB in the end (delta: 195.0MB). Free memory was 130.1MB in the beginning and 230.8MB in the end (delta: -100.6MB). Peak memory consumption was 97.3MB. Max. memory is 16.1GB. [2024-10-13 17:41:40,994 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 180.4MB. Free memory was 147.2MB in the beginning and 147.0MB in the end (delta: 167.8kB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:41:40,994 INFO L158 Benchmark]: CACSL2BoogieTranslator took 178.80ms. Allocated memory is still 180.4MB. Free memory was 129.4MB in the beginning and 118.3MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-13 17:41:40,995 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.84ms. Allocated memory is still 180.4MB. Free memory was 118.3MB in the beginning and 116.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:40,995 INFO L158 Benchmark]: Boogie Preprocessor took 27.50ms. Allocated memory is still 180.4MB. Free memory was 116.8MB in the beginning and 115.5MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:40,995 INFO L158 Benchmark]: RCFGBuilder took 186.25ms. Allocated memory is still 180.4MB. Free memory was 115.5MB in the beginning and 105.0MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-13 17:41:40,995 INFO L158 Benchmark]: BuchiAutomizer took 13621.23ms. Allocated memory was 180.4MB in the beginning and 375.4MB in the end (delta: 195.0MB). Free memory was 105.0MB in the beginning and 230.8MB in the end (delta: -125.8MB). Peak memory consumption was 72.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:40,995 INFO L158 Benchmark]: Witness Printer took 2.75ms. Allocated memory is still 375.4MB. Free memory is still 230.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:41:40,996 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.10ms. Allocated memory is still 180.4MB. Free memory was 147.2MB in the beginning and 147.0MB in the end (delta: 167.8kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 178.80ms. Allocated memory is still 180.4MB. Free memory was 129.4MB in the beginning and 118.3MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.84ms. Allocated memory is still 180.4MB. Free memory was 118.3MB in the beginning and 116.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 27.50ms. Allocated memory is still 180.4MB. Free memory was 116.8MB in the beginning and 115.5MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 186.25ms. Allocated memory is still 180.4MB. Free memory was 115.5MB in the beginning and 105.0MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 13621.23ms. Allocated memory was 180.4MB in the beginning and 375.4MB in the end (delta: 195.0MB). Free memory was 105.0MB in the beginning and 230.8MB in the end (delta: -125.8MB). Peak memory consumption was 72.1MB. Max. memory is 16.1GB. * Witness Printer took 2.75ms. Allocated memory is still 375.4MB. Free memory is still 230.8MB. 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 13.5s and 7 iterations. TraceHistogramMax:20. Analysis of lassos took 6.8s. Construction of modules took 0.6s. Büchi inclusion checks took 5.8s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 260 StatesRemovedByMinimization, 7 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 489 SdHoareTripleChecker+Valid, 0.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 441 mSDsluCounter, 478 SdHoareTripleChecker+Invalid, 0.7s 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: 19ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-13 17:41:41,017 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (40)] Ended with exit code 0 [2024-10-13 17:41:41,219 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-10-13 17:41:41,423 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:41,627 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-13 17:41:41,830 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE