./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_5-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-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-?-c7c6ca5-m [2024-11-09 16:05:28,995 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 16:05:29,055 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-09 16:05:29,060 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 16:05:29,061 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 16:05:29,101 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 16:05:29,102 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 16:05:29,102 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 16:05:29,103 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 16:05:29,103 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 16:05:29,104 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 16:05:29,104 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 16:05:29,105 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 16:05:29,105 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 16:05:29,105 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 16:05:29,106 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 16:05:29,106 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 16:05:29,107 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 16:05:29,107 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 16:05:29,107 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 16:05:29,108 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 16:05:29,108 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 16:05:29,109 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 16:05:29,109 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 16:05:29,110 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 16:05:29,110 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 16:05:29,110 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 16:05:29,110 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 16:05:29,111 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 16:05:29,111 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 16:05:29,111 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 16:05:29,112 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 16:05:29,112 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 16:05:29,112 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 16:05:29,113 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 16:05:29,113 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 16:05:29,113 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 16:05:29,113 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 16:05:29,114 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 16:05:29,114 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-11-09 16:05:29,399 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 16:05:29,423 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 16:05:29,426 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 16:05:29,428 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 16:05:29,429 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 16:05:29,430 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_5-1.c [2024-11-09 16:05:30,974 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 16:05:31,154 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 16:05:31,154 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c [2024-11-09 16:05:31,161 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c5e46e337/67057432ca0c4b9f80e60a315143889e/FLAGf86b4a525 [2024-11-09 16:05:31,173 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c5e46e337/67057432ca0c4b9f80e60a315143889e [2024-11-09 16:05:31,176 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 16:05:31,177 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 16:05:31,179 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 16:05:31,179 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 16:05:31,183 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 16:05:31,183 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,184 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1af3fb2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31, skipping insertion in model container [2024-11-09 16:05:31,184 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,204 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 16:05:31,388 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:05:31,405 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 16:05:31,420 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:05:31,439 INFO L204 MainTranslator]: Completed translation [2024-11-09 16:05:31,439 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31 WrapperNode [2024-11-09 16:05:31,440 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 16:05:31,441 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 16:05:31,441 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 16:05:31,441 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 16:05:31,448 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,455 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,472 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-09 16:05:31,473 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 16:05:31,473 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 16:05:31,474 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 16:05:31,474 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 16:05:31,484 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,485 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,486 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,498 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 16:05:31,499 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,499 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,502 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,503 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,504 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,505 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,507 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 16:05:31,507 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 16:05:31,508 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 16:05:31,508 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 16:05:31,508 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,515 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:31,532 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:31,546 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:31,550 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-09 16:05:31,598 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 16:05:31,601 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 16:05:31,601 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 16:05:31,601 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 16:05:31,601 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-09 16:05:31,602 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-09 16:05:31,654 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 16:05:31,656 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 16:05:31,789 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 16:05:31,790 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 16:05:31,799 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 16:05:31,799 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 16:05:31,800 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:31 BoogieIcfgContainer [2024-11-09 16:05:31,800 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 16:05:31,801 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 16:05:31,801 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 16:05:31,804 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 16:05:31,805 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:31,805 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 04:05:31" (1/3) ... [2024-11-09 16:05:31,806 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@25f20fe5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:05:31, skipping insertion in model container [2024-11-09 16:05:31,806 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:31,806 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31" (2/3) ... [2024-11-09 16:05:31,806 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@25f20fe5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:05:31, skipping insertion in model container [2024-11-09 16:05:31,806 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:31,806 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:31" (3/3) ... [2024-11-09 16:05:31,808 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_5-1.c [2024-11-09 16:05:31,868 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 16:05:31,869 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 16:05:31,869 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 16:05:31,869 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 16:05:31,869 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 16:05:31,869 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 16:05:31,869 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 16:05:31,870 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 16:05:31,875 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-11-09 16:05:31,892 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:31,892 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:31,892 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:31,896 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:05:31,896 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:31,897 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 16:05:31,897 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-11-09 16:05:31,899 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:31,899 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:31,899 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:31,899 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:05:31,899 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:31,905 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-11-09 16:05:31,905 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-11-09 16:05:31,911 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:31,911 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-11-09 16:05:31,919 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:31,920 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1072978123] [2024-11-09 16:05:31,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:31,921 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:32,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,004 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:32,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,043 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:32,046 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:32,048 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-11-09 16:05:32,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:32,049 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1157531780] [2024-11-09 16:05:32,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:32,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:32,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,060 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:32,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,066 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:32,068 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:32,068 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-11-09 16:05:32,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:32,068 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1338438327] [2024-11-09 16:05:32,068 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:32,069 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:32,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,084 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:32,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,096 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:32,243 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:32,244 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:32,244 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:32,245 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:32,245 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:32,245 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,245 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:32,245 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:32,245 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2024-11-09 16:05:32,245 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:32,246 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:32,261 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,270 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,274 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,281 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,291 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,373 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:32,374 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:32,376 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,377 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,379 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,380 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-09 16:05:32,381 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:32,382 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:32,399 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:32,399 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-11-09 16:05:32,416 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-09 16:05:32,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,420 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,422 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-09 16:05:32,423 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:32,423 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:32,436 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:32,436 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:32,447 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-09 16:05:32,448 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,450 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,452 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-09 16:05:32,454 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:32,454 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:32,469 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:32,469 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:32,483 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-09 16:05:32,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,484 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,485 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-09 16:05:32,486 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:32,486 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:32,509 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-09 16:05:32,510 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,510 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,511 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,512 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-09 16:05:32,513 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:32,513 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:32,585 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:32,590 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:32,590 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:32,590 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:32,591 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:32,591 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:32,591 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:32,591 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,591 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:32,591 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:32,591 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2024-11-09 16:05:32,591 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:32,591 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:32,592 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,595 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,602 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,607 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,621 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,678 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:32,684 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:32,685 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,685 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,687 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,689 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-09 16:05:32,691 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:32,705 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:32,705 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:32,706 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:32,706 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:32,706 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:32,708 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:32,709 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:32,713 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:32,728 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-09 16:05:32,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,729 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-09 16:05:32,731 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:32,742 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:32,742 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:32,742 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:32,742 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:32,742 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:32,743 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:32,743 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:32,745 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:32,756 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:32,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,757 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,758 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-09 16:05:32,759 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:32,769 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:32,769 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:32,769 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:32,770 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:32,770 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:32,770 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:32,770 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:32,774 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:32,785 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:32,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,787 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,788 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-09 16:05:32,789 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:32,799 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:32,799 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:32,799 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:32,799 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:32,799 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:32,800 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:32,801 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:32,805 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:32,809 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:32,809 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:32,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,832 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,833 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-09 16:05:32,833 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:32,833 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:32,833 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:32,834 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-09 16:05:32,845 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-11-09 16:05:32,848 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:32,873 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:32,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:32,906 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 16:05:32,907 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:32,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:32,930 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:32,931 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:32,993 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:33,025 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-09 16:05:33,028 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-11-09 16:05:33,140 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-11-09 16:05:33,144 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:33,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:05:33,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-09 16:05:33,152 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-09 16:05:33,153 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:33,153 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-09 16:05:33,153 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:33,153 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-09 16:05:33,153 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:33,154 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-09 16:05:33,158 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:33,165 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-09 16:05:33,166 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-09 16:05:33,166 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-09 16:05:33,166 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-09 16:05:33,167 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:33,168 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-09 16:05:33,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-09 16:05:33,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-09 16:05:33,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:33,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-09 16:05:33,192 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:05:33,192 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:05:33,192 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 16:05:33,192 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-09 16:05:33,193 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:33,193 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:33,193 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:33,194 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:33,194 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:33,195 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-11-09 16:05:33,195 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-11-09 16:05:33,195 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,196 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-11-09 16:05:33,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:33,196 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1300046290] [2024-11-09 16:05:33,196 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,196 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:33,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,332 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:33,342 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:05:33,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,405 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 16:05:33,405 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:33,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1300046290] [2024-11-09 16:05:33,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1300046290] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:33,406 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:33,406 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:05:33,407 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [774686208] [2024-11-09 16:05:33,410 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:33,412 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:33,413 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,413 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-11-09 16:05:33,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:33,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [18962843] [2024-11-09 16:05:33,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,414 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:33,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,473 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:33,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,518 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 16:05:33,519 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:33,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [18962843] [2024-11-09 16:05:33,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [18962843] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:33,519 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:33,519 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:05:33,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1517107522] [2024-11-09 16:05:33,519 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:33,520 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:33,520 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:33,522 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 16:05:33,522 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-09 16:05:33,523 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:33,601 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:33,604 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-09 16:05:33,604 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-09 16:05:33,606 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:33,607 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-09 16:05:33,607 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-09 16:05:33,607 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-09 16:05:33,607 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-09 16:05:33,609 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:33,609 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:33,609 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-09 16:05:33,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 16:05:33,612 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-09 16:05:33,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-09 16:05:33,614 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:33,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 16:05:33,615 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:33,615 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 16:05:33,616 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-09 16:05:33,616 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:33,619 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:33,619 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:33,620 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:33,620 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:33,620 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-11-09 16:05:33,620 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-11-09 16:05:33,621 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,621 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-11-09 16:05:33,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:33,621 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1264962889] [2024-11-09 16:05:33,621 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,622 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:33,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,706 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:05:33,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,755 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:33,755 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:33,756 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1264962889] [2024-11-09 16:05:33,756 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1264962889] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:33,756 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [638686277] [2024-11-09 16:05:33,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:33,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,759 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 16:05:33,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,800 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:33,801 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:33,839 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:33,839 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:33,959 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:33,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [638686277] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:33,960 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:33,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-09 16:05:33,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1302315877] [2024-11-09 16:05:33,960 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:33,960 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:33,961 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,961 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-11-09 16:05:33,961 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:33,961 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2111990121] [2024-11-09 16:05:33,961 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,961 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:33,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:33,972 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:33,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:33,979 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:34,103 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:34,104 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:34,104 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:34,104 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:34,104 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:34,104 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,104 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:34,104 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:34,104 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2024-11-09 16:05:34,105 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:34,105 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:34,105 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,109 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,111 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,115 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,121 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,164 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:34,164 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:34,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,165 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-09 16:05:34,167 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,167 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,179 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:34,179 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-11-09 16:05:34,190 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-09 16:05:34,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,191 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,192 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-09 16:05:34,193 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,193 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,205 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:34,205 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:34,221 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-09 16:05:34,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,223 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,224 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-09 16:05:34,226 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,226 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,244 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:34,244 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-11-09 16:05:34,259 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-09 16:05:34,261 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,261 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,262 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,265 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-09 16:05:34,266 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,266 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,295 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,296 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,297 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,299 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-09 16:05:34,300 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:34,300 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,316 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:34,331 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-09 16:05:34,332 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:34,332 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:34,332 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:34,332 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:34,332 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:34,332 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,332 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:34,332 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:34,332 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2024-11-09 16:05:34,332 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:34,332 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:34,333 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,339 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,342 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,344 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,347 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,394 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:34,395 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:34,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,397 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-11-09 16:05:34,398 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-11-09 16:05:34,400 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,411 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,411 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,411 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,411 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,411 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,412 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,412 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,414 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,424 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,426 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,427 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-09 16:05:34,428 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,438 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,438 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,438 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,438 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,438 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,439 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,439 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,440 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,451 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-09 16:05:34,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,453 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,455 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-09 16:05:34,455 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,465 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,465 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,465 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,465 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,465 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,466 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,466 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,467 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,478 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,478 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,478 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,479 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,481 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-11-09 16:05:34,484 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,494 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,494 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,494 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,494 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,494 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,495 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,495 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,496 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,506 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,508 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,509 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-09 16:05:34,511 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,521 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,521 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,521 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,521 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,521 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,522 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,522 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,524 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:34,527 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:34,527 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:34,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,529 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,531 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-09 16:05:34,531 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:34,531 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:34,531 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:34,531 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-09 16:05:34,543 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-11-09 16:05:34,545 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:34,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:34,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,579 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:34,581 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:34,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,662 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 16:05:34,663 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:34,784 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:34,785 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,785 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-09 16:05:34,786 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-11-09 16:05:35,032 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-11-09 16:05:35,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:35,033 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-11-09 16:05:35,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-09 16:05:35,034 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-11-09 16:05:35,035 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:35,035 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-11-09 16:05:35,035 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:35,035 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-11-09 16:05:35,036 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:35,036 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-11-09 16:05:35,044 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:35,048 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-11-09 16:05:35,048 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-11-09 16:05:35,048 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-11-09 16:05:35,049 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-11-09 16:05:35,049 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:35,049 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-11-09 16:05:35,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-11-09 16:05:35,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-11-09 16:05:35,060 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-11-09 16:05:35,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-11-09 16:05:35,062 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-11-09 16:05:35,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:35,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 16:05:35,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-09 16:05:35,063 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-11-09 16:05:35,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:35,206 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-11-09 16:05:35,206 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-11-09 16:05:35,211 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:35,217 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-11-09 16:05:35,220 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-09 16:05:35,221 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-09 16:05:35,221 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-11-09 16:05:35,221 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:35,221 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-11-09 16:05:35,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-11-09 16:05:35,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-11-09 16:05:35,236 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-11-09 16:05:35,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-11-09 16:05:35,239 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-09 16:05:35,240 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:05:35,240 INFO L425 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-09 16:05:35,240 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 16:05:35,241 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-11-09 16:05:35,242 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:35,242 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:35,242 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:35,245 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:35,245 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-09 16:05:35,245 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-11-09 16:05:35,245 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-11-09 16:05:35,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,246 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-11-09 16:05:35,246 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2146889191] [2024-11-09 16:05:35,246 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,269 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:35,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,297 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:35,298 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,298 INFO L85 PathProgramCache]: Analyzing trace with hash -1138642743, now seen corresponding path program 1 times [2024-11-09 16:05:35,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [167295752] [2024-11-09 16:05:35,299 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,338 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:35,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,377 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:35,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,405 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:35,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,439 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-09 16:05:35,439 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:35,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [167295752] [2024-11-09 16:05:35,439 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [167295752] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:35,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111663086] [2024-11-09 16:05:35,439 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:35,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:35,442 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-11-09 16:05:35,443 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-11-09 16:05:35,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,479 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:35,480 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:35,523 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-09 16:05:35,523 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:35,679 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-09 16:05:35,680 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111663086] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:35,680 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:35,681 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-09 16:05:35,681 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [618737977] [2024-11-09 16:05:35,682 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:35,682 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:35,682 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:35,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-09 16:05:35,683 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-09 16:05:35,683 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-11-09 16:05:35,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:35,781 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-09 16:05:35,781 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-09 16:05:35,783 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:35,784 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-09 16:05:35,784 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-09 16:05:35,784 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-09 16:05:35,784 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-09 16:05:35,784 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:35,784 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:35,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-09 16:05:35,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-09 16:05:35,788 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-11-09 16:05:35,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-09 16:05:35,789 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:35,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:05:35,790 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:35,790 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 16:05:35,790 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-09 16:05:35,791 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:35,791 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:35,791 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:35,792 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:35,792 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-09 16:05:35,792 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-11-09 16:05:35,792 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-11-09 16:05:35,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,793 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 2 times [2024-11-09 16:05:35,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [872535255] [2024-11-09 16:05:35,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,802 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:35,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,810 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:35,811 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,811 INFO L85 PathProgramCache]: Analyzing trace with hash -2000232554, now seen corresponding path program 1 times [2024-11-09 16:05:35,811 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,811 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [634062274] [2024-11-09 16:05:35,811 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,811 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,816 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:35,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,821 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:35,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,822 INFO L85 PathProgramCache]: Analyzing trace with hash -443608101, now seen corresponding path program 3 times [2024-11-09 16:05:35,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [244593466] [2024-11-09 16:05:35,822 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,965 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-09 16:05:35,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,979 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:35,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,984 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:35,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,987 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-09 16:05:35,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,998 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:36,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,005 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:36,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,011 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 34 proven. 64 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-09 16:05:36,011 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:36,012 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [244593466] [2024-11-09 16:05:36,012 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [244593466] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:36,012 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [236332841] [2024-11-09 16:05:36,012 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 16:05:36,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:36,013 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:36,014 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:36,016 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-11-09 16:05:36,068 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-09 16:05:36,068 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:36,070 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:36,072 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:36,177 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 63 proven. 69 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-09 16:05:36,177 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:36,497 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 63 proven. 70 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2024-11-09 16:05:36,498 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [236332841] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:36,498 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:36,498 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 14] total 22 [2024-11-09 16:05:36,498 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [726847403] [2024-11-09 16:05:36,498 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:36,734 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:36,734 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:36,734 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:36,734 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:36,734 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:36,734 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:36,734 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:36,734 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:36,734 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration5_Loop [2024-11-09 16:05:36,735 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:36,735 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:36,735 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,748 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,750 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,752 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,796 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:36,796 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:36,797 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:36,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:36,800 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:36,802 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-09 16:05:36,803 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:36,803 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:36,840 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-11-09 16:05:36,841 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:36,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:36,842 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:36,845 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-09 16:05:36,845 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:36,845 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:37,316 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:37,321 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:37,322 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:37,322 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:37,322 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:37,322 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:37,322 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:37,322 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,322 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:37,322 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:37,322 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration5_Loop [2024-11-09 16:05:37,322 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:37,322 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:37,323 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,328 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,331 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,340 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,395 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:37,395 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:37,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,398 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-09 16:05:37,400 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:37,413 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:37,413 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:37,413 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:37,413 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:37,413 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:37,414 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:37,414 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:37,416 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:37,431 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-11-09 16:05:37,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,433 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,434 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-11-09 16:05:37,435 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:37,447 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:37,448 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:37,448 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:37,448 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:37,448 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:37,448 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:37,448 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:37,450 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:37,465 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:37,465 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,465 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,467 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,469 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-09 16:05:37,469 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:37,481 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:37,481 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:37,481 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:37,481 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:37,481 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:37,482 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:37,482 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:37,485 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:37,489 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:37,489 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:37,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,489 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,490 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,491 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-09 16:05:37,491 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:37,492 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:37,492 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:37,492 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-09 16:05:37,502 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2024-11-09 16:05:37,503 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:37,511 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:37,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:37,557 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:37,559 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:37,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:37,775 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:37,777 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:37,901 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:37,902 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:37,902 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-11-09 16:05:37,988 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-11-09 16:05:37,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:37,990 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-11-09 16:05:37,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-09 16:05:37,990 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-09 16:05:37,991 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:37,991 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:38,001 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:38,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,044 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,046 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,197 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-11-09 16:05:38,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,286 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,287 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,415 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:38,416 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-11-09 16:05:38,416 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-11-09 16:05:38,510 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-11-09 16:05:38,511 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:38,512 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-11-09 16:05:38,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-09 16:05:38,512 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-09 16:05:38,512 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:38,512 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:38,523 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:38,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,561 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,562 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,741 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,745 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,876 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:38,877 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-11-09 16:05:38,877 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-11-09 16:05:39,110 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-11-09 16:05:39,111 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:39,113 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-11-09 16:05:39,113 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-09 16:05:39,114 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-09 16:05:39,114 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:39,114 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-09 16:05:39,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:39,115 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-09 16:05:39,120 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:39,120 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-09 16:05:39,129 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-09 16:05:39,139 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-09 16:05:39,140 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-09 16:05:39,140 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-09 16:05:39,140 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-09 16:05:39,141 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:39,141 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-09 16:05:39,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-09 16:05:39,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-09 16:05:39,158 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-11-09 16:05:39,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-09 16:05:39,160 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-09 16:05:39,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:39,160 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-09 16:05:39,161 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=376, Unknown=0, NotChecked=0, Total=462 [2024-11-09 16:05:39,161 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-11-09 16:05:39,492 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:39,492 INFO L93 Difference]: Finished difference Result 136 states and 141 transitions. [2024-11-09 16:05:39,492 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 136 states and 141 transitions. [2024-11-09 16:05:39,494 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:39,494 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 136 states to 0 states and 0 transitions. [2024-11-09 16:05:39,494 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:05:39,494 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:05:39,494 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:05:39,494 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:05:39,495 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:39,495 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:39,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-09 16:05:39,496 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:39,496 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 16:05:39,496 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 16:05:39,496 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:39,496 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 16:05:39,503 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 04:05:39 BoogieIcfgContainer [2024-11-09 16:05:39,504 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 16:05:39,504 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 16:05:39,504 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 16:05:39,504 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 16:05:39,507 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:31" (3/4) ... [2024-11-09 16:05:39,509 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 16:05:39,510 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 16:05:39,511 INFO L158 Benchmark]: Toolchain (without parser) took 8333.17ms. Allocated memory was 165.7MB in the beginning and 199.2MB in the end (delta: 33.6MB). Free memory was 112.8MB in the beginning and 159.8MB in the end (delta: -47.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:39,511 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 123.7MB. Free memory is still 95.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:39,511 INFO L158 Benchmark]: CACSL2BoogieTranslator took 261.29ms. Allocated memory is still 165.7MB. Free memory was 112.4MB in the beginning and 100.4MB in the end (delta: 12.0MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,511 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.23ms. Allocated memory is still 165.7MB. Free memory was 100.4MB in the beginning and 98.7MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,512 INFO L158 Benchmark]: Boogie Preprocessor took 33.34ms. Allocated memory is still 165.7MB. Free memory was 98.7MB in the beginning and 97.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:39,512 INFO L158 Benchmark]: RCFGBuilder took 292.48ms. Allocated memory is still 165.7MB. Free memory was 97.5MB in the beginning and 132.2MB in the end (delta: -34.8MB). Peak memory consumption was 10.9MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,512 INFO L158 Benchmark]: BuchiAutomizer took 7703.07ms. Allocated memory was 165.7MB in the beginning and 199.2MB in the end (delta: 33.6MB). Free memory was 132.2MB in the beginning and 160.9MB in the end (delta: -28.7MB). Peak memory consumption was 7.0MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,512 INFO L158 Benchmark]: Witness Printer took 5.89ms. Allocated memory is still 199.2MB. Free memory was 160.9MB in the beginning and 159.8MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,514 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.21ms. Allocated memory is still 123.7MB. Free memory is still 95.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 261.29ms. Allocated memory is still 165.7MB. Free memory was 112.4MB in the beginning and 100.4MB in the end (delta: 12.0MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 32.23ms. Allocated memory is still 165.7MB. Free memory was 100.4MB in the beginning and 98.7MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 33.34ms. Allocated memory is still 165.7MB. Free memory was 98.7MB in the beginning and 97.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 292.48ms. Allocated memory is still 165.7MB. Free memory was 97.5MB in the beginning and 132.2MB in the end (delta: -34.8MB). Peak memory consumption was 10.9MB. Max. memory is 16.1GB. * BuchiAutomizer took 7703.07ms. Allocated memory was 165.7MB in the beginning and 199.2MB in the end (delta: 33.6MB). Free memory was 132.2MB in the beginning and 160.9MB in the end (delta: -28.7MB). Peak memory consumption was 7.0MB. Max. memory is 16.1GB. * Witness Printer took 5.89ms. Allocated memory is still 199.2MB. Free memory was 160.9MB in the beginning and 159.8MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. 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 7.6s and 6 iterations. TraceHistogramMax:6. Analysis of lassos took 4.3s. Construction of modules took 0.5s. Büchi inclusion checks took 2.5s. 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.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 228 mSDsluCounter, 381 SdHoareTripleChecker+Invalid, 0.6s 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: 27ms 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-11-09 16:05:39,545 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:39,741 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Ended with exit code 0 [2024-11-09 16:05:39,942 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:40,143 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