./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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 ../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-?-c7c6ca5-m [2024-11-09 16:04:41,993 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 16:04:42,064 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-09 16:04:42,067 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 16:04:42,067 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 16:04:42,094 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 16:04:42,095 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 16:04:42,095 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 16:04:42,095 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 16:04:42,096 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 16:04:42,096 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 16:04:42,096 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 16:04:42,097 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 16:04:42,098 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 16:04:42,099 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 16:04:42,099 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 16:04:42,099 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 16:04:42,099 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 16:04:42,099 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 16:04:42,100 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 16:04:42,103 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 16:04:42,103 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 16:04:42,103 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 16:04:42,103 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 16:04:42,104 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 16:04:42,104 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 16:04:42,104 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 16:04:42,104 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 16:04:42,104 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 16:04:42,104 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 16:04:42,105 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 16:04:42,105 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 16:04:42,105 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 16:04:42,105 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 16:04:42,105 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 16:04:42,105 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 16:04:42,105 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 16:04:42,106 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 16:04:42,106 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 16:04:42,106 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-09 16:04:42,359 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 16:04:42,394 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 16:04:42,396 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 16:04:42,401 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 16:04:42,402 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 16:04:42,403 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci02.c [2024-11-09 16:04:43,898 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 16:04:44,042 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 16:04:44,043 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-11-09 16:04:44,052 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a816054aa/8eb1e621d4124ef9bea144aff9e1ef54/FLAGcec203db1 [2024-11-09 16:04:44,460 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a816054aa/8eb1e621d4124ef9bea144aff9e1ef54 [2024-11-09 16:04:44,463 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 16:04:44,467 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 16:04:44,471 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 16:04:44,472 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 16:04:44,477 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 16:04:44,478 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,478 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3133ada1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44, skipping insertion in model container [2024-11-09 16:04:44,478 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,498 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 16:04:44,759 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:04:44,771 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 16:04:44,793 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:04:44,814 INFO L204 MainTranslator]: Completed translation [2024-11-09 16:04:44,815 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44 WrapperNode [2024-11-09 16:04:44,815 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 16:04:44,816 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 16:04:44,816 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 16:04:44,816 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 16:04:44,829 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,837 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,864 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-09 16:04:44,864 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 16:04:44,865 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 16:04:44,866 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 16:04:44,866 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 16:04:44,877 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,880 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,885 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,900 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-09 16:04:44,901 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,901 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,904 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,905 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,910 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,910 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,911 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 16:04:44,915 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 16:04:44,915 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 16:04:44,915 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 16:04:44,916 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (1/1) ... [2024-11-09 16:04:44,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:44,945 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:44,968 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-09 16:04:44,970 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-09 16:04:45,002 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-11-09 16:04:45,003 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-11-09 16:04:45,003 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 16:04:45,003 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 16:04:45,003 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 16:04:45,003 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 16:04:45,050 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 16:04:45,052 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 16:04:45,144 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 16:04:45,144 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 16:04:45,152 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 16:04:45,153 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 16:04:45,153 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:04:45 BoogieIcfgContainer [2024-11-09 16:04:45,153 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 16:04:45,154 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 16:04:45,154 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 16:04:45,157 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 16:04:45,157 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:45,157 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 04:04:44" (1/3) ... [2024-11-09 16:04:45,158 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@52eff55e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:04:45, skipping insertion in model container [2024-11-09 16:04:45,158 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:45,158 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:44" (2/3) ... [2024-11-09 16:04:45,159 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@52eff55e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:04:45, skipping insertion in model container [2024-11-09 16:04:45,159 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:45,159 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:04:45" (3/3) ... [2024-11-09 16:04:45,160 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2024-11-09 16:04:45,205 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 16:04:45,206 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 16:04:45,206 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 16:04:45,206 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 16:04:45,207 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 16:04:45,208 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 16:04:45,208 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 16:04:45,208 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 16:04:45,212 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-09 16:04:45,231 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:04:45,231 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:45,231 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:45,236 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:04:45,236 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:04:45,236 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 16:04:45,236 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-09 16:04:45,238 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:04:45,239 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:45,239 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:45,239 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:04:45,239 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:04:45,245 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-09 16:04:45,247 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-09 16:04:45,251 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:45,251 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-11-09 16:04:45,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:45,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [778750951] [2024-11-09 16:04:45,263 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:45,263 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:45,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:45,346 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:45,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:45,372 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:45,374 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:45,378 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-11-09 16:04:45,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:45,378 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [937665] [2024-11-09 16:04:45,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:45,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:45,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:45,383 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:45,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:45,387 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:45,388 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:45,388 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-11-09 16:04:45,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:45,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [685735832] [2024-11-09 16:04:45,389 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:45,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:45,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:45,396 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:45,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:45,403 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:45,496 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:45,496 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:45,496 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:45,496 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:45,496 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:45,497 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,497 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:45,497 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:45,497 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-11-09 16:04:45,497 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:45,497 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:45,508 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,516 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,518 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,520 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,528 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,573 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:45,573 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:45,575 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,575 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,576 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-09 16:04:45,578 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-09 16:04:45,579 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:45,579 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:45,594 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:45,595 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:45,606 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-09 16:04:45,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,608 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-09 16:04:45,611 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-09 16:04:45,612 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:45,612 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:45,624 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:45,625 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-09 16:04:45,636 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-09 16:04:45,636 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,638 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-09 16:04:45,639 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-09 16:04:45,640 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:45,640 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:45,652 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:45,652 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:45,663 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:45,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,664 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,668 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-09 16:04:45,669 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-09 16:04:45,670 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:45,671 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:45,693 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:45,694 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,694 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,695 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-09 16:04:45,697 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-09 16:04:45,698 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:45,698 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:45,752 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:45,757 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-09 16:04:45,757 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:45,758 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:45,758 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:45,758 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:45,758 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:45,758 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,758 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:45,758 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:45,758 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-11-09 16:04:45,758 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:45,758 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:45,760 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,762 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,764 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,766 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,773 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:45,817 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:45,821 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:45,823 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,823 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,827 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-09 16:04:45,828 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-09 16:04:45,831 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-09 16:04:45,843 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:45,844 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:45,845 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:45,845 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:45,845 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:45,846 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:45,846 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:45,854 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:45,870 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-09 16:04:45,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,872 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-09 16:04:45,874 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-09 16:04:45,875 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-09 16:04:45,885 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:45,885 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:45,885 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:45,886 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:45,886 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:45,886 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:45,886 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:45,887 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:45,898 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-09 16:04:45,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,901 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-09 16:04:45,902 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-09 16:04:45,903 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-09 16:04:45,912 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:45,913 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:45,913 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:45,913 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:45,913 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:45,913 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:45,913 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:45,915 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:45,928 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-09 16:04:45,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,929 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,931 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-09 16:04:45,932 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-09 16:04:45,933 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-09 16:04:45,943 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:45,943 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:45,943 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:45,943 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:45,943 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:45,944 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:45,944 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:45,946 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:45,949 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:04:45,949 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:04:45,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:45,950 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:45,968 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-09 16:04:45,969 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-09 16:04:45,970 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:45,970 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:45,970 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:45,971 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-11-09 16:04:45,985 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-09 16:04:45,987 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:46,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:46,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,063 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 16:04:46,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:46,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,102 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:46,102 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:46,172 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-09 16:04:46,255 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-09 16:04:46,272 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-09 16:04:46,275 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-09 16:04:46,407 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-09 16:04:46,410 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-09 16:04:46,413 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-09 16:04:46,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-09 16:04:46,415 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-09 16:04:46,416 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:46,416 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-09 16:04:46,416 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:46,416 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-09 16:04:46,416 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:46,417 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-11-09 16:04:46,419 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:04:46,422 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-11-09 16:04:46,423 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-09 16:04:46,423 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-09 16:04:46,423 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-09 16:04:46,424 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:46,424 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-09 16:04:46,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-09 16:04:46,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-09 16:04:46,441 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-09 16:04:46,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-09 16:04:46,442 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:04:46,442 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:04:46,442 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 16:04:46,442 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-09 16:04:46,443 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:04:46,443 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:46,443 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:46,444 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:46,444 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:46,444 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-09 16:04:46,444 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-09 16:04:46,445 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:46,445 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-11-09 16:04:46,445 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:46,445 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [286274675] [2024-11-09 16:04:46,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:46,445 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:46,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,513 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:04:46,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,540 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-09 16:04:46,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:04:46,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [286274675] [2024-11-09 16:04:46,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [286274675] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:04:46,541 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:04:46,541 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:04:46,541 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1279430165] [2024-11-09 16:04:46,542 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:04:46,543 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:04:46,543 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:46,543 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-11-09 16:04:46,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:46,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [89786571] [2024-11-09 16:04:46,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:46,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:46,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,597 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:04:46,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,669 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-09 16:04:46,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:04:46,669 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [89786571] [2024-11-09 16:04:46,670 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [89786571] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:04:46,670 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:04:46,670 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:04:46,670 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [411268395] [2024-11-09 16:04:46,670 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:04:46,670 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:04:46,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:04:46,672 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 16:04:46,675 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-09 16:04:46,677 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-09 16:04:46,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:04:46,756 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-09 16:04:46,756 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-09 16:04:46,757 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:04:46,758 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-09 16:04:46,758 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-09 16:04:46,758 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-09 16:04:46,758 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-09 16:04:46,758 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:46,758 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:04:46,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-09 16:04:46,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 16:04:46,760 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-09 16:04:46,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-09 16:04:46,761 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:04:46,761 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 16:04:46,762 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:04:46,762 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 16:04:46,762 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-09 16:04:46,763 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:04:46,763 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:46,763 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:46,764 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:46,764 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-09 16:04:46,764 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-09 16:04:46,764 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-09 16:04:46,764 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:46,765 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-11-09 16:04:46,765 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:46,765 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1560042642] [2024-11-09 16:04:46,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:46,765 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:46,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,809 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:04:46,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,854 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-09 16:04:46,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:04:46,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1560042642] [2024-11-09 16:04:46,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1560042642] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:04:46,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1150305483] [2024-11-09 16:04:46,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:46,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:04:46,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:46,857 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-09 16:04:46,858 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-09 16:04:46,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:46,885 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:04:46,886 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:46,919 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-09 16:04:46,920 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:04:47,100 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-09 16:04:47,100 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1150305483] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:04:47,100 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:04:47,100 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-09 16:04:47,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1408709172] [2024-11-09 16:04:47,100 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:04:47,101 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:04:47,101 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:47,101 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-11-09 16:04:47,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:47,101 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1472496948] [2024-11-09 16:04:47,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:47,101 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:47,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:47,107 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:47,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:47,113 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:47,274 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:47,274 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:47,274 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:47,274 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:47,274 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:47,275 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,275 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:47,275 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:47,275 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-11-09 16:04:47,275 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:47,275 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:47,276 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,281 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,285 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,286 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,289 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,319 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:47,320 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:47,320 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,320 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:47,321 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-09 16:04:47,322 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-09 16:04:47,323 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:47,323 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:47,336 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:47,336 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-09 16:04:47,347 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-09 16:04:47,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:47,348 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-09 16:04:47,349 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-09 16:04:47,350 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:47,350 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:47,371 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-09 16:04:47,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,372 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:47,373 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-09 16:04:47,377 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-09 16:04:47,378 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:47,378 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:47,391 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:47,401 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-09 16:04:47,401 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:47,402 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:47,402 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:47,402 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:47,402 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:47,402 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,402 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:47,402 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:47,402 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-11-09 16:04:47,402 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:47,402 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:47,403 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,412 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,420 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,423 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,426 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:47,462 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:47,462 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:47,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:47,463 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-09 16:04:47,465 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-09 16:04:47,465 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-09 16:04:47,475 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:47,476 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:47,476 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:47,476 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:47,476 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:47,477 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:47,477 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:47,479 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:47,482 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:04:47,482 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:04:47,482 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:47,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:47,483 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-09 16:04:47,484 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-09 16:04:47,485 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:47,485 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:47,485 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:47,486 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-09 16:04:47,496 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-09 16:04:47,496 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:47,526 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:47,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:47,555 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:04:47,556 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:47,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:47,646 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:04:47,648 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:47,798 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-09 16:04:47,802 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-09 16:04:47,803 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-09 16:04:47,803 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-09 16:04:48,066 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-09 16:04:48,067 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-09 16:04:48,068 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-09 16:04:48,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-09 16:04:48,068 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-09 16:04:48,069 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:48,069 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-09 16:04:48,069 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:48,069 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-09 16:04:48,070 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:48,070 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-09 16:04:48,081 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-09 16:04:48,087 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-09 16:04:48,088 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-09 16:04:48,088 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-09 16:04:48,088 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-09 16:04:48,088 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:48,088 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-09 16:04:48,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-09 16:04:48,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-09 16:04:48,100 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-09 16:04:48,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-09 16:04:48,102 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-09 16:04:48,103 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:04:48,103 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 16:04:48,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-09 16:04:48,103 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-09 16:04:48,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:04:48,196 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-09 16:04:48,196 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-09 16:04:48,198 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-09 16:04:48,200 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-09 16:04:48,201 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-09 16:04:48,201 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-09 16:04:48,201 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-09 16:04:48,201 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:48,201 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-09 16:04:48,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-09 16:04:48,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-09 16:04:48,207 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-09 16:04:48,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-09 16:04:48,208 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-09 16:04:48,209 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:04:48,209 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-09 16:04:48,209 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 16:04:48,209 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-09 16:04:48,211 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-09 16:04:48,211 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:48,211 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:48,211 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:48,211 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:48,212 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-09 16:04:48,212 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-09 16:04:48,212 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:48,212 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2024-11-09 16:04:48,212 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:48,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [506662863] [2024-11-09 16:04:48,212 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:48,213 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:48,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:48,300 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-09 16:04:48,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:48,340 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:04:48,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:48,369 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:04:48,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:48,379 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-09 16:04:48,379 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:04:48,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [506662863] [2024-11-09 16:04:48,379 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [506662863] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:04:48,383 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1336883471] [2024-11-09 16:04:48,383 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:48,383 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:04:48,383 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:48,386 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-09 16:04:48,388 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-09 16:04:48,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:48,426 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:04:48,427 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:48,513 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-09 16:04:48,513 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:04:48,861 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-09 16:04:48,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1336883471] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:04:48,861 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:04:48,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-09 16:04:48,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423382896] [2024-11-09 16:04:48,861 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:04:48,861 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:04:48,862 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:48,862 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2024-11-09 16:04:48,862 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:48,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1925272633] [2024-11-09 16:04:48,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:48,862 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:48,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:48,869 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:48,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:48,875 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:48,996 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:48,996 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:48,996 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:48,996 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:48,997 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:48,997 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:48,997 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:48,997 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:48,997 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-11-09 16:04:48,997 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:48,997 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:48,997 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,000 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,007 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,009 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,011 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,055 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:49,055 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:49,058 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,058 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:49,059 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-09 16:04:49,061 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-09 16:04:49,062 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:49,062 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:49,084 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:49,084 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-09 16:04:49,095 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:49,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:49,097 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-09 16:04:49,099 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-09 16:04:49,100 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:49,100 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:49,122 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-09 16:04:49,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:49,124 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-09 16:04:49,125 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-09 16:04:49,126 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:49,126 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:49,137 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:49,150 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-09 16:04:49,150 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:49,150 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:49,150 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:49,151 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:49,151 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:49,151 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,151 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:49,151 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:49,151 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-11-09 16:04:49,151 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:49,151 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:49,152 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,154 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,158 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,162 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:49,191 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:49,191 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:49,191 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,191 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:49,193 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-09 16:04:49,194 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-09 16:04:49,195 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-09 16:04:49,204 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:49,204 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:49,204 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:49,204 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:49,204 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:49,205 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:49,205 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:49,207 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:49,217 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-09 16:04:49,218 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:49,219 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-09 16:04:49,220 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-09 16:04:49,221 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-09 16:04:49,230 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:49,230 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:49,231 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:49,231 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:49,231 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:49,231 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:49,231 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:49,236 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:49,239 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:04:49,239 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:04:49,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:49,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:49,241 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-09 16:04:49,242 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-09 16:04:49,242 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:49,242 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:49,243 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:49,243 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-09 16:04:49,256 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-09 16:04:49,257 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:49,265 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:49,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:49,296 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:04:49,321 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:49,346 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2024-11-09 16:04:49,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:49,513 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 16:04:49,514 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:49,580 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-09 16:04:49,581 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-09 16:04:49,581 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-09 16:04:49,729 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-09 16:04:49,730 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-09 16:04:49,730 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-09 16:04:49,731 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-09 16:04:49,731 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-09 16:04:49,731 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:49,731 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:04:49,740 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:49,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:49,772 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:04:49,773 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:49,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:49,926 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 16:04:49,927 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:49,986 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-09 16:04:49,987 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-09 16:04:49,987 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-09 16:04:50,122 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-09 16:04:50,123 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-09 16:04:50,123 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-09 16:04:50,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-11-09 16:04:50,124 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-09 16:04:50,124 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:50,124 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:04:50,132 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:50,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:50,161 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:04:50,162 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:50,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:50,290 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 16:04:50,291 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:50,343 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-09 16:04:50,344 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-09 16:04:50,344 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-09 16:04:50,511 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-09 16:04:50,512 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-09 16:04:50,513 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-09 16:04:50,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-11-09 16:04:50,513 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-09 16:04:50,514 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:50,514 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-11-09 16:04:50,514 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:50,514 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-11-09 16:04:50,515 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:50,515 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 808 states and 1112 transitions. [2024-11-09 16:04:50,524 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-11-09 16:04:50,537 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 808 states to 427 states and 634 transitions. [2024-11-09 16:04:50,540 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 166 [2024-11-09 16:04:50,540 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-11-09 16:04:50,541 INFO L73 IsDeterministic]: Start isDeterministic. Operand 427 states and 634 transitions. [2024-11-09 16:04:50,541 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:50,541 INFO L218 hiAutomatonCegarLoop]: Abstraction has 427 states and 634 transitions. [2024-11-09 16:04:50,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states and 634 transitions. [2024-11-09 16:04:50,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 352. [2024-11-09 16:04:50,563 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-09 16:04:50,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 479 transitions. [2024-11-09 16:04:50,565 INFO L240 hiAutomatonCegarLoop]: Abstraction has 352 states and 479 transitions. [2024-11-09 16:04:50,565 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:04:50,566 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-09 16:04:50,566 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-11-09 16:04:50,566 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-09 16:04:50,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:04:50,820 INFO L93 Difference]: Finished difference Result 707 states and 1054 transitions. [2024-11-09 16:04:50,820 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 707 states and 1054 transitions. [2024-11-09 16:04:50,831 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-09 16:04:50,847 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 707 states to 676 states and 1009 transitions. [2024-11-09 16:04:50,848 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 296 [2024-11-09 16:04:50,848 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 299 [2024-11-09 16:04:50,848 INFO L73 IsDeterministic]: Start isDeterministic. Operand 676 states and 1009 transitions. [2024-11-09 16:04:50,848 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:50,849 INFO L218 hiAutomatonCegarLoop]: Abstraction has 676 states and 1009 transitions. [2024-11-09 16:04:50,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 676 states and 1009 transitions. [2024-11-09 16:04:50,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 676 to 628. [2024-11-09 16:04:50,889 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-09 16:04:50,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 936 transitions. [2024-11-09 16:04:50,895 INFO L240 hiAutomatonCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-11-09 16:04:50,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-09 16:04:50,903 INFO L425 stractBuchiCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-11-09 16:04:50,904 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 16:04:50,904 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 628 states and 936 transitions. [2024-11-09 16:04:50,907 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-09 16:04:50,907 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:50,907 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:50,909 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:50,909 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:04:50,909 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-09 16:04:50,909 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-09 16:04:50,909 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:50,910 INFO L85 PathProgramCache]: Analyzing trace with hash 1729544275, now seen corresponding path program 1 times [2024-11-09 16:04:50,910 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:50,910 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1526718007] [2024-11-09 16:04:50,910 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:50,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:50,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:51,213 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-09 16:04:51,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:51,284 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-09 16:04:51,284 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:04:51,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1526718007] [2024-11-09 16:04:51,284 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1526718007] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:04:51,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1838134085] [2024-11-09 16:04:51,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:51,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:04:51,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,290 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-09 16:04:51,292 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-09 16:04:51,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:51,327 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 16:04:51,328 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:51,432 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-09 16:04:51,433 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:04:51,720 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-09 16:04:51,720 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1838134085] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:04:51,720 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:04:51,721 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2024-11-09 16:04:51,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1447863637] [2024-11-09 16:04:51,721 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:04:51,721 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:04:51,721 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:51,721 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-11-09 16:04:51,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:51,722 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [401074645] [2024-11-09 16:04:51,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:51,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:51,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,724 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:51,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,725 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:51,777 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:51,777 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:51,777 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:51,777 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:51,777 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:51,777 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,777 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:51,777 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:51,777 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-11-09 16:04:51,778 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:51,778 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:51,778 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,780 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,786 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,795 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,797 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,828 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:51,828 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:51,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,830 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-09 16:04:51,831 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-09 16:04:51,832 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,832 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,843 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:51,843 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-09 16:04:51,853 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-11-09 16:04:51,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,855 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-09 16:04:51,856 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-09 16:04:51,857 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,857 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,868 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:51,868 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:51,878 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-09 16:04:51,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,879 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-09 16:04:51,881 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-09 16:04:51,881 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,882 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,903 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-09 16:04:51,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,904 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-09 16:04:51,906 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-09 16:04:51,907 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:51,907 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,935 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:51,939 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-09 16:04:51,939 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:51,939 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:51,939 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:51,939 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:51,939 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:51,942 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,942 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:51,942 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:51,942 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-11-09 16:04:51,942 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:51,942 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:51,943 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,945 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,946 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,953 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,958 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,988 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:51,989 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:51,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,990 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-09 16:04:51,991 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-09 16:04:51,992 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-09 16:04:52,002 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:52,002 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:52,002 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:52,003 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:52,003 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:52,003 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:52,003 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:52,004 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:52,014 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:52,014 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,016 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-09 16:04:52,017 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-09 16:04:52,017 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-09 16:04:52,027 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:52,027 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:52,027 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:52,027 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:52,027 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:52,028 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:52,028 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:52,029 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:52,039 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-09 16:04:52,039 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,040 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,041 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-09 16:04:52,042 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-09 16:04:52,043 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-09 16:04:52,052 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:52,053 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:52,053 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:52,053 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:52,053 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:52,054 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:52,054 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:52,055 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:52,058 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:04:52,058 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:04:52,058 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,059 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,060 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-09 16:04:52,061 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-09 16:04:52,062 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:52,062 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:52,062 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:52,062 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-11-09 16:04:52,075 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-09 16:04:52,076 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:52,084 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,166 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,168 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,293 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,293 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,324 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-09 16:04:52,325 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-09 16:04:52,325 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-09 16:04:52,455 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-09 16:04:52,459 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-09 16:04:52,460 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-09 16:04:52,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-09 16:04:52,460 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-09 16:04:52,460 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:52,460 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:04:52,462 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-09 16:04:52,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,552 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,553 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,681 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,681 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,711 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-09 16:04:52,712 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-09 16:04:52,712 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-09 16:04:52,794 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-09 16:04:52,797 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-09 16:04:52,798 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-09 16:04:52,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-09 16:04:52,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-09 16:04:52,798 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:52,798 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:04:52,812 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,873 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,874 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,977 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,978 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:53,007 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-09 16:04:53,008 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-09 16:04:53,008 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-09 16:04:53,105 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-09 16:04:53,113 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-09 16:04:53,114 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-09 16:04:53,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-09 16:04:53,114 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-09 16:04:53,114 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:53,115 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-09 16:04:53,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:53,115 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-11-09 16:04:53,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:53,115 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1163 transitions. [2024-11-09 16:04:53,128 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-09 16:04:53,141 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 996 transitions. [2024-11-09 16:04:53,141 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2024-11-09 16:04:53,141 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2024-11-09 16:04:53,141 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 996 transitions. [2024-11-09 16:04:53,142 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:53,142 INFO L218 hiAutomatonCegarLoop]: Abstraction has 684 states and 996 transitions. [2024-11-09 16:04:53,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 996 transitions. [2024-11-09 16:04:53,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2024-11-09 16:04:53,172 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-09 16:04:53,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 960 transitions. [2024-11-09 16:04:53,179 INFO L240 hiAutomatonCegarLoop]: Abstraction has 654 states and 960 transitions. [2024-11-09 16:04:53,179 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:04:53,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 16:04:53,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-11-09 16:04:53,180 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-09 16:04:53,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:04:53,546 INFO L93 Difference]: Finished difference Result 781 states and 1180 transitions. [2024-11-09 16:04:53,547 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 781 states and 1180 transitions. [2024-11-09 16:04:53,556 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-09 16:04:53,574 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 781 states to 760 states and 1148 transitions. [2024-11-09 16:04:53,575 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 279 [2024-11-09 16:04:53,575 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 282 [2024-11-09 16:04:53,575 INFO L73 IsDeterministic]: Start isDeterministic. Operand 760 states and 1148 transitions. [2024-11-09 16:04:53,575 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:53,576 INFO L218 hiAutomatonCegarLoop]: Abstraction has 760 states and 1148 transitions. [2024-11-09 16:04:53,576 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states and 1148 transitions. [2024-11-09 16:04:53,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 702. [2024-11-09 16:04:53,603 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-09 16:04:53,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 702 states to 702 states and 1022 transitions. [2024-11-09 16:04:53,609 INFO L240 hiAutomatonCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-11-09 16:04:53,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-09 16:04:53,614 INFO L425 stractBuchiCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-11-09 16:04:53,614 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 16:04:53,614 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 702 states and 1022 transitions. [2024-11-09 16:04:53,617 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-09 16:04:53,617 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:53,617 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:53,623 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:53,624 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:04:53,624 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-09 16:04:53,624 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-09 16:04:53,624 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:53,624 INFO L85 PathProgramCache]: Analyzing trace with hash 1537328375, now seen corresponding path program 2 times [2024-11-09 16:04:53,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:53,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [246814944] [2024-11-09 16:04:53,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:53,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:53,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:54,011 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 16:04:54,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:54,018 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-09 16:04:54,019 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:04:54,019 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [246814944] [2024-11-09 16:04:54,019 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [246814944] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:04:54,019 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [866699297] [2024-11-09 16:04:54,019 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 16:04:54,019 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:04:54,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:54,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-09 16:04:54,026 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-09 16:04:54,061 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 16:04:54,061 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:04:54,062 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:04:54,084 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:54,160 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-09 16:04:54,161 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:04:54,315 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-09 16:04:54,316 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [866699297] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:04:54,316 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:04:54,316 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2024-11-09 16:04:54,316 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [927147729] [2024-11-09 16:04:54,316 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:04:54,316 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:04:54,317 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:54,317 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-11-09 16:04:54,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:54,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1728681813] [2024-11-09 16:04:54,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:54,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:54,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:54,319 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:54,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:54,320 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:54,410 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:54,410 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:54,410 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:54,410 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:54,410 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:54,410 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:54,410 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:54,410 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:54,411 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-11-09 16:04:54,411 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:54,411 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:54,411 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:54,414 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:54,415 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:54,423 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:54,492 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:54,492 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:54,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:54,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:54,494 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-09 16:04:54,495 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-09 16:04:54,495 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:54,495 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:54,507 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:54,507 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-09 16:04:54,517 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-09 16:04:54,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:54,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:54,519 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-09 16:04:54,523 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-09 16:04:54,524 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:54,524 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:54,536 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:54,536 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:54,546 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:54,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:54,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:54,548 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-09 16:04:54,548 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-09 16:04:54,549 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:54,549 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:54,578 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-09 16:04:54,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:54,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:54,579 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-09 16:04:54,580 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-09 16:04:54,582 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:54,582 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:55,780 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:55,786 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:55,786 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:55,786 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:55,786 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:55,786 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:55,787 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:55,787 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:55,787 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:55,787 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:55,787 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-11-09 16:04:55,787 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:55,787 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:55,787 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:55,789 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:55,790 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:55,795 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:55,827 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:55,827 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:55,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:55,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:55,829 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-09 16:04:55,830 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-09 16:04:55,831 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-09 16:04:55,841 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:55,841 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:55,845 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:55,845 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:55,845 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:55,846 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:55,846 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:55,850 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:55,860 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-09 16:04:55,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:55,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:55,862 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-09 16:04:55,864 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-09 16:04:55,865 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-09 16:04:55,874 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:55,874 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:55,874 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:55,874 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:55,874 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:55,875 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:55,875 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:55,876 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:55,888 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:55,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:55,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:55,890 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-09 16:04:55,891 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-09 16:04:55,892 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-09 16:04:55,902 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:55,902 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:55,902 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:55,902 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:55,902 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:55,903 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:55,903 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:55,906 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:55,908 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 16:04:55,908 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:04:55,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:55,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:55,911 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-09 16:04:55,912 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-09 16:04:55,912 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:55,912 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:55,912 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:55,912 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-11-09 16:04:55,924 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-09 16:04:55,926 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:55,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:56,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:56,041 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-09 16:04:56,042 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:56,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:56,127 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:56,127 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:56,151 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:04:56,153 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-09 16:04:56,153 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-09 16:04:56,189 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-09 16:04:56,189 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-09 16:04:56,190 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-09 16:04:56,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 16:04:56,190 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2024-11-09 16:04:56,190 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:56,190 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:04:56,198 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:56,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:56,256 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-09 16:04:56,258 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:56,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:56,346 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:56,347 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:56,368 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:04:56,370 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-09 16:04:56,370 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-09 16:04:56,435 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-09 16:04:56,435 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-09 16:04:56,435 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-09 16:04:56,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-09 16:04:56,436 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2024-11-09 16:04:56,436 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:56,436 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-11-09 16:04:56,436 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:56,436 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2024-11-09 16:04:56,436 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:56,436 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 944 states and 1356 transitions. [2024-11-09 16:04:56,443 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-11-09 16:04:56,448 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 944 states to 874 states and 1278 transitions. [2024-11-09 16:04:56,448 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2024-11-09 16:04:56,449 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 310 [2024-11-09 16:04:56,449 INFO L73 IsDeterministic]: Start isDeterministic. Operand 874 states and 1278 transitions. [2024-11-09 16:04:56,449 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:56,449 INFO L218 hiAutomatonCegarLoop]: Abstraction has 874 states and 1278 transitions. [2024-11-09 16:04:56,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 874 states and 1278 transitions. [2024-11-09 16:04:56,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 874 to 854. [2024-11-09 16:04:56,463 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-09 16:04:56,466 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1254 transitions. [2024-11-09 16:04:56,466 INFO L240 hiAutomatonCegarLoop]: Abstraction has 854 states and 1254 transitions. [2024-11-09 16:04:56,466 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:04:56,466 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 16:04:56,466 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2024-11-09 16:04:56,467 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-09 16:04:56,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:04:56,719 INFO L93 Difference]: Finished difference Result 471 states and 558 transitions. [2024-11-09 16:04:56,719 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 471 states and 558 transitions. [2024-11-09 16:04:56,725 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:04:56,725 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 471 states to 0 states and 0 transitions. [2024-11-09 16:04:56,725 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:04:56,725 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:04:56,725 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:04:56,725 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:04:56,725 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:04:56,725 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:04:56,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-09 16:04:56,726 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:04:56,726 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-09 16:04:56,726 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 16:04:56,726 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:04:56,726 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 16:04:56,739 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 04:04:56 BoogieIcfgContainer [2024-11-09 16:04:56,739 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 16:04:56,740 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 16:04:56,740 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 16:04:56,740 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 16:04:56,741 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:04:45" (3/4) ... [2024-11-09 16:04:56,742 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 16:04:56,743 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 16:04:56,743 INFO L158 Benchmark]: Toolchain (without parser) took 12276.25ms. Allocated memory was 199.2MB in the beginning and 283.1MB in the end (delta: 83.9MB). Free memory was 130.2MB in the beginning and 102.8MB in the end (delta: 27.4MB). Peak memory consumption was 112.1MB. Max. memory is 16.1GB. [2024-11-09 16:04:56,743 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 113.2MB. Free memory is still 76.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:04:56,744 INFO L158 Benchmark]: CACSL2BoogieTranslator took 343.77ms. Allocated memory is still 199.2MB. Free memory was 130.0MB in the beginning and 118.2MB in the end (delta: 11.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-09 16:04:56,744 INFO L158 Benchmark]: Boogie Procedure Inliner took 48.47ms. Allocated memory is still 199.2MB. Free memory was 118.2MB in the beginning and 115.8MB in the end (delta: 2.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:04:56,744 INFO L158 Benchmark]: Boogie Preprocessor took 45.98ms. Allocated memory is still 199.2MB. Free memory was 115.8MB in the beginning and 114.3MB in the end (delta: 1.6MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:04:56,744 INFO L158 Benchmark]: RCFGBuilder took 238.39ms. Allocated memory is still 199.2MB. Free memory was 114.3MB in the beginning and 166.4MB in the end (delta: -52.1MB). Peak memory consumption was 14.0MB. Max. memory is 16.1GB. [2024-11-09 16:04:56,748 INFO L158 Benchmark]: BuchiAutomizer took 11585.49ms. Allocated memory was 199.2MB in the beginning and 283.1MB in the end (delta: 83.9MB). Free memory was 166.4MB in the beginning and 103.9MB in the end (delta: 62.5MB). Peak memory consumption was 146.4MB. Max. memory is 16.1GB. [2024-11-09 16:04:56,748 INFO L158 Benchmark]: Witness Printer took 3.24ms. Allocated memory is still 283.1MB. Free memory was 103.9MB in the beginning and 102.8MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:04:56,749 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.15ms. Allocated memory is still 113.2MB. Free memory is still 76.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 343.77ms. Allocated memory is still 199.2MB. Free memory was 130.0MB in the beginning and 118.2MB in the end (delta: 11.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 48.47ms. Allocated memory is still 199.2MB. Free memory was 118.2MB in the beginning and 115.8MB in the end (delta: 2.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 45.98ms. Allocated memory is still 199.2MB. Free memory was 115.8MB in the beginning and 114.3MB in the end (delta: 1.6MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 238.39ms. Allocated memory is still 199.2MB. Free memory was 114.3MB in the beginning and 166.4MB in the end (delta: -52.1MB). Peak memory consumption was 14.0MB. Max. memory is 16.1GB. * BuchiAutomizer took 11585.49ms. Allocated memory was 199.2MB in the beginning and 283.1MB in the end (delta: 83.9MB). Free memory was 166.4MB in the beginning and 103.9MB in the end (delta: 62.5MB). Peak memory consumption was 146.4MB. Max. memory is 16.1GB. * Witness Printer took 3.24ms. Allocated memory is still 283.1MB. Free memory was 103.9MB in the beginning and 102.8MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 11.5s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 6.2s. Construction of modules took 0.9s. 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.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 571 mSDsluCounter, 658 SdHoareTripleChecker+Invalid, 0.9s 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: 31ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-09 16:04:56,769 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-09 16:04:56,973 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:57,173 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Ended with exit code 0 [2024-11-09 16:04:57,374 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-09 16:04:57,574 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:57,776 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE