./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.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 2199d5dae92fc703178378f6dd7dec10a5f129181c51bc9a88c002f6d4f76a67 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-13 17:42:03,799 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-13 17:42:03,857 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-13 17:42:03,860 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-13 17:42:03,861 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-13 17:42:03,886 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-13 17:42:03,886 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-13 17:42:03,887 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-13 17:42:03,887 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-13 17:42:03,888 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-13 17:42:03,889 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-13 17:42:03,890 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-13 17:42:03,890 INFO L153 SettingsManager]: * Use SBE=true [2024-10-13 17:42:03,890 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-13 17:42:03,890 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-13 17:42:03,890 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-13 17:42:03,891 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-13 17:42:03,891 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-13 17:42:03,894 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-13 17:42:03,894 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-13 17:42:03,894 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-13 17:42:03,895 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-13 17:42:03,895 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-13 17:42:03,895 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-13 17:42:03,895 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-13 17:42:03,895 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-13 17:42:03,896 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-13 17:42:03,896 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-13 17:42:03,896 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-13 17:42:03,896 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-13 17:42:03,896 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-13 17:42:03,896 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-13 17:42:03,897 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-13 17:42:03,897 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-13 17:42:03,897 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-13 17:42:03,897 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-13 17:42:03,897 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-13 17:42:03,897 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-13 17:42:03,898 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-13 17:42:03,898 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 -> 2199d5dae92fc703178378f6dd7dec10a5f129181c51bc9a88c002f6d4f76a67 [2024-10-13 17:42:04,102 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-13 17:42:04,127 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-13 17:42:04,131 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-13 17:42:04,132 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-13 17:42:04,132 INFO L274 PluginConnector]: CDTParser initialized [2024-10-13 17:42:04,133 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c [2024-10-13 17:42:05,434 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-13 17:42:05,583 INFO L384 CDTParser]: Found 1 translation units. [2024-10-13 17:42:05,584 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c [2024-10-13 17:42:05,590 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bcac34273/6e4f0cdbee584fd894d6bd16ec960bb7/FLAG5e569ae5a [2024-10-13 17:42:05,997 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bcac34273/6e4f0cdbee584fd894d6bd16ec960bb7 [2024-10-13 17:42:05,999 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-13 17:42:06,000 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-13 17:42:06,001 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-13 17:42:06,001 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-13 17:42:06,005 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-13 17:42:06,006 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:42:05" (1/1) ... [2024-10-13 17:42:06,007 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ae2dc25 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06, skipping insertion in model container [2024-10-13 17:42:06,007 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:42:05" (1/1) ... [2024-10-13 17:42:06,028 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-13 17:42:06,168 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:42:06,177 INFO L200 MainTranslator]: Completed pre-run [2024-10-13 17:42:06,187 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:42:06,200 INFO L204 MainTranslator]: Completed translation [2024-10-13 17:42:06,201 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06 WrapperNode [2024-10-13 17:42:06,201 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-13 17:42:06,202 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-13 17:42:06,202 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-13 17:42:06,202 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-13 17:42:06,207 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,212 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,224 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-10-13 17:42:06,225 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-13 17:42:06,225 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-13 17:42:06,225 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-13 17:42:06,226 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-13 17:42:06,247 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,247 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,248 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,261 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-13 17:42:06,261 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,261 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,263 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,265 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,265 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,266 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,267 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-13 17:42:06,267 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-13 17:42:06,267 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-13 17:42:06,267 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-13 17:42:06,268 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (1/1) ... [2024-10-13 17:42:06,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:06,292 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:06,308 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:06,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-10-13 17:42:06,356 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-13 17:42:06,356 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-13 17:42:06,356 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-13 17:42:06,356 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-13 17:42:06,357 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-10-13 17:42:06,357 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-10-13 17:42:06,412 INFO L238 CfgBuilder]: Building ICFG [2024-10-13 17:42:06,414 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-13 17:42:06,505 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-13 17:42:06,505 INFO L287 CfgBuilder]: Performing block encoding [2024-10-13 17:42:06,521 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-13 17:42:06,522 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-13 17:42:06,523 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:42:06 BoogieIcfgContainer [2024-10-13 17:42:06,523 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-13 17:42:06,524 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-13 17:42:06,525 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-13 17:42:06,528 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-13 17:42:06,529 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:42:06,529 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 13.10 05:42:05" (1/3) ... [2024-10-13 17:42:06,530 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@57e0be1b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:42:06, skipping insertion in model container [2024-10-13 17:42:06,530 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:42:06,531 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:42:06" (2/3) ... [2024-10-13 17:42:06,531 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@57e0be1b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:42:06, skipping insertion in model container [2024-10-13 17:42:06,531 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:42:06,531 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:42:06" (3/3) ... [2024-10-13 17:42:06,533 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_5-1.c [2024-10-13 17:42:06,586 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-13 17:42:06,586 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-13 17:42:06,586 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-13 17:42:06,586 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-13 17:42:06,587 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-13 17:42:06,587 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-13 17:42:06,588 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-13 17:42:06,588 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-13 17:42:06,592 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-13 17:42:06,609 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:06,610 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:06,610 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:06,615 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:42:06,615 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:42:06,616 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-13 17:42:06,616 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-13 17:42:06,619 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:06,619 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:06,619 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:06,620 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:42:06,620 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:42:06,627 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(11, 2);call #Ultimate.allocInit(12, 3); 9#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 := 5; 4#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 11#$Ultimate##0true [2024-10-13 17:42:06,628 INFO L747 eck$LassoCheckResult]: Loop: 11#$Ultimate##0true ~n := #in~n; 5#L8true assume !(~n < 1); 7#L10true assume !(1 == ~n); 13#L13true call #t~ret4 := fibo(~n - 1);< 11#$Ultimate##0true [2024-10-13 17:42:06,635 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:06,635 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-10-13 17:42:06,643 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:06,646 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [211953257] [2024-10-13 17:42:06,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:06,647 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:06,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:06,727 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:06,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:06,750 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:06,752 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:06,753 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-10-13 17:42:06,753 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:06,753 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [748959936] [2024-10-13 17:42:06,753 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:06,753 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:06,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:06,763 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:06,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:06,770 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:06,773 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:06,773 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-10-13 17:42:06,773 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:06,773 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1693056754] [2024-10-13 17:42:06,773 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:06,773 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:06,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:06,786 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:06,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:06,801 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:06,923 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:06,923 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:06,923 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:06,924 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:06,924 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:42:06,924 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:06,924 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:06,924 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:06,924 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2024-10-13 17:42:06,924 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:06,925 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:06,938 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:06,955 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:06,959 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:06,963 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:06,972 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:07,048 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:07,049 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:42:07,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,052 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,056 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,063 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:07,063 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:07,067 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-10-13 17:42:07,086 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:07,086 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:07,102 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-10-13 17:42:07,102 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,103 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,104 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,107 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-10-13 17:42:07,112 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:07,112 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:07,124 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:07,124 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:07,137 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:07,138 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,140 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,141 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-10-13 17:42:07,142 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:07,142 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:07,154 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:07,154 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:07,165 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-10-13 17:42:07,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,168 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,169 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-10-13 17:42:07,171 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:07,171 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:07,196 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-10-13 17:42:07,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,199 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,201 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-10-13 17:42:07,202 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:42:07,202 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:07,258 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:42:07,262 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-10-13 17:42:07,262 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:07,262 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:07,263 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:07,263 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:07,263 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:42:07,263 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,263 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:07,263 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:07,263 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2024-10-13 17:42:07,263 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:07,263 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:07,265 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:07,267 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:07,269 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:07,272 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:07,279 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:07,325 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:07,330 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:42:07,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,335 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-10-13 17:42:07,339 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:07,349 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:07,349 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:07,350 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:07,350 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:07,350 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:07,352 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:07,352 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:07,354 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:07,364 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-13 17:42:07,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,367 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,368 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-10-13 17:42:07,369 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:07,379 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:07,379 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:07,379 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:07,379 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:07,379 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:07,380 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:07,380 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:07,382 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:07,395 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-10-13 17:42:07,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,398 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-10-13 17:42:07,400 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:07,410 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:07,410 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:07,410 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:07,410 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:07,410 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:07,411 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:07,411 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:07,413 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:07,423 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-10-13 17:42:07,424 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,424 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,425 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,426 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-10-13 17:42:07,427 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:07,436 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:07,437 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:07,437 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:07,437 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:07,437 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:07,438 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:07,438 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:07,440 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:42:07,442 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:42:07,443 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:42:07,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:07,444 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:07,467 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:07,469 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-10-13 17:42:07,469 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:42:07,470 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:42:07,470 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:42:07,470 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-10-13 17:42:07,480 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:07,483 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:42:07,505 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:07,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:07,534 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-13 17:42:07,535 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:07,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:07,555 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:42:07,556 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:07,598 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:07,622 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-10-13 17:42:07,624 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-13 17:42:07,672 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-10-13 17:42:07,786 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 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 41 states and 54 transitions. Complement of second has 16 states. [2024-10-13 17:42:07,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:42:07,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-13 17:42:07,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-13 17:42:07,797 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-13 17:42:07,797 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:07,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-13 17:42:07,798 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:07,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-13 17:42:07,798 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:07,798 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-10-13 17:42:07,801 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:07,804 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-10-13 17:42:07,805 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-13 17:42:07,805 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-13 17:42:07,806 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-13 17:42:07,807 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:07,807 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-13 17:42:07,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-13 17:42:07,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-13 17:42:07,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:42:07,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-13 17:42:07,829 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:42:07,829 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:42:07,829 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-13 17:42:07,829 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-13 17:42:07,829 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:07,830 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:07,830 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:07,830 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:07,830 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:07,831 INFO L745 eck$LassoCheckResult]: Stem: 135#$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(11, 2);call #Ultimate.allocInit(12, 3); 136#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 := 5; 121#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 120#$Ultimate##0 ~n := #in~n; 122#L8 assume !(~n < 1); 134#L10 assume !(1 == ~n); 124#L13 call #t~ret4 := fibo(~n - 1);< 123#$Ultimate##0 ~n := #in~n; 125#L8 assume ~n < 1;#res := 0; 131#fiboFINAL assume true; 132#fiboEXIT >#35#return; 127#L13-1 [2024-10-13 17:42:07,831 INFO L747 eck$LassoCheckResult]: Loop: 127#L13-1 call #t~ret5 := fibo(~n - 2);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume !(~n < 1); 139#L10 assume !(1 == ~n); 126#L13 call #t~ret4 := fibo(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume ~n < 1;#res := 0; 130#fiboFINAL assume true; 137#fiboEXIT >#35#return; 127#L13-1 [2024-10-13 17:42:07,831 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:07,831 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-10-13 17:42:07,831 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:07,831 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1607939378] [2024-10-13 17:42:07,832 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:07,832 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:07,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:07,923 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:42:07,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:07,966 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:42:07,966 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:42:07,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1607939378] [2024-10-13 17:42:07,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1607939378] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:42:07,967 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:42:07,967 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:42:07,967 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [716866585] [2024-10-13 17:42:07,967 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:42:07,969 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:42:07,969 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:07,969 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-10-13 17:42:07,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:07,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [806958922] [2024-10-13 17:42:07,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:07,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:07,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:08,005 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:42:08,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:08,042 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:42:08,043 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:42:08,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [806958922] [2024-10-13 17:42:08,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [806958922] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:42:08,043 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:42:08,043 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:42:08,043 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1594241660] [2024-10-13 17:42:08,043 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:42:08,043 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:42:08,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:42:08,045 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-13 17:42:08,045 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-13 17:42:08,046 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:42:08,107 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:42:08,107 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-13 17:42:08,107 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-13 17:42:08,108 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:08,109 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-13 17:42:08,109 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-13 17:42:08,109 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-13 17:42:08,109 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-13 17:42:08,109 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:08,109 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:42:08,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-13 17:42:08,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-13 17:42:08,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-13 17:42:08,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-13 17:42:08,115 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:42:08,115 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-13 17:42:08,116 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:42:08,116 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-13 17:42:08,116 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-13 17:42:08,117 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:08,118 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:08,118 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:08,118 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:08,118 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:08,119 INFO L745 eck$LassoCheckResult]: Stem: 205#$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(11, 2);call #Ultimate.allocInit(12, 3); 206#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 := 5; 199#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 202#$Ultimate##0 ~n := #in~n; 197#L8 assume !(~n < 1); 208#L10 assume !(1 == ~n); 196#L13 call #t~ret4 := fibo(~n - 1);< 195#$Ultimate##0 ~n := #in~n; 198#L8 assume !(~n < 1); 214#L10 assume 1 == ~n;#res := 1; 213#fiboFINAL assume true; 211#fiboEXIT >#35#return; 192#L13-1 [2024-10-13 17:42:08,119 INFO L747 eck$LassoCheckResult]: Loop: 192#L13-1 call #t~ret5 := fibo(~n - 2);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume !(1 == ~n); 193#L13 call #t~ret4 := fibo(~n - 1);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume 1 == ~n;#res := 1; 209#fiboFINAL assume true; 210#fiboEXIT >#35#return; 192#L13-1 [2024-10-13 17:42:08,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:08,119 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-10-13 17:42:08,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:08,120 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2032247204] [2024-10-13 17:42:08,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:08,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:08,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:08,185 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:42:08,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:08,220 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:08,221 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:42:08,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2032247204] [2024-10-13 17:42:08,221 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2032247204] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:42:08,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [592179900] [2024-10-13 17:42:08,221 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:08,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:42:08,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,223 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,224 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-13 17:42:08,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:08,251 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:42:08,252 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:08,276 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:08,277 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:42:08,373 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:08,373 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [592179900] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:42:08,373 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:42:08,373 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-10-13 17:42:08,374 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1873331682] [2024-10-13 17:42:08,374 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:42:08,374 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:42:08,374 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:08,374 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-10-13 17:42:08,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:08,375 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1925717701] [2024-10-13 17:42:08,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:08,375 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:08,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:08,383 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:08,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:08,388 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:08,495 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:08,496 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:08,496 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:08,496 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:08,496 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:42:08,496 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,496 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:08,496 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:08,496 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2024-10-13 17:42:08,496 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:08,496 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:08,497 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,503 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,505 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,511 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,515 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,547 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:08,548 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:42:08,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,549 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,550 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-10-13 17:42:08,550 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:08,550 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:08,561 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:08,562 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#in~n=2} Honda state: {fibo_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:08,572 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-10-13 17:42:08,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,573 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,574 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-10-13 17:42:08,574 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:08,574 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:08,585 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:08,586 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:08,596 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:08,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,598 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,599 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-10-13 17:42:08,600 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:08,600 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:08,611 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:08,611 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:08,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:08,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,623 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,624 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-10-13 17:42:08,625 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:08,625 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:08,648 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:08,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,650 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,651 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-10-13 17:42:08,653 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:42:08,653 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:08,665 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:42:08,676 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:08,676 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:08,677 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:08,677 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:08,677 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:08,677 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:42:08,677 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,677 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:08,677 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:08,677 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2024-10-13 17:42:08,677 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:08,677 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:08,678 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,681 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,684 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,688 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,691 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:08,723 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:08,723 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:42:08,723 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,724 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,725 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-10-13 17:42:08,726 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:08,735 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:08,735 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:08,735 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:08,736 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:08,736 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:08,736 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:08,736 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:08,738 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:08,748 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-10-13 17:42:08,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,748 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,749 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,750 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-10-13 17:42:08,751 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:08,761 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:08,761 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:08,761 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:08,761 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:08,761 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:08,762 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:08,762 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:08,763 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:08,775 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-10-13 17:42:08,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,776 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,778 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-10-13 17:42:08,779 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:08,788 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:08,788 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:08,789 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:08,789 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:08,789 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:08,789 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:08,789 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:08,790 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:08,800 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-10-13 17:42:08,800 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,801 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,802 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-10-13 17:42:08,803 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:08,815 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:08,815 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:08,815 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:08,815 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:08,815 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:08,816 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:08,816 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:08,818 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:08,832 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-10-13 17:42:08,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,833 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,834 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-10-13 17:42:08,836 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:08,845 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:08,845 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:08,845 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:08,845 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:08,846 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:08,847 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:08,847 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:08,849 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:42:08,851 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:42:08,852 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:42:08,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:08,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:08,853 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:08,854 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-10-13 17:42:08,855 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:42:08,855 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:42:08,855 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:42:08,855 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-10-13 17:42:08,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:08,871 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:42:08,883 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:08,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:08,904 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:42:08,905 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:09,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:09,004 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-13 17:42:09,005 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:09,079 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:09,079 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-13 17:42:09,079 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-13 17:42:09,284 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:09,292 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 128 states and 178 transitions. Complement of second has 40 states. [2024-10-13 17:42:09,292 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-10-13 17:42:09,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-13 17:42:09,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-10-13 17:42:09,294 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-10-13 17:42:09,294 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:09,294 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-10-13 17:42:09,294 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:09,294 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-10-13 17:42:09,294 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:09,295 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-10-13 17:42:09,299 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-13 17:42:09,302 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-10-13 17:42:09,302 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-10-13 17:42:09,302 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-10-13 17:42:09,302 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-10-13 17:42:09,302 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:09,303 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-10-13 17:42:09,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-10-13 17:42:09,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-10-13 17:42:09,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (35), 18 states have call predecessors, (35), 19 states have call successors, (35) [2024-10-13 17:42:09,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-10-13 17:42:09,312 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-10-13 17:42:09,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:42:09,313 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-13 17:42:09,313 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-10-13 17:42:09,313 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-13 17:42:09,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:42:09,418 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-10-13 17:42:09,418 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-10-13 17:42:09,421 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-13 17:42:09,423 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-10-13 17:42:09,423 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-10-13 17:42:09,423 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-10-13 17:42:09,423 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-10-13 17:42:09,424 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:09,424 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-10-13 17:42:09,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-10-13 17:42:09,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-10-13 17:42:09,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (39), 20 states have call predecessors, (39), 22 states have call successors, (39) [2024-10-13 17:42:09,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-10-13 17:42:09,439 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-10-13 17:42:09,444 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-13 17:42:09,444 INFO L425 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-10-13 17:42:09,445 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-13 17:42:09,446 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-10-13 17:42:09,447 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-13 17:42:09,450 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:09,450 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:09,451 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:09,451 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-10-13 17:42:09,451 INFO L745 eck$LassoCheckResult]: Stem: 806#$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(11, 2);call #Ultimate.allocInit(12, 3); 807#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 := 5; 792#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 793#$Ultimate##0 ~n := #in~n; 809#L8 assume !(~n < 1); 810#L10 assume !(1 == ~n); 780#L13 call #t~ret4 := fibo(~n - 1);< 779#$Ultimate##0 ~n := #in~n; 781#L8 assume !(~n < 1); 816#L10 assume !(1 == ~n); 790#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 839#L8 assume !(~n < 1); 837#L10 assume 1 == ~n;#res := 1; 835#fiboFINAL assume true; 834#fiboEXIT >#35#return; 817#L13-1 call #t~ret5 := fibo(~n - 2);< 833#$Ultimate##0 ~n := #in~n; 879#L8 assume ~n < 1;#res := 0; 878#fiboFINAL assume true; 877#fiboEXIT >#37#return; 875#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 872#fiboFINAL assume true; 864#fiboEXIT >#35#return; 813#L13-1 [2024-10-13 17:42:09,451 INFO L747 eck$LassoCheckResult]: Loop: 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#35#return; 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#37#return; 862#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 871#fiboFINAL assume true; 865#fiboEXIT >#35#return; 813#L13-1 [2024-10-13 17:42:09,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:09,452 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-10-13 17:42:09,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:09,452 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [185222488] [2024-10-13 17:42:09,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:09,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:09,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:09,474 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:09,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:09,490 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:09,491 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:09,492 INFO L85 PathProgramCache]: Analyzing trace with hash -1138642743, now seen corresponding path program 1 times [2024-10-13 17:42:09,492 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:09,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [810212162] [2024-10-13 17:42:09,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:09,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:09,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:09,522 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:42:09,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:09,544 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:42:09,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:09,563 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:42:09,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:09,585 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-10-13 17:42:09,585 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:42:09,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [810212162] [2024-10-13 17:42:09,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [810212162] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:42:09,586 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [20116282] [2024-10-13 17:42:09,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:09,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:42:09,586 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:09,587 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:42:09,588 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2024-10-13 17:42:09,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:09,614 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:42:09,615 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:09,639 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-10-13 17:42:09,639 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:42:09,767 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-10-13 17:42:09,770 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [20116282] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:42:09,770 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:42:09,770 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-10-13 17:42:09,771 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [508085463] [2024-10-13 17:42:09,771 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:42:09,771 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:42:09,771 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:42:09,771 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-13 17:42:09,771 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-10-13 17:42:09,772 INFO L87 Difference]: Start difference. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 2 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-13 17:42:09,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:42:09,869 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-10-13 17:42:09,869 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-10-13 17:42:09,871 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:09,872 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-10-13 17:42:09,872 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-10-13 17:42:09,872 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-10-13 17:42:09,872 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-10-13 17:42:09,872 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:09,872 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-10-13 17:42:09,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-10-13 17:42:09,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-10-13 17:42:09,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2024-10-13 17:42:09,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-10-13 17:42:09,883 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-10-13 17:42:09,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-13 17:42:09,884 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-10-13 17:42:09,884 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-13 17:42:09,884 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-10-13 17:42:09,885 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:42:09,885 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:09,885 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:09,886 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:09,886 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-13 17:42:09,886 INFO L745 eck$LassoCheckResult]: Stem: 1144#$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(11, 2);call #Ultimate.allocInit(12, 3); 1145#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 := 5; 1138#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1139#$Ultimate##0 ~n := #in~n; 1154#L8 assume !(~n < 1); 1153#L10 assume !(1 == ~n); 1126#L13 call #t~ret4 := fibo(~n - 1);< 1125#$Ultimate##0 ~n := #in~n; 1127#L8 assume !(~n < 1); 1147#L10 assume !(1 == ~n); 1131#L13 call #t~ret4 := fibo(~n - 1);< 1132#$Ultimate##0 ~n := #in~n; 1152#L8 assume !(~n < 1); 1169#L10 assume !(1 == ~n); 1142#L13 call #t~ret4 := fibo(~n - 1);< 1132#$Ultimate##0 ~n := #in~n; 1152#L8 assume !(~n < 1); 1169#L10 assume !(1 == ~n); 1142#L13 call #t~ret4 := fibo(~n - 1);< 1132#$Ultimate##0 ~n := #in~n; 1151#L8 assume !(~n < 1); 1148#L10 assume 1 == ~n;#res := 1; 1149#fiboFINAL assume true; 1141#fiboEXIT >#35#return; 1143#L13-1 call #t~ret5 := fibo(~n - 2);< 1168#$Ultimate##0 ~n := #in~n; 1175#L8 assume ~n < 1;#res := 0; 1173#fiboFINAL assume true; 1167#fiboEXIT >#37#return; 1165#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1164#fiboFINAL assume true; 1161#fiboEXIT >#35#return; 1134#L13-1 [2024-10-13 17:42:09,886 INFO L747 eck$LassoCheckResult]: Loop: 1134#L13-1 call #t~ret5 := fibo(~n - 2);< 1130#$Ultimate##0 ~n := #in~n; 1172#L8 assume !(~n < 1); 1170#L10 assume !(1 == ~n); 1136#L13 call #t~ret4 := fibo(~n - 1);< 1130#$Ultimate##0 ~n := #in~n; 1172#L8 assume !(~n < 1); 1170#L10 assume !(1 == ~n); 1136#L13 call #t~ret4 := fibo(~n - 1);< 1130#$Ultimate##0 ~n := #in~n; 1172#L8 assume !(~n < 1); 1170#L10 assume 1 == ~n;#res := 1; 1171#fiboFINAL assume true; 1166#fiboEXIT >#35#return; 1123#L13-1 call #t~ret5 := fibo(~n - 2);< 1122#$Ultimate##0 ~n := #in~n; 1124#L8 assume ~n < 1;#res := 0; 1146#fiboFINAL assume true; 1174#fiboEXIT >#37#return; 1133#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1137#fiboFINAL assume true; 1140#fiboEXIT >#35#return; 1134#L13-1 [2024-10-13 17:42:09,887 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:09,887 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 2 times [2024-10-13 17:42:09,887 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:09,887 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1423480707] [2024-10-13 17:42:09,887 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:09,887 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:09,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:09,900 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:09,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:09,914 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:09,915 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:09,915 INFO L85 PathProgramCache]: Analyzing trace with hash -2000232554, now seen corresponding path program 1 times [2024-10-13 17:42:09,915 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:09,915 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1827803258] [2024-10-13 17:42:09,915 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:09,915 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:09,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:09,919 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:09,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:09,923 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:09,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:09,923 INFO L85 PathProgramCache]: Analyzing trace with hash -443608101, now seen corresponding path program 3 times [2024-10-13 17:42:09,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:09,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [437586705] [2024-10-13 17:42:09,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:09,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:09,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,071 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-13 17:42:10,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,079 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:42:10,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,082 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:42:10,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,084 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-13 17:42:10,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,091 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:42:10,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,093 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:42:10,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:10,095 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 34 proven. 64 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-10-13 17:42:10,095 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:42:10,096 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [437586705] [2024-10-13 17:42:10,096 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [437586705] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:42:10,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [747516815] [2024-10-13 17:42:10,097 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-13 17:42:10,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:42:10,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:10,099 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:42:10,100 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-10-13 17:42:10,143 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-10-13 17:42:10,143 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:42:10,144 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:42:10,145 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:10,223 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 63 proven. 69 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-10-13 17:42:10,223 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:42:10,464 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 63 proven. 70 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2024-10-13 17:42:10,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [747516815] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:42:10,465 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:42:10,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 14] total 22 [2024-10-13 17:42:10,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1395167939] [2024-10-13 17:42:10,465 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:42:10,673 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:10,673 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:10,673 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:10,673 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:10,673 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:42:10,673 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:10,673 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:10,673 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:10,673 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration5_Loop [2024-10-13 17:42:10,673 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:10,673 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:10,674 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:10,680 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:10,682 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:10,686 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:10,720 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:10,720 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:42:10,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:10,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:10,722 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:10,724 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-10-13 17:42:10,724 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:10,724 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:10,753 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:10,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:10,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:10,755 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:10,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-10-13 17:42:10,757 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:42:10,757 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:11,232 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:42:11,236 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:11,237 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:11,237 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:11,237 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:11,237 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:11,237 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:42:11,237 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:11,237 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:11,237 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:11,237 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration5_Loop [2024-10-13 17:42:11,237 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:11,237 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:11,238 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:11,241 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:11,242 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:11,248 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:11,286 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:11,286 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:42:11,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:11,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:11,287 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:11,288 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-10-13 17:42:11,289 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:11,299 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:11,299 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:11,299 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:11,299 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:11,299 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:11,300 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:11,300 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:11,301 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:11,311 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-10-13 17:42:11,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:11,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:11,312 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:11,313 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-10-13 17:42:11,314 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:11,324 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:11,325 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:11,325 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:11,325 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:11,325 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:11,325 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:11,325 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:11,326 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:11,336 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:11,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:11,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:11,338 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:11,339 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-10-13 17:42:11,339 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:11,349 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:11,349 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:11,349 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:11,349 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:11,349 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:11,350 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:11,350 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:11,352 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:42:11,355 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:42:11,355 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:42:11,355 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:11,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:11,357 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:11,357 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-10-13 17:42:11,358 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:42:11,358 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:42:11,358 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:42:11,358 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-10-13 17:42:11,368 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:11,369 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:42:11,381 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:11,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:11,411 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:42:11,412 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:11,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:11,586 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:42:11,587 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:11,692 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:42:11,693 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-10-13 17:42:11,693 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-13 17:42:11,767 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-10-13 17:42:11,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:42:11,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-13 17:42:11,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-10-13 17:42:11,770 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-10-13 17:42:11,770 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:11,770 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:42:11,778 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:11,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:11,811 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:42:11,812 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:11,970 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-10-13 17:42:12,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:12,010 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:42:12,011 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:12,120 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:42:12,121 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-10-13 17:42:12,121 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-13 17:42:12,204 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-10-13 17:42:12,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:42:12,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-13 17:42:12,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-10-13 17:42:12,206 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-10-13 17:42:12,206 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:12,206 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:42:12,214 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:12,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:12,245 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-13 17:42:12,247 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:12,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:12,394 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:42:12,395 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:12,500 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:42:12,500 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-10-13 17:42:12,501 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-13 17:42:12,697 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 408 states and 526 transitions. Complement of second has 132 states. [2024-10-13 17:42:12,698 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-10-13 17:42:12,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-13 17:42:12,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-10-13 17:42:12,699 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-10-13 17:42:12,700 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:12,700 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-10-13 17:42:12,703 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:12,703 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-10-13 17:42:12,704 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:12,704 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-10-13 17:42:12,711 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:42:12,714 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-10-13 17:42:12,715 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-10-13 17:42:12,715 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-10-13 17:42:12,715 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-10-13 17:42:12,716 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:12,716 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-10-13 17:42:12,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-10-13 17:42:12,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-10-13 17:42:12,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 115 states have (on average 1.1391304347826088) internal successors, (131), 122 states have internal predecessors, (131), 43 states have call successors, (48), 25 states have call predecessors, (48), 29 states have return successors, (67), 39 states have call predecessors, (67), 39 states have call successors, (67) [2024-10-13 17:42:12,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-10-13 17:42:12,728 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-10-13 17:42:12,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:42:12,728 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-13 17:42:12,729 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=376, Unknown=0, NotChecked=0, Total=462 [2024-10-13 17:42:12,729 INFO L87 Difference]: Start difference. First operand 187 states and 246 transitions. Second operand has 22 states, 19 states have (on average 2.263157894736842) internal successors, (43), 16 states have internal predecessors, (43), 13 states have call successors, (17), 7 states have call predecessors, (17), 3 states have return successors, (10), 5 states have call predecessors, (10), 9 states have call successors, (10) [2024-10-13 17:42:13,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:42:13,024 INFO L93 Difference]: Finished difference Result 136 states and 141 transitions. [2024-10-13 17:42:13,025 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 136 states and 141 transitions. [2024-10-13 17:42:13,026 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:42:13,026 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 136 states to 0 states and 0 transitions. [2024-10-13 17:42:13,026 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-13 17:42:13,026 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-13 17:42:13,026 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-13 17:42:13,026 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-13 17:42:13,026 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,026 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,027 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-10-13 17:42:13,028 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,028 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-13 17:42:13,028 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-13 17:42:13,028 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:42:13,028 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-13 17:42:13,037 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 13.10 05:42:13 BoogieIcfgContainer [2024-10-13 17:42:13,037 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-13 17:42:13,037 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-13 17:42:13,038 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-13 17:42:13,038 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-13 17:42:13,038 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:42:06" (3/4) ... [2024-10-13 17:42:13,040 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-13 17:42:13,040 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-13 17:42:13,041 INFO L158 Benchmark]: Toolchain (without parser) took 7041.20ms. Allocated memory was 146.8MB in the beginning and 243.3MB in the end (delta: 96.5MB). Free memory was 73.8MB in the beginning and 95.8MB in the end (delta: -22.0MB). Peak memory consumption was 75.9MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,041 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 146.8MB. Free memory is still 95.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:42:13,041 INFO L158 Benchmark]: CACSL2BoogieTranslator took 200.36ms. Allocated memory is still 146.8MB. Free memory was 73.7MB in the beginning and 62.3MB in the end (delta: 11.4MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,041 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.34ms. Allocated memory is still 146.8MB. Free memory was 62.1MB in the beginning and 60.7MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:42:13,043 INFO L158 Benchmark]: Boogie Preprocessor took 41.41ms. Allocated memory is still 146.8MB. Free memory was 60.7MB in the beginning and 115.9MB in the end (delta: -55.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,044 INFO L158 Benchmark]: RCFGBuilder took 255.55ms. Allocated memory was 146.8MB in the beginning and 201.3MB in the end (delta: 54.5MB). Free memory was 115.8MB in the beginning and 163.9MB in the end (delta: -48.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,044 INFO L158 Benchmark]: BuchiAutomizer took 6513.55ms. Allocated memory was 201.3MB in the beginning and 243.3MB in the end (delta: 41.9MB). Free memory was 163.9MB in the beginning and 95.8MB in the end (delta: 68.1MB). Peak memory consumption was 110.1MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,044 INFO L158 Benchmark]: Witness Printer took 3.02ms. Allocated memory is still 243.3MB. Free memory is still 95.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:42:13,045 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 146.8MB. Free memory is still 95.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 200.36ms. Allocated memory is still 146.8MB. Free memory was 73.7MB in the beginning and 62.3MB in the end (delta: 11.4MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.34ms. Allocated memory is still 146.8MB. Free memory was 62.1MB in the beginning and 60.7MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 41.41ms. Allocated memory is still 146.8MB. Free memory was 60.7MB in the beginning and 115.9MB in the end (delta: -55.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 255.55ms. Allocated memory was 146.8MB in the beginning and 201.3MB in the end (delta: 54.5MB). Free memory was 115.8MB in the beginning and 163.9MB in the end (delta: -48.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 6513.55ms. Allocated memory was 201.3MB in the beginning and 243.3MB in the end (delta: 41.9MB). Free memory was 163.9MB in the beginning and 95.8MB in the end (delta: 68.1MB). Peak memory consumption was 110.1MB. Max. memory is 16.1GB. * Witness Printer took 3.02ms. Allocated memory is still 243.3MB. Free memory is still 95.8MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 7 terminating modules (4 trivial, 2 deterministic, 1 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 10 locations. One nondeterministic module has affine ranking function n and consists of 11 locations. 4 modules have a trivial ranking function, the largest among these consists of 22 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 6.4s and 6 iterations. TraceHistogramMax:6. Analysis of lassos took 3.6s. Construction of modules took 0.4s. Büchi inclusion checks took 2.1s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 94 StatesRemovedByMinimization, 4 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 1, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 243 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 228 mSDsluCounter, 381 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 253 mSDsCounter, 151 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 766 IncrementalHoareTripleChecker+Invalid, 917 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 151 mSolverCounterUnsat, 128 mSDtfsCounter, 766 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI1 SFLT1 conc0 concLT1 SILN0 SILU0 SILI1 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital17 mio100 ax100 hnf100 lsp81 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq180 hnf92 smp80 dnf100 smp100 tf111 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 23ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 6 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 3 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.7s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-13 17:42:13,069 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Ended with exit code 0 [2024-10-13 17:42:13,270 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Ended with exit code 0 [2024-10-13 17:42:13,472 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-13 17:42:13,671 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE