./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 4a390ef5 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/Fibonacci02.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4a390ef-m [2024-10-25 00:35:21,622 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-25 00:35:21,688 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-25 00:35:21,696 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-25 00:35:21,697 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-25 00:35:21,727 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-25 00:35:21,727 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-25 00:35:21,728 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-25 00:35:21,728 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-25 00:35:21,729 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-25 00:35:21,730 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-25 00:35:21,730 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-25 00:35:21,731 INFO L153 SettingsManager]: * Use SBE=true [2024-10-25 00:35:21,732 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-25 00:35:21,735 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-25 00:35:21,735 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-25 00:35:21,735 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-25 00:35:21,736 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-25 00:35:21,736 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-25 00:35:21,736 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-25 00:35:21,736 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-25 00:35:21,737 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-25 00:35:21,737 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-25 00:35:21,737 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-25 00:35:21,737 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-25 00:35:21,738 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-25 00:35:21,738 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-25 00:35:21,738 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-25 00:35:21,739 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-25 00:35:21,739 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-25 00:35:21,739 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-25 00:35:21,739 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-25 00:35:21,740 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-25 00:35:21,740 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-25 00:35:21,740 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-25 00:35:21,740 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-25 00:35:21,741 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-25 00:35:21,742 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-25 00:35:21,742 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-25 00:35:21,742 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 -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2024-10-25 00:35:21,993 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-25 00:35:22,017 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-25 00:35:22,023 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-25 00:35:22,024 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-25 00:35:22,025 INFO L274 PluginConnector]: CDTParser initialized [2024-10-25 00:35:22,026 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-25 00:35:23,535 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-25 00:35:23,707 INFO L384 CDTParser]: Found 1 translation units. [2024-10-25 00:35:23,707 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-25 00:35:23,719 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f59ee2704/5bdc7cb51d4143679c1d9c58e82e55ec/FLAG81d69e181 [2024-10-25 00:35:23,736 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f59ee2704/5bdc7cb51d4143679c1d9c58e82e55ec [2024-10-25 00:35:23,739 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-25 00:35:23,741 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-25 00:35:23,745 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-25 00:35:23,745 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-25 00:35:23,750 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-25 00:35:23,751 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.10 12:35:23" (1/1) ... [2024-10-25 00:35:23,752 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2a01cff3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:23, skipping insertion in model container [2024-10-25 00:35:23,754 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.10 12:35:23" (1/1) ... [2024-10-25 00:35:23,774 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-25 00:35:23,959 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-25 00:35:23,974 INFO L200 MainTranslator]: Completed pre-run [2024-10-25 00:35:23,986 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-25 00:35:24,000 INFO L204 MainTranslator]: Completed translation [2024-10-25 00:35:24,000 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24 WrapperNode [2024-10-25 00:35:24,000 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-25 00:35:24,001 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-25 00:35:24,001 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-25 00:35:24,001 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-25 00:35:24,008 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,013 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,027 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-10-25 00:35:24,028 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-25 00:35:24,028 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-25 00:35:24,028 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-25 00:35:24,029 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-25 00:35:24,038 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,039 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,040 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,049 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-25 00:35:24,050 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,050 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,052 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,053 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,054 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,055 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,056 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-25 00:35:24,057 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-25 00:35:24,057 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-25 00:35:24,057 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-25 00:35:24,058 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (1/1) ... [2024-10-25 00:35:24,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:24,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:24,085 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-25 00:35:24,087 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-25 00:35:24,130 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-10-25 00:35:24,130 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-10-25 00:35:24,130 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-25 00:35:24,131 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-25 00:35:24,131 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-25 00:35:24,131 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-25 00:35:24,184 INFO L238 CfgBuilder]: Building ICFG [2024-10-25 00:35:24,186 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-25 00:35:24,277 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-25 00:35:24,278 INFO L287 CfgBuilder]: Performing block encoding [2024-10-25 00:35:24,291 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-25 00:35:24,291 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-25 00:35:24,292 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.10 12:35:24 BoogieIcfgContainer [2024-10-25 00:35:24,292 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-25 00:35:24,293 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-25 00:35:24,293 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-25 00:35:24,297 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-25 00:35:24,298 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-25 00:35:24,298 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 25.10 12:35:23" (1/3) ... [2024-10-25 00:35:24,299 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@374c4936 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 25.10 12:35:24, skipping insertion in model container [2024-10-25 00:35:24,299 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-25 00:35:24,299 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.10 12:35:24" (2/3) ... [2024-10-25 00:35:24,300 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@374c4936 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 25.10 12:35:24, skipping insertion in model container [2024-10-25 00:35:24,300 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-25 00:35:24,300 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.10 12:35:24" (3/3) ... [2024-10-25 00:35:24,301 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2024-10-25 00:35:24,357 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-25 00:35:24,357 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-25 00:35:24,357 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-25 00:35:24,358 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-25 00:35:24,358 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-25 00:35:24,358 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-25 00:35:24,359 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-25 00:35:24,359 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-25 00:35:24,364 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-25 00:35:24,385 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-25 00:35:24,386 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:24,386 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:24,392 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-25 00:35:24,393 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-25 00:35:24,393 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-25 00:35:24,394 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-25 00:35:24,395 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-25 00:35:24,396 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:24,396 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:24,397 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-25 00:35:24,397 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-25 00:35:24,405 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~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 8#L29true call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 14#$Ultimate##0true [2024-10-25 00:35:24,406 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-25 00:35:24,411 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:24,412 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-10-25 00:35:24,419 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:24,419 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1474827862] [2024-10-25 00:35:24,420 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:24,420 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:24,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:24,494 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:24,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:24,518 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:24,523 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:24,523 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-10-25 00:35:24,523 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:24,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [211366684] [2024-10-25 00:35:24,524 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:24,524 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:24,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:24,538 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:24,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:24,546 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:24,549 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:24,550 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-10-25 00:35:24,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:24,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [334727840] [2024-10-25 00:35:24,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:24,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:24,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:24,570 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:24,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:24,585 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:24,784 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:24,785 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:24,785 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:24,785 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:24,785 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-25 00:35:24,785 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:24,785 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:24,786 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:24,786 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-25 00:35:24,786 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:24,786 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:24,800 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:24,814 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:24,817 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:24,820 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:24,828 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:24,896 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:24,896 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-25 00:35:24,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:24,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:24,901 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-25 00:35:24,903 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-25 00:35:24,905 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:24,905 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:24,922 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:24,922 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-25 00:35:24,933 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-25 00:35:24,934 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:24,934 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:24,935 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-25 00:35:24,936 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-25 00:35:24,937 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:24,937 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:24,949 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:24,950 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-25 00:35:24,963 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:24,963 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:24,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:24,965 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-25 00:35:24,966 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-25 00:35:24,967 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:24,967 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:24,979 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:24,979 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-25 00:35:24,991 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-10-25 00:35:24,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:24,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:24,993 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-25 00:35:24,994 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-25 00:35:24,994 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:24,995 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:25,017 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-25 00:35:25,017 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,017 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:25,018 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-25 00:35:25,020 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-25 00:35:25,021 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-25 00:35:25,021 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:25,077 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-25 00:35:25,082 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-25 00:35:25,082 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:25,083 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:25,083 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:25,083 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:25,083 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-25 00:35:25,083 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,083 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:25,083 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:25,083 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-25 00:35:25,083 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:25,083 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:25,085 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:25,089 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:25,094 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:25,099 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:25,109 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:25,164 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:25,168 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-25 00:35:25,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,170 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:25,172 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-25 00:35:25,174 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-25 00:35:25,177 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-25 00:35:25,187 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:25,187 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:25,188 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:25,188 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:25,188 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:25,190 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:25,190 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:25,192 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:25,208 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-25 00:35:25,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,209 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:25,210 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-25 00:35:25,213 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-25 00:35:25,214 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-25 00:35:25,228 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:25,229 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:25,229 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:25,229 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:25,229 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:25,230 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:25,230 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:25,232 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:25,246 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-10-25 00:35:25,247 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,247 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:25,248 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-25 00:35:25,249 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-25 00:35:25,249 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-25 00:35:25,259 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:25,259 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:25,259 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:25,259 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:25,259 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:25,260 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:25,260 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:25,263 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:25,274 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-25 00:35:25,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:25,275 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-25 00:35:25,277 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-25 00:35:25,277 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-25 00:35:25,287 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:25,287 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:25,287 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:25,287 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:25,287 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:25,288 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:25,289 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:25,292 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-25 00:35:25,295 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-25 00:35:25,296 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-25 00:35:25,297 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:25,297 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:25,317 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-25 00:35:25,319 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-25 00:35:25,320 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-25 00:35:25,320 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-25 00:35:25,320 INFO L474 LassoAnalysis]: Proved termination. [2024-10-25 00:35:25,320 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-25 00:35:25,331 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-10-25 00:35:25,334 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-25 00:35:25,358 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:25,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:25,393 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-25 00:35:25,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:25,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:25,418 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-25 00:35:25,419 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:25,475 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-25 00:35:25,507 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-25 00:35:25,509 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-25 00:35:25,604 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-25 00:35:25,609 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-25 00:35:25,615 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-25 00:35:25,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-25 00:35:25,617 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-25 00:35:25,618 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:25,618 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-25 00:35:25,619 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:25,619 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-25 00:35:25,619 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:25,620 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-10-25 00:35:25,625 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-25 00:35:25,631 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-10-25 00:35:25,632 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-25 00:35:25,633 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-25 00:35:25,633 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-25 00:35:25,634 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:25,634 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-25 00:35:25,649 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-25 00:35:25,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-25 00:35:25,658 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-25 00:35:25,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-25 00:35:25,660 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-25 00:35:25,660 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-25 00:35:25,661 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-25 00:35:25,661 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-25 00:35:25,662 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-25 00:35:25,662 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:25,662 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:25,663 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:25,663 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:25,663 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~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 120#L29 call main_#t~ret6#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-25 00:35:25,663 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-25 00:35:25,664 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:25,664 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-10-25 00:35:25,664 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:25,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1534742430] [2024-10-25 00:35:25,664 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:25,665 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:25,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:25,783 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-25 00:35:25,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:25,832 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-25 00:35:25,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-25 00:35:25,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1534742430] [2024-10-25 00:35:25,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1534742430] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-25 00:35:25,833 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-25 00:35:25,835 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-25 00:35:25,835 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539100055] [2024-10-25 00:35:25,836 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-25 00:35:25,838 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-25 00:35:25,838 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:25,838 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-10-25 00:35:25,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:25,839 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1206088900] [2024-10-25 00:35:25,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:25,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:25,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:25,876 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-25 00:35:25,880 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:25,925 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-25 00:35:25,925 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-25 00:35:25,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1206088900] [2024-10-25 00:35:25,926 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1206088900] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-25 00:35:25,926 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-25 00:35:25,927 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-25 00:35:25,927 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [463558590] [2024-10-25 00:35:25,927 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-25 00:35:25,927 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-25 00:35:25,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-25 00:35:25,929 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-25 00:35:25,930 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-25 00:35:25,931 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-25 00:35:25,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-25 00:35:25,996 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-25 00:35:25,996 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-25 00:35:25,998 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-25 00:35:25,999 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-25 00:35:25,999 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-25 00:35:26,002 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-25 00:35:26,002 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-25 00:35:26,002 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:26,003 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-25 00:35:26,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-25 00:35:26,005 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-25 00:35:26,006 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-25 00:35:26,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-25 00:35:26,007 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-25 00:35:26,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-25 00:35:26,009 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-25 00:35:26,009 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-25 00:35:26,009 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-25 00:35:26,010 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-25 00:35:26,011 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:26,012 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:26,012 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:26,013 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-25 00:35:26,013 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~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 191#L29 call main_#t~ret6#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-25 00:35:26,014 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-25 00:35:26,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:26,014 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-10-25 00:35:26,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:26,015 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1857048313] [2024-10-25 00:35:26,015 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:26,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:26,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:26,090 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-25 00:35:26,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:26,125 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-25 00:35:26,125 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-25 00:35:26,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1857048313] [2024-10-25 00:35:26,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1857048313] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-25 00:35:26,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1611914524] [2024-10-25 00:35:26,126 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:26,127 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-25 00:35:26,127 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:26,129 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-25 00:35:26,130 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-25 00:35:26,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:26,163 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-25 00:35:26,164 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:26,193 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-25 00:35:26,193 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-25 00:35:26,299 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-25 00:35:26,300 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1611914524] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-25 00:35:26,300 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-25 00:35:26,300 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-10-25 00:35:26,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981620353] [2024-10-25 00:35:26,300 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-25 00:35:26,301 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-25 00:35:26,301 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:26,301 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-10-25 00:35:26,301 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:26,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1699552730] [2024-10-25 00:35:26,302 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:26,302 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:26,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:26,313 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:26,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:26,322 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:26,551 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-25 00:35:26,616 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:26,617 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:26,617 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:26,617 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:26,617 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-25 00:35:26,617 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,617 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:26,617 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:26,617 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-25 00:35:26,617 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:26,617 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:26,618 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,621 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,629 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,631 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,635 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,680 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:26,681 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-25 00:35:26,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:26,683 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-25 00:35:26,684 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-25 00:35:26,685 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:26,685 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:26,699 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:26,699 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-25 00:35:26,709 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-10-25 00:35:26,710 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:26,711 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-25 00:35:26,711 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-25 00:35:26,712 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:26,712 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:26,734 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-10-25 00:35:26,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:26,736 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-25 00:35:26,737 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-25 00:35:26,738 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-25 00:35:26,738 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:26,750 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-25 00:35:26,761 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-25 00:35:26,761 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:26,761 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:26,761 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:26,761 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:26,761 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-25 00:35:26,761 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,761 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:26,762 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:26,762 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-25 00:35:26,762 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:26,762 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:26,763 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,772 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,775 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,778 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,780 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:26,817 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:26,817 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-25 00:35:26,818 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:26,819 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-25 00:35:26,820 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-25 00:35:26,821 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-25 00:35:26,834 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:26,834 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:26,835 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:26,835 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:26,835 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:26,836 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:26,836 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:26,840 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-25 00:35:26,843 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-25 00:35:26,843 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-25 00:35:26,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:26,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:26,845 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-25 00:35:26,847 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-25 00:35:26,848 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-25 00:35:26,849 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-25 00:35:26,849 INFO L474 LassoAnalysis]: Proved termination. [2024-10-25 00:35:26,849 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-25 00:35:26,863 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-10-25 00:35:26,864 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-25 00:35:26,882 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:26,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:26,909 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-25 00:35:26,910 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:27,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:27,034 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-25 00:35:27,036 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:27,180 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-25 00:35:27,181 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-25 00:35:27,181 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-25 00:35:27,405 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-25 00:35:27,405 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-25 00:35:27,406 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-25 00:35:27,407 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-10-25 00:35:27,407 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-10-25 00:35:27,407 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:27,407 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-10-25 00:35:27,408 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:27,408 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-10-25 00:35:27,409 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:27,409 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-10-25 00:35:27,415 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-25 00:35:27,420 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-10-25 00:35:27,420 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-10-25 00:35:27,421 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-25 00:35:27,421 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-10-25 00:35:27,421 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:27,421 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-10-25 00:35:27,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-10-25 00:35:27,432 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-10-25 00:35:27,433 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-25 00:35:27,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-10-25 00:35:27,435 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-10-25 00:35:27,435 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-25 00:35:27,435 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-25 00:35:27,435 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-10-25 00:35:27,436 INFO L87 Difference]: Start difference. First operand 106 states and 142 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-25 00:35:27,569 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-25 00:35:27,569 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-10-25 00:35:27,569 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-10-25 00:35:27,576 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-25 00:35:27,579 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-10-25 00:35:27,582 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-10-25 00:35:27,583 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-10-25 00:35:27,583 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-10-25 00:35:27,583 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:27,583 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-10-25 00:35:27,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-10-25 00:35:27,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-10-25 00:35:27,598 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 74 states have (on average 1.2027027027027026) internal successors, (89), 78 states have internal predecessors, (89), 28 states have call successors, (29), 15 states have call predecessors, (29), 16 states have return successors, (39), 24 states have call predecessors, (39), 26 states have call successors, (39) [2024-10-25 00:35:27,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-10-25 00:35:27,603 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-25 00:35:27,604 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-25 00:35:27,604 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-25 00:35:27,604 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-25 00:35:27,605 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-10-25 00:35:27,607 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-25 00:35:27,607 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:27,608 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:27,608 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:27,609 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:27,609 INFO L745 eck$LassoCheckResult]: Stem: 905#$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); 906#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 880#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 907#$Ultimate##0 ~n := #in~n; 887#L17 assume !(~n < 1); 888#L19 assume !(1 == ~n); 891#L22 call #t~ret4 := fibonacci(~n - 1);< 892#$Ultimate##0 ~n := #in~n; 949#L17 assume !(~n < 1); 948#L19 assume !(1 == ~n); 937#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 947#L17 assume !(~n < 1); 945#L19 assume 1 == ~n;#res := 1; 943#fibonacciFINAL assume true; 941#fibonacciEXIT >#31#return; 883#L22-1 call #t~ret5 := fibonacci(~n - 2);< 940#$Ultimate##0 ~n := #in~n; 885#L17 assume ~n < 1;#res := 0; 886#fibonacciFINAL assume true; 992#fibonacciEXIT >#33#return; 990#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 987#fibonacciFINAL assume true; 980#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-25 00:35:27,609 INFO L747 eck$LassoCheckResult]: Loop: 913#L22-1 call #t~ret5 := fibonacci(~n - 2);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume !(1 == ~n); 914#L22 call #t~ret4 := fibonacci(~n - 1);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume 1 == ~n;#res := 1; 915#fibonacciFINAL assume true; 916#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-25 00:35:27,609 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:27,610 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2024-10-25 00:35:27,610 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:27,610 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1514203365] [2024-10-25 00:35:27,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:27,610 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:27,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:27,785 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-25 00:35:27,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:27,848 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-25 00:35:27,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:27,871 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-25 00:35:27,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:27,902 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-25 00:35:27,902 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-25 00:35:27,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1514203365] [2024-10-25 00:35:27,903 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1514203365] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-25 00:35:27,903 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [91933717] [2024-10-25 00:35:27,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:27,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-25 00:35:27,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:27,905 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-25 00:35:27,906 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-25 00:35:27,920 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-25 00:35:27,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:27,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-25 00:35:27,953 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:28,004 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-25 00:35:28,004 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-25 00:35:28,271 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-25 00:35:28,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [91933717] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-25 00:35:28,271 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-25 00:35:28,271 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-10-25 00:35:28,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1129017522] [2024-10-25 00:35:28,271 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-25 00:35:28,272 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-25 00:35:28,272 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:28,272 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2024-10-25 00:35:28,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:28,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1382344198] [2024-10-25 00:35:28,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:28,273 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:28,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:28,276 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:28,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:28,279 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:28,381 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:28,382 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:28,382 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:28,382 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:28,382 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-25 00:35:28,382 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,382 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:28,382 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:28,382 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-25 00:35:28,382 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:28,382 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:28,383 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,386 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,392 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,394 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,396 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,432 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:28,432 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-25 00:35:28,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:28,434 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-25 00:35:28,435 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-25 00:35:28,439 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:28,440 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:28,456 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:28,457 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=2} Honda state: {fibonacci_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-25 00:35:28,471 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-10-25 00:35:28,472 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:28,474 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-25 00:35:28,478 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-25 00:35:28,479 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:28,479 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:28,508 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-25 00:35:28,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:28,511 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-25 00:35:28,513 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-10-25 00:35:28,514 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-25 00:35:28,514 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:28,531 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-25 00:35:28,546 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-10-25 00:35:28,547 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:28,547 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:28,547 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:28,547 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:28,547 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-25 00:35:28,547 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,547 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:28,547 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:28,547 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-25 00:35:28,547 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:28,547 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:28,548 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,553 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,558 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,561 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,563 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:28,598 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:28,598 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-25 00:35:28,598 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:28,601 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-25 00:35:28,603 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-25 00:35:28,604 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-25 00:35:28,616 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:28,616 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:28,617 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:28,617 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:28,617 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:28,617 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:28,617 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:28,619 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:28,634 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-25 00:35:28,634 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:28,636 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-25 00:35:28,637 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-25 00:35:28,638 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-25 00:35:28,650 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:28,651 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:28,651 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:28,651 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:28,651 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:28,652 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:28,652 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:28,654 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-25 00:35:28,658 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-25 00:35:28,658 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-25 00:35:28,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:28,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:28,660 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-25 00:35:28,662 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-25 00:35:28,663 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-25 00:35:28,663 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-25 00:35:28,663 INFO L474 LassoAnalysis]: Proved termination. [2024-10-25 00:35:28,663 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-25 00:35:28,677 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:28,679 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-25 00:35:28,691 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:28,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:28,735 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-25 00:35:28,737 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:28,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:28,931 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-25 00:35:28,932 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:29,008 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-25 00:35:29,009 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-25 00:35:29,009 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-25 00:35:29,164 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:29,237 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 230 states and 321 transitions. Complement of second has 37 states. [2024-10-25 00:35:29,240 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-10-25 00:35:29,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-25 00:35:29,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-10-25 00:35:29,241 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-25 00:35:29,242 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:29,242 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-25 00:35:29,254 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:29,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:29,297 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-25 00:35:29,299 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:29,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:29,490 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-25 00:35:29,491 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:29,568 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-25 00:35:29,569 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-25 00:35:29,569 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-25 00:35:29,755 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 300 states and 408 transitions. Complement of second has 29 states. [2024-10-25 00:35:29,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-10-25 00:35:29,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-25 00:35:29,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-10-25 00:35:29,759 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-25 00:35:29,760 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:29,760 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-25 00:35:29,771 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:29,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:29,816 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-25 00:35:29,818 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:30,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:30,003 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-25 00:35:30,006 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:30,088 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-25 00:35:30,089 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-25 00:35:30,089 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-25 00:35:30,304 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 808 states and 1112 transitions. Complement of second has 135 states. [2024-10-25 00:35:30,307 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-10-25 00:35:30,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-25 00:35:30,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-10-25 00:35:30,308 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-25 00:35:30,309 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:30,309 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-10-25 00:35:30,309 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:30,309 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-10-25 00:35:30,310 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:30,310 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 808 states and 1112 transitions. [2024-10-25 00:35:30,323 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-10-25 00:35:30,337 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 808 states to 427 states and 634 transitions. [2024-10-25 00:35:30,340 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 166 [2024-10-25 00:35:30,341 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-10-25 00:35:30,341 INFO L73 IsDeterministic]: Start isDeterministic. Operand 427 states and 634 transitions. [2024-10-25 00:35:30,341 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:30,341 INFO L218 hiAutomatonCegarLoop]: Abstraction has 427 states and 634 transitions. [2024-10-25 00:35:30,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states and 634 transitions. [2024-10-25 00:35:30,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 352. [2024-10-25 00:35:30,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 352 states, 221 states have (on average 1.1990950226244343) internal successors, (265), 235 states have internal predecessors, (265), 75 states have call successors, (84), 46 states have call predecessors, (84), 56 states have return successors, (130), 70 states have call predecessors, (130), 71 states have call successors, (130) [2024-10-25 00:35:30,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 479 transitions. [2024-10-25 00:35:30,375 INFO L240 hiAutomatonCegarLoop]: Abstraction has 352 states and 479 transitions. [2024-10-25 00:35:30,375 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-25 00:35:30,376 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-25 00:35:30,376 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-10-25 00:35:30,376 INFO L87 Difference]: Start difference. First operand 352 states and 479 transitions. Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-25 00:35:30,733 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-25 00:35:30,734 INFO L93 Difference]: Finished difference Result 707 states and 1054 transitions. [2024-10-25 00:35:30,734 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 707 states and 1054 transitions. [2024-10-25 00:35:30,746 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-25 00:35:30,760 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 707 states to 676 states and 1009 transitions. [2024-10-25 00:35:30,760 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 296 [2024-10-25 00:35:30,762 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 299 [2024-10-25 00:35:30,762 INFO L73 IsDeterministic]: Start isDeterministic. Operand 676 states and 1009 transitions. [2024-10-25 00:35:30,762 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:30,762 INFO L218 hiAutomatonCegarLoop]: Abstraction has 676 states and 1009 transitions. [2024-10-25 00:35:30,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 676 states and 1009 transitions. [2024-10-25 00:35:30,804 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 676 to 628. [2024-10-25 00:35:30,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 628 states, 383 states have (on average 1.1618798955613576) internal successors, (445), 406 states have internal predecessors, (445), 151 states have call successors, (165), 76 states have call predecessors, (165), 94 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-25 00:35:30,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 936 transitions. [2024-10-25 00:35:30,815 INFO L240 hiAutomatonCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-25 00:35:30,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-25 00:35:30,816 INFO L425 stractBuchiCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-25 00:35:30,817 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-25 00:35:30,817 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 628 states and 936 transitions. [2024-10-25 00:35:30,821 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-25 00:35:30,822 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:30,822 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:30,823 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:30,824 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-25 00:35:30,824 INFO L745 eck$LassoCheckResult]: Stem: 4310#$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); 4311#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 4312#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 4313#$Ultimate##0 ~n := #in~n; 4329#L17 assume !(~n < 1); 4398#L19 assume !(1 == ~n); 4394#L22 call #t~ret4 := fibonacci(~n - 1);< 4395#$Ultimate##0 ~n := #in~n; 4427#L17 assume !(~n < 1); 4414#L19 assume !(1 == ~n); 4407#L22 call #t~ret4 := fibonacci(~n - 1);< 4410#$Ultimate##0 ~n := #in~n; 4421#L17 assume !(~n < 1); 4412#L19 assume !(1 == ~n); 4402#L22 call #t~ret4 := fibonacci(~n - 1);< 4408#$Ultimate##0 ~n := #in~n; 4431#L17 assume !(~n < 1); 4430#L19 assume !(1 == ~n); 4424#L22 call #t~ret4 := fibonacci(~n - 1);< 4429#$Ultimate##0 ~n := #in~n; 4448#L17 assume !(~n < 1); 4447#L19 assume !(1 == ~n); 4416#L22 call #t~ret4 := fibonacci(~n - 1);< 4446#$Ultimate##0 ~n := #in~n; 4461#L17 assume !(~n < 1); 4460#L19 assume !(1 == ~n); 4344#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4345#L17 assume !(~n < 1); 4464#L19 assume !(1 == ~n); 4343#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4346#L17 assume !(~n < 1); 4536#L19 assume 1 == ~n;#res := 1; 4535#fibonacciFINAL assume true; 4530#fibonacciEXIT >#31#return; 4514#L22-1 call #t~ret5 := fibonacci(~n - 2);< 4528#$Ultimate##0 ~n := #in~n; 4777#L17 assume !(~n < 1); 4655#L19 assume !(1 == ~n); 4656#L22 call #t~ret4 := fibonacci(~n - 1);< 4707#$Ultimate##0 ~n := #in~n; 4821#L17 assume !(~n < 1); 4818#L19 assume !(1 == ~n); 4819#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-25 00:35:30,824 INFO L747 eck$LassoCheckResult]: Loop: 4828#$Ultimate##0 ~n := #in~n; 4850#L17 assume !(~n < 1); 4847#L19 assume !(1 == ~n); 4827#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-25 00:35:30,825 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:30,825 INFO L85 PathProgramCache]: Analyzing trace with hash 1729544275, now seen corresponding path program 1 times [2024-10-25 00:35:30,825 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:30,825 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1689592790] [2024-10-25 00:35:30,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:30,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:30,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:31,074 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-25 00:35:31,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:31,109 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-25 00:35:31,110 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-25 00:35:31,110 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1689592790] [2024-10-25 00:35:31,110 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1689592790] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-25 00:35:31,110 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1326603211] [2024-10-25 00:35:31,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:31,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-25 00:35:31,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,116 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-25 00:35:31,117 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-10-25 00:35:31,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:31,164 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-10-25 00:35:31,166 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:31,244 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-25 00:35:31,245 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-25 00:35:31,459 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-25 00:35:31,460 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1326603211] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-25 00:35:31,460 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-25 00:35:31,460 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2024-10-25 00:35:31,460 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [106498269] [2024-10-25 00:35:31,460 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-25 00:35:31,461 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-25 00:35:31,461 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:31,461 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-10-25 00:35:31,461 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:31,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2084346576] [2024-10-25 00:35:31,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:31,462 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:31,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:31,464 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:31,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:31,466 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:31,499 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:31,500 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:31,500 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:31,500 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:31,500 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-25 00:35:31,500 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,500 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:31,500 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:31,500 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-25 00:35:31,500 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:31,500 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:31,501 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,504 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,506 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,512 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,514 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,543 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:31,543 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-25 00:35:31,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,545 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-25 00:35:31,546 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-25 00:35:31,546 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:31,546 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:31,558 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:31,558 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-25 00:35:31,568 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:31,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,570 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-25 00:35:31,571 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-25 00:35:31,571 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:31,571 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:31,583 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:31,583 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-25 00:35:31,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-10-25 00:35:31,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,594 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-25 00:35:31,595 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-25 00:35:31,596 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:31,596 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:31,617 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-25 00:35:31,617 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,617 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,618 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-25 00:35:31,619 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-10-25 00:35:31,620 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-25 00:35:31,620 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:31,647 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-25 00:35:31,651 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:31,651 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:31,651 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:31,651 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:31,651 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:31,651 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-25 00:35:31,651 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,651 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:31,651 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:31,651 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-25 00:35:31,651 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:31,651 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:31,652 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,654 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,656 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,661 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,662 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:31,690 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:31,690 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-25 00:35:31,691 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,692 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-25 00:35:31,693 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-25 00:35:31,693 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-25 00:35:31,703 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:31,703 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:31,703 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:31,703 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:31,704 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:31,704 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:31,704 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:31,706 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:31,716 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-25 00:35:31,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,717 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-25 00:35:31,718 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-25 00:35:31,719 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-25 00:35:31,729 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:31,729 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:31,729 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:31,729 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:31,729 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:31,729 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:31,729 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:31,730 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:31,741 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-10-25 00:35:31,741 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,741 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,743 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-25 00:35:31,744 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-25 00:35:31,744 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-25 00:35:31,754 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:31,754 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:31,754 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:31,755 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:31,755 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:31,755 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:31,755 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:31,757 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-25 00:35:31,759 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-25 00:35:31,759 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-25 00:35:31,760 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:31,760 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:31,761 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-25 00:35:31,762 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-25 00:35:31,762 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-25 00:35:31,762 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-25 00:35:31,762 INFO L474 LassoAnalysis]: Proved termination. [2024-10-25 00:35:31,762 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-25 00:35:31,772 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-10-25 00:35:31,773 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-25 00:35:31,781 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:31,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:31,856 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-25 00:35:31,858 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:31,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:31,953 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-25 00:35:31,953 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:31,980 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-25 00:35:31,981 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-25 00:35:31,981 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,045 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-25 00:35:32,046 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-25 00:35:32,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-25 00:35:32,047 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-25 00:35:32,047 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:32,047 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-25 00:35:32,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:32,120 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2024-10-25 00:35:32,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:32,146 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-25 00:35:32,148 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:32,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:32,244 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-25 00:35:32,244 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:32,268 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-25 00:35:32,268 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-25 00:35:32,269 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,330 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-25 00:35:32,331 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-25 00:35:32,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-25 00:35:32,332 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-25 00:35:32,332 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:32,332 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-25 00:35:32,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:32,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:32,401 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-25 00:35:32,403 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:32,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:32,517 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-25 00:35:32,518 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:32,543 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-25 00:35:32,544 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-25 00:35:32,545 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,623 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 839 states and 1163 transitions. Complement of second has 19 states. [2024-10-25 00:35:32,623 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-25 00:35:32,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-10-25 00:35:32,624 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-25 00:35:32,626 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:32,626 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-10-25 00:35:32,627 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:32,627 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-10-25 00:35:32,627 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:32,627 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1163 transitions. [2024-10-25 00:35:32,637 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-25 00:35:32,646 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 996 transitions. [2024-10-25 00:35:32,646 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2024-10-25 00:35:32,647 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2024-10-25 00:35:32,647 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 996 transitions. [2024-10-25 00:35:32,648 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:32,648 INFO L218 hiAutomatonCegarLoop]: Abstraction has 684 states and 996 transitions. [2024-10-25 00:35:32,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 996 transitions. [2024-10-25 00:35:32,662 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2024-10-25 00:35:32,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 654 states, 407 states have (on average 1.1523341523341524) internal successors, (469), 432 states have internal predecessors, (469), 151 states have call successors, (165), 76 states have call predecessors, (165), 96 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-25 00:35:32,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 960 transitions. [2024-10-25 00:35:32,668 INFO L240 hiAutomatonCegarLoop]: Abstraction has 654 states and 960 transitions. [2024-10-25 00:35:32,668 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-25 00:35:32,669 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-25 00:35:32,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-10-25 00:35:32,669 INFO L87 Difference]: Start difference. First operand 654 states and 960 transitions. Second operand has 21 states, 20 states have (on average 1.8) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (10), 9 states have call predecessors, (10), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:32,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-25 00:35:32,966 INFO L93 Difference]: Finished difference Result 781 states and 1180 transitions. [2024-10-25 00:35:32,966 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 781 states and 1180 transitions. [2024-10-25 00:35:32,975 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-25 00:35:32,984 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 781 states to 760 states and 1148 transitions. [2024-10-25 00:35:32,985 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 279 [2024-10-25 00:35:32,985 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 282 [2024-10-25 00:35:32,985 INFO L73 IsDeterministic]: Start isDeterministic. Operand 760 states and 1148 transitions. [2024-10-25 00:35:32,985 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:32,986 INFO L218 hiAutomatonCegarLoop]: Abstraction has 760 states and 1148 transitions. [2024-10-25 00:35:32,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states and 1148 transitions. [2024-10-25 00:35:33,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 702. [2024-10-25 00:35:33,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 702 states, 437 states have (on average 1.1464530892448512) internal successors, (501), 462 states have internal predecessors, (501), 169 states have call successors, (185), 86 states have call predecessors, (185), 96 states have return successors, (336), 153 states have call predecessors, (336), 159 states have call successors, (336) [2024-10-25 00:35:33,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 702 states to 702 states and 1022 transitions. [2024-10-25 00:35:33,010 INFO L240 hiAutomatonCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-25 00:35:33,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-25 00:35:33,012 INFO L425 stractBuchiCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-25 00:35:33,012 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-25 00:35:33,012 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 702 states and 1022 transitions. [2024-10-25 00:35:33,016 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-25 00:35:33,016 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-25 00:35:33,016 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-25 00:35:33,018 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2024-10-25 00:35:33,018 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-25 00:35:33,019 INFO L745 eck$LassoCheckResult]: Stem: 9342#$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); 9343#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 9344#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 9345#$Ultimate##0 ~n := #in~n; 9513#L17 assume !(~n < 1); 9512#L19 assume !(1 == ~n); 9490#L22 call #t~ret4 := fibonacci(~n - 1);< 9491#$Ultimate##0 ~n := #in~n; 9555#L17 assume !(~n < 1); 9553#L19 assume !(1 == ~n); 9545#L22 call #t~ret4 := fibonacci(~n - 1);< 9551#$Ultimate##0 ~n := #in~n; 9550#L17 assume !(~n < 1); 9547#L19 assume !(1 == ~n); 9509#L22 call #t~ret4 := fibonacci(~n - 1);< 9546#$Ultimate##0 ~n := #in~n; 9661#L17 assume !(~n < 1); 9657#L19 assume !(1 == ~n); 9653#L22 call #t~ret4 := fibonacci(~n - 1);< 9655#$Ultimate##0 ~n := #in~n; 9680#L17 assume !(~n < 1); 9679#L19 assume !(1 == ~n); 9319#L22 call #t~ret4 := fibonacci(~n - 1);< 9678#$Ultimate##0 ~n := #in~n; 9723#L17 assume !(~n < 1); 9721#L19 assume !(1 == ~n); 9674#L22 call #t~ret4 := fibonacci(~n - 1);< 9698#$Ultimate##0 ~n := #in~n; 9792#L17 assume !(~n < 1); 9777#L19 assume !(1 == ~n); 9694#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9819#L17 assume !(~n < 1); 9815#L19 assume !(1 == ~n); 9693#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9822#L17 assume !(~n < 1); 9820#L19 assume 1 == ~n;#res := 1; 9816#fibonacciFINAL assume true; 9808#fibonacciEXIT >#31#return; 9715#L22-1 call #t~ret5 := fibonacci(~n - 2);< 9726#$Ultimate##0 ~n := #in~n; 9846#L17 assume !(~n < 1); 9909#L19 assume !(1 == ~n); 9368#L22 call #t~ret4 := fibonacci(~n - 1);< 9374#$Ultimate##0 ~n := #in~n; 9375#L17 assume !(~n < 1); 9973#L19 assume !(1 == ~n); 9354#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-25 00:35:33,019 INFO L747 eck$LassoCheckResult]: Loop: 9355#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-25 00:35:33,020 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:33,020 INFO L85 PathProgramCache]: Analyzing trace with hash 1537328375, now seen corresponding path program 2 times [2024-10-25 00:35:33,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:33,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [809638494] [2024-10-25 00:35:33,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:33,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:33,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:33,329 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-25 00:35:33,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:33,333 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-25 00:35:33,334 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-25 00:35:33,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [809638494] [2024-10-25 00:35:33,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [809638494] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-25 00:35:33,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [543480010] [2024-10-25 00:35:33,334 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-25 00:35:33,335 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-25 00:35:33,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:33,336 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-25 00:35:33,338 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2024-10-25 00:35:33,382 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-25 00:35:33,382 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-25 00:35:33,383 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-10-25 00:35:33,384 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:33,441 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-25 00:35:33,441 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-25 00:35:33,645 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-25 00:35:33,645 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [543480010] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-25 00:35:33,645 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-25 00:35:33,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2024-10-25 00:35:33,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [433887692] [2024-10-25 00:35:33,646 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-25 00:35:33,646 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-25 00:35:33,647 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:33,647 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-10-25 00:35:33,647 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-25 00:35:33,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1730763936] [2024-10-25 00:35:33,647 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-25 00:35:33,647 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-25 00:35:33,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:33,650 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-25 00:35:33,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-25 00:35:33,651 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-25 00:35:33,697 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:33,698 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:33,698 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:33,698 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:33,698 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-25 00:35:33,698 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:33,698 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:33,698 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:33,698 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-25 00:35:33,698 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:33,698 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:33,698 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:33,704 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:33,706 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:33,713 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:33,755 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:33,755 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-25 00:35:33,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:33,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:33,757 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-25 00:35:33,759 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-25 00:35:33,759 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:33,759 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:33,771 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:33,771 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-25 00:35:33,781 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:33,782 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:33,782 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:33,783 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-25 00:35:33,784 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-25 00:35:33,784 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:33,784 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:33,795 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-25 00:35:33,795 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-25 00:35:33,805 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2024-10-25 00:35:33,805 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:33,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:33,807 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-25 00:35:33,807 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-25 00:35:33,808 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-25 00:35:33,808 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:33,836 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-25 00:35:33,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:33,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:33,838 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-25 00:35:33,839 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-25 00:35:33,839 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-25 00:35:33,840 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-25 00:35:35,015 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-25 00:35:35,020 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:35,021 INFO L204 LassoAnalysis]: Preferences: [2024-10-25 00:35:35,021 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-25 00:35:35,021 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-25 00:35:35,021 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-25 00:35:35,021 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-25 00:35:35,021 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:35,021 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-25 00:35:35,021 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-25 00:35:35,021 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-25 00:35:35,021 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-25 00:35:35,021 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-25 00:35:35,022 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:35,023 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:35,025 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:35,031 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-25 00:35:35,063 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-25 00:35:35,063 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-25 00:35:35,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:35,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:35,064 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-25 00:35:35,066 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-25 00:35:35,067 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-25 00:35:35,079 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:35,079 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:35,079 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:35,079 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:35,079 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:35,080 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:35,080 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:35,083 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:35,095 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-25 00:35:35,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:35,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:35,096 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-25 00:35:35,097 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-10-25 00:35:35,098 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-25 00:35:35,108 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:35,108 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:35,108 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:35,108 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:35,108 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:35,109 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:35,109 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:35,110 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-25 00:35:35,125 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:35,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:35,126 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:35,128 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-25 00:35:35,129 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-25 00:35:35,130 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-25 00:35:35,141 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-25 00:35:35,141 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-25 00:35:35,141 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-25 00:35:35,141 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-25 00:35:35,141 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-25 00:35:35,142 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-25 00:35:35,142 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-25 00:35:35,146 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-25 00:35:35,150 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-25 00:35:35,150 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-25 00:35:35,150 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-25 00:35:35,150 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-25 00:35:35,151 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-25 00:35:35,152 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-25 00:35:35,152 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-25 00:35:35,153 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-25 00:35:35,153 INFO L474 LassoAnalysis]: Proved termination. [2024-10-25 00:35:35,153 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-25 00:35:35,167 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-10-25 00:35:35,168 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-25 00:35:35,184 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:35,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:35,253 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-25 00:35:35,255 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:35,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:35,369 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-25 00:35:35,369 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:35,400 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-25 00:35:35,401 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-25 00:35:35,401 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:35,446 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 724 states and 1045 transitions. Complement of second has 18 states. [2024-10-25 00:35:35,447 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-25 00:35:35,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:35,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-25 00:35:35,448 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-25 00:35:35,448 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:35,448 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-25 00:35:35,459 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-25 00:35:35,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:35,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-25 00:35:35,528 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:35,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-25 00:35:35,628 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-25 00:35:35,628 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-25 00:35:35,659 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-25 00:35:35,660 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-25 00:35:35,660 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:35,742 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 944 states and 1356 transitions. Complement of second has 22 states. [2024-10-25 00:35:35,742 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-25 00:35:35,743 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:35,743 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-10-25 00:35:35,743 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-25 00:35:35,743 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:35,744 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-10-25 00:35:35,744 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:35,744 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2024-10-25 00:35:35,744 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-25 00:35:35,744 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 944 states and 1356 transitions. [2024-10-25 00:35:35,755 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-25 00:35:35,803 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 944 states to 874 states and 1278 transitions. [2024-10-25 00:35:35,803 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2024-10-25 00:35:35,804 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 310 [2024-10-25 00:35:35,807 INFO L73 IsDeterministic]: Start isDeterministic. Operand 874 states and 1278 transitions. [2024-10-25 00:35:35,807 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-25 00:35:35,807 INFO L218 hiAutomatonCegarLoop]: Abstraction has 874 states and 1278 transitions. [2024-10-25 00:35:35,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 874 states and 1278 transitions. [2024-10-25 00:35:35,821 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-25 00:35:35,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 874 to 854. [2024-10-25 00:35:35,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 854 states, 537 states have (on average 1.1340782122905029) internal successors, (609), 569 states have internal predecessors, (609), 202 states have call successors, (236), 111 states have call predecessors, (236), 115 states have return successors, (409), 173 states have call predecessors, (409), 192 states have call successors, (409) [2024-10-25 00:35:35,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1254 transitions. [2024-10-25 00:35:35,841 INFO L240 hiAutomatonCegarLoop]: Abstraction has 854 states and 1254 transitions. [2024-10-25 00:35:35,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-25 00:35:35,841 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-25 00:35:35,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2024-10-25 00:35:35,842 INFO L87 Difference]: Start difference. First operand 854 states and 1254 transitions. Second operand has 21 states, 20 states have (on average 1.75) internal successors, (35), 12 states have internal predecessors, (35), 10 states have call successors, (11), 11 states have call predecessors, (11), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-25 00:35:36,107 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-25 00:35:36,107 INFO L93 Difference]: Finished difference Result 471 states and 558 transitions. [2024-10-25 00:35:36,107 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 471 states and 558 transitions. [2024-10-25 00:35:36,111 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-25 00:35:36,111 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 471 states to 0 states and 0 transitions. [2024-10-25 00:35:36,111 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-25 00:35:36,111 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-25 00:35:36,111 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-25 00:35:36,112 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-25 00:35:36,112 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-25 00:35:36,112 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-25 00:35:36,112 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-25 00:35:36,112 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-25 00:35:36,113 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-25 00:35:36,113 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-25 00:35:36,113 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-25 00:35:36,113 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-25 00:35:36,119 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 25.10 12:35:36 BoogieIcfgContainer [2024-10-25 00:35:36,120 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-25 00:35:36,120 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-25 00:35:36,120 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-25 00:35:36,121 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-25 00:35:36,121 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.10 12:35:24" (3/4) ... [2024-10-25 00:35:36,122 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-25 00:35:36,123 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-25 00:35:36,124 INFO L158 Benchmark]: Toolchain (without parser) took 12383.08ms. Allocated memory was 174.1MB in the beginning and 230.7MB in the end (delta: 56.6MB). Free memory was 105.2MB in the beginning and 162.1MB in the end (delta: -56.9MB). Peak memory consumption was 960.2kB. Max. memory is 16.1GB. [2024-10-25 00:35:36,124 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 117.4MB. Free memory is still 78.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-25 00:35:36,124 INFO L158 Benchmark]: CACSL2BoogieTranslator took 255.78ms. Allocated memory is still 174.1MB. Free memory was 104.9MB in the beginning and 93.3MB in the end (delta: 11.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-25 00:35:36,125 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.79ms. Allocated memory is still 174.1MB. Free memory was 93.3MB in the beginning and 92.1MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-25 00:35:36,125 INFO L158 Benchmark]: Boogie Preprocessor took 28.09ms. Allocated memory is still 174.1MB. Free memory was 92.1MB in the beginning and 90.3MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-25 00:35:36,125 INFO L158 Benchmark]: RCFGBuilder took 235.22ms. Allocated memory is still 174.1MB. Free memory was 90.3MB in the beginning and 80.1MB in the end (delta: 10.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-25 00:35:36,125 INFO L158 Benchmark]: BuchiAutomizer took 11826.59ms. Allocated memory was 174.1MB in the beginning and 230.7MB in the end (delta: 56.6MB). Free memory was 79.8MB in the beginning and 162.1MB in the end (delta: -82.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-25 00:35:36,126 INFO L158 Benchmark]: Witness Printer took 3.24ms. Allocated memory is still 230.7MB. Free memory is still 162.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-25 00:35:36,127 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.17ms. Allocated memory is still 117.4MB. Free memory is still 78.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 255.78ms. Allocated memory is still 174.1MB. Free memory was 104.9MB in the beginning and 93.3MB in the end (delta: 11.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.79ms. Allocated memory is still 174.1MB. Free memory was 93.3MB in the beginning and 92.1MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 28.09ms. Allocated memory is still 174.1MB. Free memory was 92.1MB in the beginning and 90.3MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 235.22ms. Allocated memory is still 174.1MB. Free memory was 90.3MB in the beginning and 80.1MB in the end (delta: 10.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 11826.59ms. Allocated memory was 174.1MB in the beginning and 230.7MB in the end (delta: 56.6MB). Free memory was 79.8MB in the beginning and 162.1MB in the end (delta: -82.3MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.24ms. Allocated memory is still 230.7MB. Free memory is still 162.1MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 11.7s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 6.2s. Construction of modules took 1.0s. Büchi inclusion checks took 4.1s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 265 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 596 SdHoareTripleChecker+Valid, 1.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 571 mSDsluCounter, 658 SdHoareTripleChecker+Invalid, 1.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 425 mSDsCounter, 357 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1357 IncrementalHoareTripleChecker+Invalid, 1714 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 357 mSolverCounterUnsat, 233 mSDtfsCounter, 1357 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI1 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp82 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf92 smp80 dnf100 smp100 tf112 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 22ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 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-25 00:35:36,151 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:36,347 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Forceful destruction successful, exit code 0 [2024-10-25 00:35:36,548 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-10-25 00:35:36,748 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-25 00:35:36,949 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE