./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 fca748b1 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/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-wip.dd.update-z3-fca748b-m [2024-11-20 22:54:32,130 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-20 22:54:32,206 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-20 22:54:32,213 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-20 22:54:32,214 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-20 22:54:32,242 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-20 22:54:32,243 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-20 22:54:32,243 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-20 22:54:32,244 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-20 22:54:32,244 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-20 22:54:32,244 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-20 22:54:32,245 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-20 22:54:32,245 INFO L153 SettingsManager]: * Use SBE=true [2024-11-20 22:54:32,246 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-20 22:54:32,246 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-20 22:54:32,247 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-20 22:54:32,247 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-20 22:54:32,248 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-20 22:54:32,248 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-20 22:54:32,248 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-20 22:54:32,253 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-20 22:54:32,254 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-20 22:54:32,254 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-20 22:54:32,254 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-20 22:54:32,254 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-20 22:54:32,255 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-20 22:54:32,255 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-20 22:54:32,255 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-20 22:54:32,255 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-20 22:54:32,255 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-20 22:54:32,256 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-20 22:54:32,256 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-20 22:54:32,256 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-20 22:54:32,256 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-20 22:54:32,257 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-20 22:54:32,257 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-20 22:54:32,258 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-20 22:54:32,259 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-20 22:54:32,259 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-20 22:54:32,260 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-11-20 22:54:32,526 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-20 22:54:32,550 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-20 22:54:32,554 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-20 22:54:32,555 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-20 22:54:32,555 INFO L274 PluginConnector]: CDTParser initialized [2024-11-20 22:54:32,556 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-11-20 22:54:34,035 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-20 22:54:34,216 INFO L384 CDTParser]: Found 1 translation units. [2024-11-20 22:54:34,217 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-11-20 22:54:34,226 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/63adcc0ac/ded8ddade3db4c66a9e38450a3920265/FLAG55002d9f9 [2024-11-20 22:54:34,622 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/63adcc0ac/ded8ddade3db4c66a9e38450a3920265 [2024-11-20 22:54:34,625 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-20 22:54:34,629 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-20 22:54:34,630 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-20 22:54:34,631 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-20 22:54:34,636 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-20 22:54:34,637 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,640 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1bb29627 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34, skipping insertion in model container [2024-11-20 22:54:34,640 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,671 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-20 22:54:34,831 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-20 22:54:34,839 INFO L200 MainTranslator]: Completed pre-run [2024-11-20 22:54:34,850 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-20 22:54:34,862 INFO L204 MainTranslator]: Completed translation [2024-11-20 22:54:34,862 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34 WrapperNode [2024-11-20 22:54:34,862 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-20 22:54:34,863 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-20 22:54:34,863 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-20 22:54:34,863 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-20 22:54:34,869 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,874 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,886 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-20 22:54:34,887 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-20 22:54:34,887 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-20 22:54:34,887 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-20 22:54:34,887 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-20 22:54:34,896 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,896 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,898 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,905 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-20 22:54:34,905 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,906 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,907 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,909 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,910 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,910 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,911 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-20 22:54:34,914 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-20 22:54:34,914 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-20 22:54:34,914 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-20 22:54:34,915 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (1/1) ... [2024-11-20 22:54:34,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:34,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:34,944 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:34,946 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-20 22:54:34,985 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-11-20 22:54:34,985 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-11-20 22:54:34,985 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-20 22:54:34,986 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-20 22:54:34,986 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-20 22:54:34,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-20 22:54:35,038 INFO L238 CfgBuilder]: Building ICFG [2024-11-20 22:54:35,040 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-20 22:54:35,146 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-20 22:54:35,147 INFO L287 CfgBuilder]: Performing block encoding [2024-11-20 22:54:35,158 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-20 22:54:35,158 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-20 22:54:35,159 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:54:35 BoogieIcfgContainer [2024-11-20 22:54:35,159 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-20 22:54:35,160 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-20 22:54:35,160 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-20 22:54:35,175 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-20 22:54:35,176 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:54:35,176 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 20.11 10:54:34" (1/3) ... [2024-11-20 22:54:35,177 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@242a4ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 20.11 10:54:35, skipping insertion in model container [2024-11-20 22:54:35,178 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:54:35,178 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:54:34" (2/3) ... [2024-11-20 22:54:35,179 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@242a4ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 20.11 10:54:35, skipping insertion in model container [2024-11-20 22:54:35,179 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:54:35,179 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:54:35" (3/3) ... [2024-11-20 22:54:35,181 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2024-11-20 22:54:35,239 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-20 22:54:35,240 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-20 22:54:35,240 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-20 22:54:35,241 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-20 22:54:35,242 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-20 22:54:35,242 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-20 22:54:35,242 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-20 22:54:35,242 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-20 22:54:35,248 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-20 22:54:35,268 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:35,268 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:35,269 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:35,274 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:54:35,274 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:35,274 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-20 22:54:35,275 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-20 22:54:35,278 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:35,278 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:35,278 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:35,279 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:54:35,279 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:35,285 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-11-20 22:54:35,286 INFO L747 eck$LassoCheckResult]: Loop: 14#$Ultimate##0true ~n := #in~n; 4#L17true assume !(~n < 1); 18#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 14#$Ultimate##0true [2024-11-20 22:54:35,291 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:35,291 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-11-20 22:54:35,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:35,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [268573743] [2024-11-20 22:54:35,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:35,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:35,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:35,379 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:35,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:35,400 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:35,403 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:35,403 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-11-20 22:54:35,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:35,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [951448869] [2024-11-20 22:54:35,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:35,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:35,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:35,410 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:35,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:35,414 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:35,416 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:35,416 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-11-20 22:54:35,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:35,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [191818043] [2024-11-20 22:54:35,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:35,417 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:35,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:35,434 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:35,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:35,446 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:35,571 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:35,571 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:35,572 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:35,572 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:35,572 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:35,572 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,572 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:35,573 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:35,573 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-11-20 22:54:35,573 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:35,573 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:35,587 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,596 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,599 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,603 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,619 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,683 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:35,684 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:35,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,692 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,694 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-20 22:54:35,695 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:35,695 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:35,712 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:35,712 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:35,718 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-20 22:54:35,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,722 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,723 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-20 22:54:35,724 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:35,725 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:35,736 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:35,736 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:35,744 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:35,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,748 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,750 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-20 22:54:35,751 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:35,751 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:35,769 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:35,770 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:35,778 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-11-20 22:54:35,779 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,783 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,786 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-20 22:54:35,786 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:35,787 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:35,810 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-20 22:54:35,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,812 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,816 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:35,817 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-20 22:54:35,817 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:35,872 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:35,877 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-11-20 22:54:35,877 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:35,877 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:35,877 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:35,877 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:35,877 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:35,878 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,878 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:35,878 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:35,878 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-11-20 22:54:35,878 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:35,878 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:35,880 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,883 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,888 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,894 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,903 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:35,958 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:35,962 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:35,963 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,965 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,966 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-20 22:54:35,967 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:35,978 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:35,978 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:35,979 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:35,979 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:35,979 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:35,981 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:35,981 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:35,983 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:35,990 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:35,990 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:35,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:35,991 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:35,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-20 22:54:35,996 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:36,006 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:36,006 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:36,006 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:36,006 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:36,006 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:36,007 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:36,007 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:36,009 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:36,015 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:36,016 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:36,016 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:36,019 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:36,020 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-20 22:54:36,023 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:36,039 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:36,039 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:36,039 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:36,039 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:36,039 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:36,040 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:36,040 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:36,042 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:36,050 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-20 22:54:36,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:36,052 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:36,054 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:36,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-20 22:54:36,059 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:36,070 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:36,070 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:36,070 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:36,070 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:36,070 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:36,071 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:36,071 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:36,074 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:36,077 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:36,078 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:36,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:36,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:36,180 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:36,181 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-20 22:54:36,182 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:36,182 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:36,182 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:36,183 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-11-20 22:54:36,189 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-11-20 22:54:36,192 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:36,218 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:36,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,249 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-20 22:54:36,250 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:36,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,276 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:36,277 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:36,329 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:36,359 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-20 22:54:36,361 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-20 22:54:36,382 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-11-20 22:54:36,480 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 40 states and 53 transitions. Complement of second has 16 states. [2024-11-20 22:54:36,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:36,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-20 22:54:36,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-20 22:54:36,490 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-20 22:54:36,491 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:36,491 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-20 22:54:36,492 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:36,492 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-20 22:54:36,492 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:36,493 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-11-20 22:54:36,497 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:36,501 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-11-20 22:54:36,502 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-20 22:54:36,502 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-20 22:54:36,503 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-20 22:54:36,504 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:36,504 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-20 22:54:36,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-20 22:54:36,523 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-20 22:54:36,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-20 22:54:36,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-20 22:54:36,525 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-20 22:54:36,525 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-20 22:54:36,525 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-20 22:54:36,525 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-20 22:54:36,526 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:36,526 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:36,526 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:36,527 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:36,527 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:36,527 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-11-20 22:54:36,528 INFO L747 eck$LassoCheckResult]: Loop: 118#L22-1 call #t~ret5 := fibonacci(~n - 2);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume !(~n < 1); 136#L19 assume !(1 == ~n); 121#L22 call #t~ret4 := fibonacci(~n - 1);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume ~n < 1;#res := 0; 134#fibonacciFINAL assume true; 135#fibonacciEXIT >#31#return; 118#L22-1 [2024-11-20 22:54:36,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:36,528 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-11-20 22:54:36,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:36,529 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2094047078] [2024-11-20 22:54:36,529 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:36,529 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:36,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-20 22:54:36,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,693 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-20 22:54:36,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:36,694 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2094047078] [2024-11-20 22:54:36,695 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2094047078] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:54:36,698 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-20 22:54:36,698 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-20 22:54:36,699 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1946458495] [2024-11-20 22:54:36,699 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:54:36,701 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:54:36,701 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:36,701 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-11-20 22:54:36,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:36,701 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1732695112] [2024-11-20 22:54:36,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:36,702 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:36,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,746 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-20 22:54:36,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,774 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-20 22:54:36,775 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:36,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1732695112] [2024-11-20 22:54:36,775 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1732695112] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:54:36,775 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-20 22:54:36,775 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-20 22:54:36,775 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1603730209] [2024-11-20 22:54:36,775 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:54:36,776 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-20 22:54:36,776 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:36,778 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-20 22:54:36,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-20 22:54:36,780 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-20 22:54:36,855 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:36,855 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-20 22:54:36,856 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-20 22:54:36,857 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:36,858 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-20 22:54:36,859 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-20 22:54:36,859 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-20 22:54:36,859 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-20 22:54:36,859 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:36,859 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-20 22:54:36,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-20 22:54:36,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-20 22:54:36,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-20 22:54:36,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-20 22:54:36,865 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-20 22:54:36,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-20 22:54:36,867 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-20 22:54:36,867 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-20 22:54:36,867 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-20 22:54:36,869 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-20 22:54:36,870 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:36,870 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:36,871 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:36,871 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-20 22:54:36,872 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-11-20 22:54:36,872 INFO L747 eck$LassoCheckResult]: Loop: 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume 1 == ~n;#res := 1; 210#fibonacciFINAL assume true; 207#fibonacciEXIT >#31#return; 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume ~n < 1;#res := 0; 212#fibonacciFINAL assume true; 199#fibonacciEXIT >#33#return; 200#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 204#fibonacciFINAL assume true; 206#fibonacciEXIT >#31#return; 189#L22-1 [2024-11-20 22:54:36,873 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:36,873 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-11-20 22:54:36,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:36,874 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1736114574] [2024-11-20 22:54:36,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:36,875 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:36,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-20 22:54:36,956 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:36,983 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:36,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:36,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1736114574] [2024-11-20 22:54:36,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1736114574] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:36,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1546410579] [2024-11-20 22:54:36,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:36,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:36,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:36,987 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:54:36,988 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-20 22:54:37,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:37,020 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-20 22:54:37,021 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:37,059 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:37,060 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:37,183 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:37,183 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1546410579] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:37,183 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:37,183 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-20 22:54:37,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023893420] [2024-11-20 22:54:37,184 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:37,184 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:54:37,184 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:37,184 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-11-20 22:54:37,184 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:37,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1471032691] [2024-11-20 22:54:37,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:37,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:37,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:37,202 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:37,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:37,216 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:37,433 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:37,433 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:37,434 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:37,434 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:37,434 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:37,434 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,434 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:37,434 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:37,434 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-11-20 22:54:37,435 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:37,435 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:37,435 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,439 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,444 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,447 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,450 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,487 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:37,488 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:37,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:37,489 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:37,490 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-20 22:54:37,491 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:37,491 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:37,502 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:37,503 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:37,509 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:37,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:37,510 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:37,511 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-20 22:54:37,512 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:37,513 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:37,531 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:37,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:37,532 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:37,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-20 22:54:37,534 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:37,534 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:37,548 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:37,554 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-11-20 22:54:37,555 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:37,555 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:37,555 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:37,555 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:37,555 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:37,555 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,555 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:37,555 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:37,555 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-11-20 22:54:37,555 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:37,556 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:37,556 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,563 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,566 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,568 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,571 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:37,606 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:37,606 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:37,606 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,606 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:37,607 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:37,608 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-20 22:54:37,609 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:37,620 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:37,620 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:37,620 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:37,620 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:37,620 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:37,622 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:37,622 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:37,624 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:37,627 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:37,627 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:37,627 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:37,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:37,630 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:37,632 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-20 22:54:37,633 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:37,633 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:37,633 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:37,633 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-20 22:54:37,640 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:37,641 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:37,659 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:37,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:37,680 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-20 22:54:37,681 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:37,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:37,805 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-20 22:54:37,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:37,959 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:37,960 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-20 22:54:37,961 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-20 22:54:38,211 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-11-20 22:54:38,239 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 152 states and 210 transitions. Complement of second has 54 states. [2024-11-20 22:54:38,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:38,243 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-20 22:54:38,244 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-20 22:54:38,244 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-20 22:54:38,244 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:38,244 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-20 22:54:38,245 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:38,245 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-20 22:54:38,246 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:38,246 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-20 22:54:38,273 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-20 22:54:38,282 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-20 22:54:38,285 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-20 22:54:38,287 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-20 22:54:38,287 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-20 22:54:38,288 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:38,288 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-20 22:54:38,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-20 22:54:38,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-20 22:54:38,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 70 states have internal predecessors, (81), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (35), 22 states have call predecessors, (35), 23 states have call successors, (35) [2024-11-20 22:54:38,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-20 22:54:38,301 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-20 22:54:38,301 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:38,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-20 22:54:38,302 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-20 22:54:38,302 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-11-20 22:54:38,435 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:38,435 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-20 22:54:38,436 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-20 22:54:38,439 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-20 22:54:38,444 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-20 22:54:38,444 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-20 22:54:38,445 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-20 22:54:38,445 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-20 22:54:38,445 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:38,445 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-20 22:54:38,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-20 22:54:38,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-20 22:54:38,454 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-11-20 22:54:38,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-20 22:54:38,455 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-20 22:54:38,456 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-20 22:54:38,457 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-20 22:54:38,457 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-20 22:54:38,457 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-20 22:54:38,458 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-20 22:54:38,458 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:38,458 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:38,459 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:38,460 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:38,460 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-11-20 22:54:38,460 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-11-20 22:54:38,460 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:38,461 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2024-11-20 22:54:38,461 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:38,461 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [81778325] [2024-11-20 22:54:38,461 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:38,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:38,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:38,599 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-20 22:54:38,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:38,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-20 22:54:38,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:38,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-20 22:54:38,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:38,687 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-20 22:54:38,688 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:38,688 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [81778325] [2024-11-20 22:54:38,688 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [81778325] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:38,688 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1760742842] [2024-11-20 22:54:38,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:38,689 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:38,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:38,691 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-11-20 22:54:38,693 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-11-20 22:54:38,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:38,729 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-20 22:54:38,731 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:38,794 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-20 22:54:38,794 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:39,073 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-20 22:54:39,073 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1760742842] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:39,073 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:39,074 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-20 22:54:39,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [576507749] [2024-11-20 22:54:39,074 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:39,074 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:54:39,075 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:39,075 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2024-11-20 22:54:39,075 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:39,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [54512720] [2024-11-20 22:54:39,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:39,076 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:39,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:39,079 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:39,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:39,082 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:39,176 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:39,176 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:39,176 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:39,176 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:39,176 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:39,176 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,176 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:39,176 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:39,176 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-11-20 22:54:39,176 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:39,177 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:39,177 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,181 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,189 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,190 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,192 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,224 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:39,224 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:39,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,227 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:39,228 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-20 22:54:39,230 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:39,230 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:39,244 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:39,244 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-11-20 22:54:39,252 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-11-20 22:54:39,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,255 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:39,257 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-20 22:54:39,258 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:39,258 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:39,282 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:39,282 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,282 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,284 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-11-20 22:54:39,286 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-11-20 22:54:39,287 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:39,288 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:39,304 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:39,312 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-11-20 22:54:39,313 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:39,313 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:39,313 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:39,313 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:39,313 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:39,313 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,313 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:39,313 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:39,313 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-11-20 22:54:39,313 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:39,313 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:39,314 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,318 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,323 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,326 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,328 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:39,359 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:39,360 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:39,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,360 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,362 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:39,364 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-20 22:54:39,365 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:39,377 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:39,378 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:39,378 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:39,378 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:39,378 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:39,383 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:39,383 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:39,387 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:39,395 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-11-20 22:54:39,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,397 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:39,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-20 22:54:39,400 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:39,412 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:39,412 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:39,413 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:39,413 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:39,413 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:39,414 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:39,414 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:39,416 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:39,418 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:39,418 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:39,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:39,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:39,420 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:39,421 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-20 22:54:39,422 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:39,422 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:39,422 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:39,422 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-20 22:54:39,427 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:39,429 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:39,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:39,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:39,484 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-20 22:54:39,486 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:39,628 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:39,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:39,699 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-20 22:54:39,700 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:39,778 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:39,779 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-11-20 22:54:39,779 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-11-20 22:54:39,976 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-11-20 22:54:39,977 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-11-20 22:54:39,977 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-11-20 22:54:39,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-20 22:54:39,978 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-20 22:54:39,978 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:39,978 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:39,996 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:40,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:40,037 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-20 22:54:40,038 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:40,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:40,216 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-20 22:54:40,217 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:40,288 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:40,289 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-11-20 22:54:40,289 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-11-20 22:54:40,467 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-11-20 22:54:40,470 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-11-20 22:54:40,471 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-11-20 22:54:40,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-11-20 22:54:40,471 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-20 22:54:40,471 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:40,471 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:40,482 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:40,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:40,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-20 22:54:40,528 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:40,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:40,712 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-20 22:54:40,713 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:40,790 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:40,791 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-20 22:54:40,791 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-11-20 22:54:41,036 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-11-20 22:54:41,037 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-11-20 22:54:41,038 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-11-20 22:54:41,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-11-20 22:54:41,038 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-20 22:54:41,039 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:41,039 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-11-20 22:54:41,039 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:41,039 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-11-20 22:54:41,040 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:41,043 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 808 states and 1112 transitions. [2024-11-20 22:54:41,062 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-11-20 22:54:41,074 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 808 states to 427 states and 634 transitions. [2024-11-20 22:54:41,074 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 166 [2024-11-20 22:54:41,075 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-11-20 22:54:41,075 INFO L73 IsDeterministic]: Start isDeterministic. Operand 427 states and 634 transitions. [2024-11-20 22:54:41,075 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:41,075 INFO L218 hiAutomatonCegarLoop]: Abstraction has 427 states and 634 transitions. [2024-11-20 22:54:41,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states and 634 transitions. [2024-11-20 22:54:41,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 352. [2024-11-20 22:54:41,117 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-11-20 22:54:41,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 479 transitions. [2024-11-20 22:54:41,126 INFO L240 hiAutomatonCegarLoop]: Abstraction has 352 states and 479 transitions. [2024-11-20 22:54:41,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:41,127 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-20 22:54:41,127 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-11-20 22:54:41,128 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-11-20 22:54:41,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:41,453 INFO L93 Difference]: Finished difference Result 707 states and 1054 transitions. [2024-11-20 22:54:41,453 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 707 states and 1054 transitions. [2024-11-20 22:54:41,465 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-20 22:54:41,479 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 707 states to 676 states and 1009 transitions. [2024-11-20 22:54:41,479 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 296 [2024-11-20 22:54:41,481 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 299 [2024-11-20 22:54:41,482 INFO L73 IsDeterministic]: Start isDeterministic. Operand 676 states and 1009 transitions. [2024-11-20 22:54:41,482 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:41,482 INFO L218 hiAutomatonCegarLoop]: Abstraction has 676 states and 1009 transitions. [2024-11-20 22:54:41,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 676 states and 1009 transitions. [2024-11-20 22:54:41,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 676 to 628. [2024-11-20 22:54:41,516 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-11-20 22:54:41,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 936 transitions. [2024-11-20 22:54:41,523 INFO L240 hiAutomatonCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-11-20 22:54:41,524 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-20 22:54:41,524 INFO L425 stractBuchiCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-11-20 22:54:41,524 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-20 22:54:41,525 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 628 states and 936 transitions. [2024-11-20 22:54:41,529 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-20 22:54:41,529 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:41,529 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:41,530 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:41,530 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:41,530 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-11-20 22:54:41,531 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-11-20 22:54:41,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:41,531 INFO L85 PathProgramCache]: Analyzing trace with hash 1729544275, now seen corresponding path program 1 times [2024-11-20 22:54:41,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:41,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [267878712] [2024-11-20 22:54:41,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:41,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,798 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-20 22:54:41,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,837 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:41,837 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:41,837 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [267878712] [2024-11-20 22:54:41,837 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [267878712] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:41,837 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1818929176] [2024-11-20 22:54:41,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:41,838 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:41,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:41,840 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-11-20 22:54:41,842 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-11-20 22:54:41,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:41,876 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-20 22:54:41,878 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:41,946 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:41,946 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:42,174 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-20 22:54:42,174 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1818929176] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:42,174 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:42,174 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2024-11-20 22:54:42,175 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [613026325] [2024-11-20 22:54:42,175 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:42,175 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:54:42,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:42,176 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-11-20 22:54:42,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:42,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1837046495] [2024-11-20 22:54:42,176 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:42,177 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:42,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:42,180 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:42,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:42,182 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:42,216 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:42,216 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:42,216 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:42,216 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:42,216 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:42,216 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,216 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:42,216 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:42,216 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-11-20 22:54:42,217 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:42,217 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:42,217 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,220 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,221 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,226 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,232 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,255 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:42,256 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:42,256 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,257 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,258 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-20 22:54:42,259 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:42,259 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,271 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:42,271 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:42,277 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:42,277 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,278 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-20 22:54:42,280 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:42,280 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,291 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:42,291 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:42,297 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:42,297 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,297 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,298 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,299 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-20 22:54:42,300 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:42,300 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,317 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:42,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,318 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,318 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-11-20 22:54:42,319 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-11-20 22:54:42,320 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:42,321 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:42,343 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:42,347 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-11-20 22:54:42,347 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:42,347 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:42,347 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:42,347 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:42,347 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:42,347 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,348 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:42,348 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:42,348 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-11-20 22:54:42,348 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:42,348 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:42,349 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,351 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,352 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,358 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,360 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:42,385 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:42,385 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:42,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,385 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,386 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,388 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-20 22:54:42,388 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:42,398 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:42,399 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:42,399 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:42,399 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:42,399 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:42,399 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:42,400 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:42,401 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:42,407 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2024-11-20 22:54:42,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,409 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,410 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-20 22:54:42,411 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:42,420 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:42,421 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:42,421 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:42,421 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:42,421 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:42,421 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:42,421 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:42,422 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:42,428 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:42,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,429 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,430 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,431 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-20 22:54:42,432 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:42,442 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:42,442 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:42,443 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:42,443 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:42,443 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:42,443 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:42,443 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:42,445 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:42,447 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:54:42,448 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:54:42,448 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:42,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:42,449 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:42,450 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-20 22:54:42,451 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:42,451 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:42,451 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:42,451 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-11-20 22:54:42,458 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:42,458 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:42,471 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:42,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,536 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,538 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:42,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,629 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,629 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:42,652 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:42,653 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:54:42,653 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-11-20 22:54:42,713 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-11-20 22:54:42,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:42,714 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-11-20 22:54:42,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-20 22:54:42,715 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-20 22:54:42,715 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:42,715 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:42,725 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:42,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,787 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,788 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:42,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:42,887 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:42,887 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:42,912 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:42,912 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:54:42,913 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-11-20 22:54:42,978 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-11-20 22:54:42,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:42,979 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-11-20 22:54:42,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-20 22:54:42,979 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-20 22:54:42,979 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:42,979 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:42,990 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:43,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,048 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-20 22:54:43,052 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:43,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:43,151 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:43,151 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:43,175 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:43,176 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:54:43,176 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-11-20 22:54:43,261 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-11-20 22:54:43,262 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:43,262 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-11-20 22:54:43,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-20 22:54:43,263 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-20 22:54:43,264 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:43,264 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-20 22:54:43,264 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:43,264 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-11-20 22:54:43,265 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:43,265 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1163 transitions. [2024-11-20 22:54:43,274 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-20 22:54:43,283 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 996 transitions. [2024-11-20 22:54:43,283 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2024-11-20 22:54:43,283 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2024-11-20 22:54:43,283 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 996 transitions. [2024-11-20 22:54:43,284 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:43,284 INFO L218 hiAutomatonCegarLoop]: Abstraction has 684 states and 996 transitions. [2024-11-20 22:54:43,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 996 transitions. [2024-11-20 22:54:43,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2024-11-20 22:54:43,300 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-11-20 22:54:43,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 960 transitions. [2024-11-20 22:54:43,305 INFO L240 hiAutomatonCegarLoop]: Abstraction has 654 states and 960 transitions. [2024-11-20 22:54:43,305 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:43,305 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-20 22:54:43,306 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-11-20 22:54:43,306 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-11-20 22:54:43,369 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:43,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:43,612 INFO L93 Difference]: Finished difference Result 781 states and 1180 transitions. [2024-11-20 22:54:43,612 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 781 states and 1180 transitions. [2024-11-20 22:54:43,620 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-20 22:54:43,631 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 781 states to 760 states and 1148 transitions. [2024-11-20 22:54:43,631 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 279 [2024-11-20 22:54:43,631 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 282 [2024-11-20 22:54:43,632 INFO L73 IsDeterministic]: Start isDeterministic. Operand 760 states and 1148 transitions. [2024-11-20 22:54:43,632 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:43,632 INFO L218 hiAutomatonCegarLoop]: Abstraction has 760 states and 1148 transitions. [2024-11-20 22:54:43,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states and 1148 transitions. [2024-11-20 22:54:43,652 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 702. [2024-11-20 22:54:43,653 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-11-20 22:54:43,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 702 states to 702 states and 1022 transitions. [2024-11-20 22:54:43,658 INFO L240 hiAutomatonCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-11-20 22:54:43,659 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-20 22:54:43,661 INFO L425 stractBuchiCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-11-20 22:54:43,661 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-20 22:54:43,661 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 702 states and 1022 transitions. [2024-11-20 22:54:43,666 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-20 22:54:43,666 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:54:43,666 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:54:43,667 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:54:43,668 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-20 22:54:43,668 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-11-20 22:54:43,668 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-11-20 22:54:43,669 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:43,669 INFO L85 PathProgramCache]: Analyzing trace with hash 1537328375, now seen corresponding path program 2 times [2024-11-20 22:54:43,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:43,669 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [295364708] [2024-11-20 22:54:43,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:43,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:43,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:44,017 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-20 22:54:44,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:44,020 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-20 22:54:44,021 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:54:44,021 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [295364708] [2024-11-20 22:54:44,021 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [295364708] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:54:44,021 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [933332221] [2024-11-20 22:54:44,021 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-20 22:54:44,021 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:54:44,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,024 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-11-20 22:54:44,025 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-11-20 22:54:44,061 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-20 22:54:44,061 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-20 22:54:44,063 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-20 22:54:44,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:44,119 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-20 22:54:44,120 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:54:44,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-11-20 22:54:44,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [933332221] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:54:44,333 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:54:44,333 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2024-11-20 22:54:44,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1211132757] [2024-11-20 22:54:44,334 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:54:44,334 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:54:44,334 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:44,334 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-11-20 22:54:44,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:54:44,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1020016879] [2024-11-20 22:54:44,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:54:44,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:54:44,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:44,337 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:54:44,338 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:54:44,339 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:54:44,391 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:44,391 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:44,391 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:44,391 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:44,392 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:54:44,392 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,392 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:44,392 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:44,392 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-11-20 22:54:44,392 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:44,392 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:44,393 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,395 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,396 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,405 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,444 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:44,444 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:54:44,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,444 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,447 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,449 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-20 22:54:44,450 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:44,450 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,460 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:44,460 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:44,466 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,467 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,468 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,469 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-20 22:54:44,470 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:44,470 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,480 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:54:44,481 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:54:44,486 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2024-11-20 22:54:44,487 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,488 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,489 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-20 22:54:44,490 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:54:44,490 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,514 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,514 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,515 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,516 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,516 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-20 22:54:44,517 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:54:44,517 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:54:44,657 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:54:44,663 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2024-11-20 22:54:44,664 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:54:44,664 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:54:44,664 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:54:44,664 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:54:44,664 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:54:44,664 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,664 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:54:44,664 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:54:44,664 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-11-20 22:54:44,664 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:54:44,664 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:54:44,665 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,667 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,668 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,675 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:54:44,707 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:54:44,707 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:54:44,707 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,709 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,710 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-20 22:54:44,711 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:44,720 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:44,721 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:44,721 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:44,721 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:44,721 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:44,721 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:44,721 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:44,725 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:44,732 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,732 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,732 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,735 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-11-20 22:54:44,736 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-11-20 22:54:44,736 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:44,747 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:44,747 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:44,747 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:44,747 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:44,747 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:44,747 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:44,747 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:44,751 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:54:44,758 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Ended with exit code 0 [2024-11-20 22:54:44,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,760 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-20 22:54:44,761 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-20 22:54:44,771 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:54:44,771 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:54:44,772 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:54:44,772 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:54:44,772 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:54:44,773 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:54:44,773 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:54:44,775 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:54:44,777 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:54:44,777 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:54:44,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:54:44,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:54:44,780 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:54:44,781 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-20 22:54:44,782 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:54:44,782 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:54:44,782 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:54:44,782 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-20 22:54:44,790 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,791 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:54:44,803 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:44,819 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:44,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:44,873 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-20 22:54:44,875 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:44,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:44,985 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:44,985 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,021 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:45,022 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-20 22:54:45,022 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-11-20 22:54:45,070 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-11-20 22:54:45,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:45,071 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-11-20 22:54:45,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-20 22:54:45,072 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2024-11-20 22:54:45,072 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:45,072 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:54:45,083 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:54:45,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:45,146 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-20 22:54:45,147 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:54:45,248 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:54:45,248 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:54:45,281 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:54:45,282 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-20 22:54:45,282 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-11-20 22:54:45,364 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-11-20 22:54:45,365 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-20 22:54:45,365 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-11-20 22:54:45,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-20 22:54:45,365 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2024-11-20 22:54:45,366 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:45,366 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-11-20 22:54:45,366 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:45,366 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2024-11-20 22:54:45,366 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:54:45,366 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 944 states and 1356 transitions. [2024-11-20 22:54:45,375 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-20 22:54:45,385 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 944 states to 874 states and 1278 transitions. [2024-11-20 22:54:45,385 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2024-11-20 22:54:45,385 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 310 [2024-11-20 22:54:45,386 INFO L73 IsDeterministic]: Start isDeterministic. Operand 874 states and 1278 transitions. [2024-11-20 22:54:45,386 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:54:45,386 INFO L218 hiAutomatonCegarLoop]: Abstraction has 874 states and 1278 transitions. [2024-11-20 22:54:45,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 874 states and 1278 transitions. [2024-11-20 22:54:45,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 874 to 854. [2024-11-20 22:54:45,404 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-11-20 22:54:45,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1254 transitions. [2024-11-20 22:54:45,409 INFO L240 hiAutomatonCegarLoop]: Abstraction has 854 states and 1254 transitions. [2024-11-20 22:54:45,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:54:45,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-20 22:54:45,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2024-11-20 22:54:45,410 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-11-20 22:54:45,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:54:45,693 INFO L93 Difference]: Finished difference Result 471 states and 558 transitions. [2024-11-20 22:54:45,693 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 471 states and 558 transitions. [2024-11-20 22:54:45,697 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:54:45,697 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 471 states to 0 states and 0 transitions. [2024-11-20 22:54:45,697 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-20 22:54:45,697 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-20 22:54:45,697 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-20 22:54:45,697 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-20 22:54:45,697 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:54:45,698 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:54:45,698 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-20 22:54:45,698 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:54:45,698 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-20 22:54:45,698 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-20 22:54:45,698 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:54:45,699 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-20 22:54:45,705 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 20.11 10:54:45 BoogieIcfgContainer [2024-11-20 22:54:45,706 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-20 22:54:45,706 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-20 22:54:45,706 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-20 22:54:45,706 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-20 22:54:45,707 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:54:35" (3/4) ... [2024-11-20 22:54:45,709 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-20 22:54:45,710 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-20 22:54:45,711 INFO L158 Benchmark]: Toolchain (without parser) took 11082.51ms. Allocated memory was 155.2MB in the beginning and 237.0MB in the end (delta: 81.8MB). Free memory was 83.7MB in the beginning and 104.2MB in the end (delta: -20.6MB). Peak memory consumption was 63.3MB. Max. memory is 16.1GB. [2024-11-20 22:54:45,711 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 155.2MB. Free memory was 105.6MB in the beginning and 105.5MB in the end (delta: 129.1kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:54:45,711 INFO L158 Benchmark]: CACSL2BoogieTranslator took 232.55ms. Allocated memory is still 155.2MB. Free memory was 83.5MB in the beginning and 71.8MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-20 22:54:45,712 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.88ms. Allocated memory is still 155.2MB. Free memory was 71.8MB in the beginning and 70.3MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-20 22:54:45,712 INFO L158 Benchmark]: Boogie Preprocessor took 24.41ms. Allocated memory is still 155.2MB. Free memory was 70.3MB in the beginning and 68.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-20 22:54:45,712 INFO L158 Benchmark]: RCFGBuilder took 245.52ms. Allocated memory is still 155.2MB. Free memory was 68.8MB in the beginning and 122.8MB in the end (delta: -54.0MB). Peak memory consumption was 13.6MB. Max. memory is 16.1GB. [2024-11-20 22:54:45,712 INFO L158 Benchmark]: BuchiAutomizer took 10545.85ms. Allocated memory was 155.2MB in the beginning and 237.0MB in the end (delta: 81.8MB). Free memory was 122.7MB in the beginning and 104.2MB in the end (delta: 18.4MB). Peak memory consumption was 100.0MB. Max. memory is 16.1GB. [2024-11-20 22:54:45,712 INFO L158 Benchmark]: Witness Printer took 4.21ms. Allocated memory is still 237.0MB. Free memory is still 104.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:54:45,715 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.16ms. Allocated memory is still 155.2MB. Free memory was 105.6MB in the beginning and 105.5MB in the end (delta: 129.1kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 232.55ms. Allocated memory is still 155.2MB. Free memory was 83.5MB in the beginning and 71.8MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.88ms. Allocated memory is still 155.2MB. Free memory was 71.8MB in the beginning and 70.3MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 24.41ms. Allocated memory is still 155.2MB. Free memory was 70.3MB in the beginning and 68.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 245.52ms. Allocated memory is still 155.2MB. Free memory was 68.8MB in the beginning and 122.8MB in the end (delta: -54.0MB). Peak memory consumption was 13.6MB. Max. memory is 16.1GB. * BuchiAutomizer took 10545.85ms. Allocated memory was 155.2MB in the beginning and 237.0MB in the end (delta: 81.8MB). Free memory was 122.7MB in the beginning and 104.2MB in the end (delta: 18.4MB). Peak memory consumption was 100.0MB. Max. memory is 16.1GB. * Witness Printer took 4.21ms. Allocated memory is still 237.0MB. Free memory is still 104.2MB. 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 10.4s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 4.9s. Construction of modules took 1.0s. Büchi inclusion checks took 4.0s. 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: 20ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.5s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-20 22:54:45,737 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Ended with exit code 0 [2024-11-20 22:54:45,939 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-11-20 22:54:46,137 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-20 22:54:46,336 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-20 22:54:46,537 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE