./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_10-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 3061b6dc 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_10-2.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 a6546395432109233bf3e1991428a566548dd822bb23ca198622322bf4db5a8a --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-19 15:00:01,847 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 15:00:01,909 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-19 15:00:01,914 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 15:00:01,916 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 15:00:01,949 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 15:00:01,950 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 15:00:01,950 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 15:00:01,951 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 15:00:01,952 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 15:00:01,954 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 15:00:01,954 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 15:00:01,955 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 15:00:01,955 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-19 15:00:01,955 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-19 15:00:01,955 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-19 15:00:01,955 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-19 15:00:01,956 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-19 15:00:01,956 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-19 15:00:01,956 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 15:00:01,956 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-19 15:00:01,959 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-19 15:00:01,959 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 15:00:01,959 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-19 15:00:01,959 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 15:00:01,959 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-19 15:00:01,960 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-19 15:00:01,960 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-19 15:00:01,960 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 15:00:01,960 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-19 15:00:01,961 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-19 15:00:01,961 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 15:00:01,961 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-19 15:00:01,962 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 15:00:01,962 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 15:00:01,962 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 15:00:01,962 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 15:00:01,962 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 15:00:01,963 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-19 15:00:01,963 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 -> a6546395432109233bf3e1991428a566548dd822bb23ca198622322bf4db5a8a [2024-11-19 15:00:02,193 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 15:00:02,219 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 15:00:02,222 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 15:00:02,224 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 15:00:02,224 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 15:00:02,225 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_10-2.c [2024-11-19 15:00:03,553 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 15:00:03,714 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 15:00:03,715 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-2.c [2024-11-19 15:00:03,721 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/79548f3fc/545deae3988a4352b46add304a01bfae/FLAG5b03ddab9 [2024-11-19 15:00:04,132 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/79548f3fc/545deae3988a4352b46add304a01bfae [2024-11-19 15:00:04,134 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 15:00:04,135 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 15:00:04,136 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 15:00:04,137 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 15:00:04,144 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 15:00:04,145 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,145 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@19762e18 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04, skipping insertion in model container [2024-11-19 15:00:04,145 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,159 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 15:00:04,296 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 15:00:04,307 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 15:00:04,317 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 15:00:04,331 INFO L204 MainTranslator]: Completed translation [2024-11-19 15:00:04,332 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04 WrapperNode [2024-11-19 15:00:04,332 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 15:00:04,332 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 15:00:04,333 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 15:00:04,333 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 15:00:04,339 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,346 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,368 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-19 15:00:04,369 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 15:00:04,369 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 15:00:04,369 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 15:00:04,369 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 15:00:04,380 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,381 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,381 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,389 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-19 15:00:04,390 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,390 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,391 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,393 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,393 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,394 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,398 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 15:00:04,399 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 15:00:04,399 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 15:00:04,399 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 15:00:04,400 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (1/1) ... [2024-11-19 15:00:04,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:04,414 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:04,427 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-19 15:00:04,429 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-19 15:00:04,465 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 15:00:04,465 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 15:00:04,465 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 15:00:04,465 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 15:00:04,465 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-19 15:00:04,465 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-19 15:00:04,512 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 15:00:04,513 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 15:00:04,621 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-19 15:00:04,621 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 15:00:04,633 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 15:00:04,634 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-19 15:00:04,634 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 03:00:04 BoogieIcfgContainer [2024-11-19 15:00:04,634 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 15:00:04,635 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-19 15:00:04,635 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-19 15:00:04,638 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-19 15:00:04,639 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 15:00:04,639 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 19.11 03:00:04" (1/3) ... [2024-11-19 15:00:04,640 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@4357aa97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 03:00:04, skipping insertion in model container [2024-11-19 15:00:04,640 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 15:00:04,640 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:00:04" (2/3) ... [2024-11-19 15:00:04,640 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@4357aa97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 03:00:04, skipping insertion in model container [2024-11-19 15:00:04,640 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 15:00:04,640 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 03:00:04" (3/3) ... [2024-11-19 15:00:04,641 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_10-2.c [2024-11-19 15:00:04,682 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-19 15:00:04,683 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-19 15:00:04,683 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-19 15:00:04,683 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-19 15:00:04,683 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-19 15:00:04,683 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-19 15:00:04,683 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-19 15:00:04,683 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-19 15:00:04,686 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-19 15:00:04,700 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-19 15:00:04,700 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:04,700 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:04,705 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:00:04,705 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-19 15:00:04,705 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-19 15:00:04,705 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-19 15:00:04,707 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-19 15:00:04,707 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:04,707 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:04,708 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:00:04,708 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-19 15:00:04,713 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(12, 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 := 10; 4#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 11#$Ultimate##0true [2024-11-19 15:00:04,714 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-19 15:00:04,719 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:04,719 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-11-19 15:00:04,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:04,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1129885256] [2024-11-19 15:00:04,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:04,728 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:04,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:04,818 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:04,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:04,848 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:04,852 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:04,852 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-11-19 15:00:04,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:04,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1343867124] [2024-11-19 15:00:04,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:04,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:04,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:04,857 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:04,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:04,862 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:04,864 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:04,865 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-11-19 15:00:04,865 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:04,865 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [698744194] [2024-11-19 15:00:04,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:04,865 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:04,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:04,878 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:04,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:04,890 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:04,985 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:04,986 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:04,986 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:04,986 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:04,986 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 15:00:04,986 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:04,986 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:04,986 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:04,986 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration1_Loop [2024-11-19 15:00:04,986 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:04,986 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:04,997 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,005 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,007 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,010 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,018 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,079 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:05,080 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 15:00:05,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,084 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-19 15:00:05,086 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-19 15:00:05,089 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:05,089 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:05,109 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:05,109 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-19 15:00:05,122 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-19 15:00:05,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,124 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-19 15:00:05,125 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-19 15:00:05,125 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:05,125 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:05,137 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:05,137 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 15:00:05,148 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:05,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,150 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-19 15:00:05,151 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-19 15:00:05,152 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:05,152 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:05,164 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:05,164 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 15:00:05,175 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:05,176 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,176 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,178 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-19 15:00:05,179 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-19 15:00:05,181 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:05,181 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:05,203 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-19 15:00:05,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,205 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-19 15:00:05,207 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-19 15:00:05,208 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 15:00:05,208 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:05,261 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 15:00:05,266 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-11-19 15:00:05,267 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:05,267 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:05,267 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:05,267 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:05,267 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 15:00:05,267 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,267 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:05,267 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:05,267 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration1_Loop [2024-11-19 15:00:05,267 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:05,267 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:05,268 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,271 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,273 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,275 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,282 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:05,322 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:05,326 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 15:00:05,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,328 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,329 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-19 15:00:05,331 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-19 15:00:05,332 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-19 15:00:05,343 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:05,344 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:05,344 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:05,344 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:05,344 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:05,346 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:05,346 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:05,348 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:05,359 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-19 15:00:05,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,359 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,361 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-19 15:00:05,362 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-19 15:00:05,362 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-19 15:00:05,372 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:05,372 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:05,372 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:05,373 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:05,373 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:05,373 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:05,373 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:05,375 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:05,388 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-19 15:00:05,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,389 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,393 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-19 15:00:05,394 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-19 15:00:05,395 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-19 15:00:05,405 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:05,405 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:05,405 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:05,405 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:05,405 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:05,406 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:05,406 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:05,408 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:05,419 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-19 15:00:05,420 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,420 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,421 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-19 15:00:05,421 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-19 15:00:05,422 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-19 15:00:05,432 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:05,432 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:05,432 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:05,433 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:05,433 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:05,433 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:05,434 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:05,436 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 15:00:05,438 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 15:00:05,439 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-19 15:00:05,440 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:05,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:05,441 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-19 15:00:05,443 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-19 15:00:05,443 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 15:00:05,443 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 15:00:05,443 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 15:00:05,444 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-19 15:00:05,455 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:05,458 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 15:00:05,485 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:05,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:05,507 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-19 15:00:05,508 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:05,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:05,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 15:00:05,527 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:05,570 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-19 15:00:05,599 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-19 15:00:05,600 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-19 15:00:05,685 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-19 15:00:05,688 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-19 15:00:05,692 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-19 15:00:05,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-19 15:00:05,694 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-19 15:00:05,696 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:05,696 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-19 15:00:05,696 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:05,696 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-19 15:00:05,696 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:05,697 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-19 15:00:05,702 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-19 15:00:05,708 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-19 15:00:05,710 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-19 15:00:05,710 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-19 15:00:05,711 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-19 15:00:05,712 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:05,712 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-19 15:00:05,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-19 15:00:05,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-19 15:00:05,733 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-19 15:00:05,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-19 15:00:05,735 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-19 15:00:05,735 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-19 15:00:05,735 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-19 15:00:05,735 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-19 15:00:05,736 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-19 15:00:05,736 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:05,736 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:05,737 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:05,737 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:05,737 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(12, 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 := 10; 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-19 15:00:05,737 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-19 15:00:05,737 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:05,737 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-11-19 15:00:05,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:05,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [771646528] [2024-11-19 15:00:05,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:05,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:05,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:05,833 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-11-19 15:00:05,889 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-19 15:00:05,890 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:00:05,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [771646528] [2024-11-19 15:00:05,891 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [771646528] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 15:00:05,891 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 15:00:05,891 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 15:00:05,891 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [55334891] [2024-11-19 15:00:05,894 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 15:00:05,896 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-19 15:00:05,897 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:05,897 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-11-19 15:00:05,897 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:05,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1452981448] [2024-11-19 15:00:05,898 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:05,898 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:05,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:05,977 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-19 15:00:05,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:00:05,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1452981448] [2024-11-19 15:00:05,978 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1452981448] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 15:00:05,978 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 15:00:05,978 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 15:00:05,979 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1141505887] [2024-11-19 15:00:05,979 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 15:00:05,979 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:00:05,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:00:05,981 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-19 15:00:05,982 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-19 15:00:05,983 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-19 15:00:06,049 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:00:06,050 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-19 15:00:06,050 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-19 15:00:06,051 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-19 15:00:06,052 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-19 15:00:06,052 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-19 15:00:06,052 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-19 15:00:06,052 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-19 15:00:06,053 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:06,053 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-19 15:00:06,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-19 15:00:06,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-19 15:00:06,056 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-19 15:00:06,057 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-19 15:00:06,057 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-19 15:00:06,058 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-19 15:00:06,061 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-19 15:00:06,062 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-19 15:00:06,062 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-19 15:00:06,062 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-19 15:00:06,063 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:06,063 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:06,063 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:06,063 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:06,063 INFO L745 eck$LassoCheckResult]: Stem: 199#$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(12, 2);call #Ultimate.allocInit(12, 3); 200#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 := 10; 184#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 183#$Ultimate##0 ~n := #in~n; 185#L8 assume !(~n < 1); 198#L10 assume !(1 == ~n); 187#L13 call #t~ret4 := fibo(~n - 1);< 186#$Ultimate##0 ~n := #in~n; 188#L8 assume !(~n < 1); 206#L10 assume 1 == ~n;#res := 1; 205#fiboFINAL assume true; 204#fiboEXIT >#35#return; 190#L13-1 [2024-11-19 15:00:06,065 INFO L747 eck$LassoCheckResult]: Loop: 190#L13-1 call #t~ret5 := fibo(~n - 2);< 191#$Ultimate##0 ~n := #in~n; 196#L8 assume !(~n < 1); 197#L10 assume !(1 == ~n); 189#L13 call #t~ret4 := fibo(~n - 1);< 191#$Ultimate##0 ~n := #in~n; 196#L8 assume !(~n < 1); 197#L10 assume 1 == ~n;#res := 1; 201#fiboFINAL assume true; 202#fiboEXIT >#35#return; 190#L13-1 [2024-11-19 15:00:06,066 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:06,066 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-11-19 15:00:06,066 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:06,066 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1994584190] [2024-11-19 15:00:06,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:06,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:06,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:06,140 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-19 15:00:06,141 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:00:06,141 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1994584190] [2024-11-19 15:00:06,141 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1994584190] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:00:06,141 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1635123556] [2024-11-19 15:00:06,141 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:06,141 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:00:06,141 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,143 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-19 15:00:06,144 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-19 15:00:06,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:06,172 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-19 15:00:06,173 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:06,192 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-19 15:00:06,193 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:00:06,275 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-19 15:00:06,275 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1635123556] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:00:06,275 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:00:06,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2024-11-19 15:00:06,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1839965436] [2024-11-19 15:00:06,276 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:00:06,277 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-19 15:00:06,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:06,278 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-11-19 15:00:06,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:06,278 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1135523386] [2024-11-19 15:00:06,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:06,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:06,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:06,287 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:06,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:06,295 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:06,399 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:06,400 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:06,400 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:06,400 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:06,400 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 15:00:06,400 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,400 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:06,400 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:06,400 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration3_Loop [2024-11-19 15:00:06,400 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:06,400 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:06,401 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,403 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,405 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,407 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,411 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,441 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:06,442 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 15:00:06,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,442 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,446 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-19 15:00:06,448 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-19 15:00:06,450 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:06,450 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:06,462 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:06,462 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-19 15:00:06,472 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:06,473 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,473 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,474 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-19 15:00:06,475 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-19 15:00:06,475 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:06,476 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:06,486 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:06,487 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 15:00:06,497 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-19 15:00:06,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,499 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-19 15:00:06,500 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-19 15:00:06,500 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:06,502 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:06,518 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:06,518 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-19 15:00:06,529 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:06,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,530 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-19 15:00:06,531 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-19 15:00:06,532 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:06,532 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:06,556 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-19 15:00:06,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,558 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-19 15:00:06,558 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-19 15:00:06,559 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 15:00:06,559 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:06,572 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 15:00:06,584 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:06,585 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:06,585 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:06,586 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:06,586 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:06,586 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 15:00:06,586 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,586 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:06,586 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:06,586 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration3_Loop [2024-11-19 15:00:06,586 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:06,586 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:06,589 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,592 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,594 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,596 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,598 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:06,631 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:06,632 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 15:00:06,632 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,632 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,633 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-19 15:00:06,634 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-19 15:00:06,634 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-19 15:00:06,644 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:06,644 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:06,644 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:06,644 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:06,644 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:06,645 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:06,645 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:06,647 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:06,657 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-19 15:00:06,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,659 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-19 15:00:06,659 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-19 15:00:06,660 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-19 15:00:06,669 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:06,670 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:06,670 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:06,670 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:06,670 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:06,670 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:06,670 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:06,672 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:06,682 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:06,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,683 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-19 15:00:06,685 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-19 15:00:06,686 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-19 15:00:06,695 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:06,695 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:06,695 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:06,696 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:06,696 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:06,696 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:06,696 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:06,697 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:06,707 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-19 15:00:06,707 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,709 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-19 15:00:06,710 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-19 15:00:06,712 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-19 15:00:06,722 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:06,722 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:06,722 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:06,722 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:06,722 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:06,723 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:06,723 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:06,724 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:06,734 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-19 15:00:06,734 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,736 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-19 15:00:06,736 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-19 15:00:06,737 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-19 15:00:06,746 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:06,747 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:06,747 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:06,747 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:06,747 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:06,748 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:06,748 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:06,750 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 15:00:06,752 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 15:00:06,752 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-19 15:00:06,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:06,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:06,753 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-19 15:00:06,754 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-19 15:00:06,758 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 15:00:06,758 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 15:00:06,758 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 15:00:06,758 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-19 15:00:06,768 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-19 15:00:06,770 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 15:00:06,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:06,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:06,803 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-19 15:00:06,804 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:06,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:06,888 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 15:00:06,889 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:06,965 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-19 15:00:06,965 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-19 15:00:06,965 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-19 15:00:07,157 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-19 15:00:07,158 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-19 15:00:07,158 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-19 15:00:07,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-19 15:00:07,159 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-11-19 15:00:07,159 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:07,159 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-11-19 15:00:07,160 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:07,160 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-11-19 15:00:07,162 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:07,162 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-11-19 15:00:07,167 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-19 15:00:07,174 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-11-19 15:00:07,175 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-11-19 15:00:07,176 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-11-19 15:00:07,176 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-11-19 15:00:07,176 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:07,176 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-11-19 15:00:07,177 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-11-19 15:00:07,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-11-19 15:00:07,185 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-19 15:00:07,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-11-19 15:00:07,186 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-11-19 15:00:07,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:00:07,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-19 15:00:07,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-11-19 15:00:07,187 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 11 states, 8 states have (on average 2.0) internal successors, (16), 8 states have internal predecessors, (16), 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-19 15:00:07,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:00:07,302 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-11-19 15:00:07,302 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-11-19 15:00:07,307 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-19 15:00:07,309 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-11-19 15:00:07,310 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-19 15:00:07,310 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-19 15:00:07,310 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-11-19 15:00:07,310 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:07,310 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-11-19 15:00:07,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-11-19 15:00:07,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-11-19 15:00:07,316 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-19 15:00:07,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-11-19 15:00:07,318 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-19 15:00:07,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 15:00:07,318 INFO L425 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-19 15:00:07,319 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-19 15:00:07,319 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-11-19 15:00:07,320 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-19 15:00:07,320 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:07,320 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:07,321 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:07,321 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:07,321 INFO L745 eck$LassoCheckResult]: Stem: 792#$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(12, 2);call #Ultimate.allocInit(12, 3); 793#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 := 10; 778#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 779#$Ultimate##0 ~n := #in~n; 796#L8 assume !(~n < 1); 797#L10 assume !(1 == ~n); 766#L13 call #t~ret4 := fibo(~n - 1);< 765#$Ultimate##0 ~n := #in~n; 767#L8 assume !(~n < 1); 826#L10 assume !(1 == ~n); 770#L13 call #t~ret4 := fibo(~n - 1);< 771#$Ultimate##0 ~n := #in~n; 824#L8 assume !(~n < 1); 822#L10 assume !(1 == ~n); 817#L13 call #t~ret4 := fibo(~n - 1);< 771#$Ultimate##0 ~n := #in~n; 824#L8 assume !(~n < 1); 822#L10 assume !(1 == ~n); 817#L13 call #t~ret4 := fibo(~n - 1);< 771#$Ultimate##0 ~n := #in~n; 825#L8 assume !(~n < 1); 823#L10 assume 1 == ~n;#res := 1; 821#fiboFINAL assume true; 820#fiboEXIT >#35#return; 803#L13-1 call #t~ret5 := fibo(~n - 2);< 818#$Ultimate##0 ~n := #in~n; 864#L8 assume ~n < 1;#res := 0; 862#fiboFINAL assume true; 861#fiboEXIT >#37#return; 859#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 858#fiboFINAL assume true; 852#fiboEXIT >#35#return; 801#L13-1 [2024-11-19 15:00:07,321 INFO L747 eck$LassoCheckResult]: Loop: 801#L13-1 call #t~ret5 := fibo(~n - 2);< 769#$Ultimate##0 ~n := #in~n; 856#L8 assume !(~n < 1); 798#L10 assume !(1 == ~n); 800#L13 call #t~ret4 := fibo(~n - 1);< 769#$Ultimate##0 ~n := #in~n; 856#L8 assume !(~n < 1); 798#L10 assume 1 == ~n;#res := 1; 802#fiboFINAL assume true; 848#fiboEXIT >#35#return; 801#L13-1 [2024-11-19 15:00:07,322 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:07,322 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-11-19 15:00:07,322 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:07,322 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101300301] [2024-11-19 15:00:07,322 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:07,322 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:07,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:07,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2024-11-19 15:00:07,570 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-19 15:00:07,571 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:00:07,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101300301] [2024-11-19 15:00:07,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1101300301] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:00:07,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1346986963] [2024-11-19 15:00:07,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:07,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:00:07,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:07,576 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-19 15:00:07,588 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2024-11-19 15:00:07,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:07,625 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-19 15:00:07,626 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:07,686 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-19 15:00:07,686 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:00:07,918 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 15:00:07,918 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1346986963] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:00:07,918 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:00:07,918 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 12] total 20 [2024-11-19 15:00:07,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1489828794] [2024-11-19 15:00:07,918 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:00:07,919 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-19 15:00:07,919 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:07,919 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 2 times [2024-11-19 15:00:07,919 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:07,919 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2093098152] [2024-11-19 15:00:07,919 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 15:00:07,919 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:07,928 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 15:00:07,928 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:00:07,929 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:07,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:07,935 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:08,017 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:08,017 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:08,018 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:08,018 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:08,018 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 15:00:08,018 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,018 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:08,018 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:08,018 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration4_Loop [2024-11-19 15:00:08,018 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:08,018 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:08,019 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,021 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,027 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,031 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,033 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,061 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:08,061 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 15:00:08,062 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,062 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,064 INFO L229 MonitoredProcess]: Starting monitored process 25 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-19 15:00:08,065 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-11-19 15:00:08,066 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:08,066 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:08,078 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:08,079 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-19 15:00:08,089 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2024-11-19 15:00:08,090 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,090 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,091 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-19 15:00:08,093 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-19 15:00:08,093 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:08,093 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:08,104 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:08,104 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-19 15:00:08,114 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:08,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,116 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-19 15:00:08,116 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-19 15:00:08,117 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:08,117 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:08,138 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-11-19 15:00:08,138 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,139 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-19 15:00:08,140 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-19 15:00:08,140 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 15:00:08,140 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:08,152 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 15:00:08,163 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-19 15:00:08,164 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:08,164 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:08,164 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:08,164 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:08,164 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 15:00:08,164 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,164 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:08,164 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:08,164 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration4_Loop [2024-11-19 15:00:08,164 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:08,164 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:08,165 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,167 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,169 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,170 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,177 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:08,205 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:08,206 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 15:00:08,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,207 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-19 15:00:08,208 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-19 15:00:08,209 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-19 15:00:08,218 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:08,218 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:08,219 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:08,219 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:08,219 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:08,219 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:08,219 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:08,221 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:08,231 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-19 15:00:08,231 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,232 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-19 15:00:08,233 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-19 15:00:08,234 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-19 15:00:08,244 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:08,244 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:08,244 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:08,244 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:08,244 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:08,245 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:08,245 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:08,247 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:08,256 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-19 15:00:08,257 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,257 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,258 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-19 15:00:08,258 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-19 15:00:08,259 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-19 15:00:08,268 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:08,268 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:08,268 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:08,268 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:08,268 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:08,269 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:08,269 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:08,270 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:08,280 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-19 15:00:08,280 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,280 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,281 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:08,281 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-19 15:00:08,282 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-19 15:00:08,291 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:08,291 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:08,292 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:08,292 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:08,292 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:08,292 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:08,292 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:08,294 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 15:00:08,296 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 15:00:08,296 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-19 15:00:08,296 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:08,296 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:08,297 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:08,298 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-19 15:00:08,299 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 15:00:08,299 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 15:00:08,299 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 15:00:08,299 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-19 15:00:08,309 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:08,309 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 15:00:08,316 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:08,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:08,358 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 15:00:08,360 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:08,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:08,550 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 15:00:08,551 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:08,616 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-19 15:00:08,617 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-19 15:00:08,617 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 15:00:08,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:08,821 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 190 states and 265 transitions. Complement of second has 37 states. [2024-11-19 15:00:08,822 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-19 15:00:08,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 15:00:08,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-19 15:00:08,823 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-19 15:00:08,824 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:08,824 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 15:00:08,838 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:08,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:08,875 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 15:00:08,876 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:09,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:09,032 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 15:00:09,033 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:09,098 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-19 15:00:09,100 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-19 15:00:09,101 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 15:00:09,267 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 296 states and 402 transitions. Complement of second has 29 states. [2024-11-19 15:00:09,268 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-19 15:00:09,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 15:00:09,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-11-19 15:00:09,269 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-19 15:00:09,269 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:09,269 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 15:00:09,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:09,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:09,319 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 15:00:09,321 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:09,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:09,471 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 15:00:09,471 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:09,535 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-19 15:00:09,536 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-19 15:00:09,536 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 15:00:09,740 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 143 transitions. cyclomatic complexity: 42. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 817 states and 1129 transitions. Complement of second has 135 states. [2024-11-19 15:00:09,741 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-19 15:00:09,742 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 15:00:09,743 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-11-19 15:00:09,743 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-19 15:00:09,744 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:09,745 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-11-19 15:00:09,745 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:09,746 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-11-19 15:00:09,746 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:09,748 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 817 states and 1129 transitions. [2024-11-19 15:00:09,764 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-11-19 15:00:09,781 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 817 states to 418 states and 629 transitions. [2024-11-19 15:00:09,781 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 162 [2024-11-19 15:00:09,783 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 182 [2024-11-19 15:00:09,783 INFO L73 IsDeterministic]: Start isDeterministic. Operand 418 states and 629 transitions. [2024-11-19 15:00:09,784 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:09,784 INFO L218 hiAutomatonCegarLoop]: Abstraction has 418 states and 629 transitions. [2024-11-19 15:00:09,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 418 states and 629 transitions. [2024-11-19 15:00:09,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 418 to 356. [2024-11-19 15:00:09,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 356 states, 223 states have (on average 1.1973094170403586) internal successors, (267), 239 states have internal predecessors, (267), 75 states have call successors, (84), 46 states have call predecessors, (84), 58 states have return successors, (142), 70 states have call predecessors, (142), 71 states have call successors, (142) [2024-11-19 15:00:09,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 356 states to 356 states and 493 transitions. [2024-11-19 15:00:09,822 INFO L240 hiAutomatonCegarLoop]: Abstraction has 356 states and 493 transitions. [2024-11-19 15:00:09,822 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:00:09,823 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-19 15:00:09,823 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2024-11-19 15:00:09,823 INFO L87 Difference]: Start difference. First operand 356 states and 493 transitions. Second operand has 21 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 14 states have internal predecessors, (37), 11 states have call successors, (11), 7 states have call predecessors, (11), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-19 15:00:10,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:00:10,098 INFO L93 Difference]: Finished difference Result 620 states and 969 transitions. [2024-11-19 15:00:10,098 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 620 states and 969 transitions. [2024-11-19 15:00:10,107 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-11-19 15:00:10,117 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 620 states to 595 states and 933 transitions. [2024-11-19 15:00:10,117 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 277 [2024-11-19 15:00:10,117 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 280 [2024-11-19 15:00:10,118 INFO L73 IsDeterministic]: Start isDeterministic. Operand 595 states and 933 transitions. [2024-11-19 15:00:10,118 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:10,118 INFO L218 hiAutomatonCegarLoop]: Abstraction has 595 states and 933 transitions. [2024-11-19 15:00:10,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 595 states and 933 transitions. [2024-11-19 15:00:10,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 595 to 516. [2024-11-19 15:00:10,144 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 516 states, 315 states have (on average 1.146031746031746) internal successors, (361), 339 states have internal predecessors, (361), 118 states have call successors, (128), 62 states have call predecessors, (128), 83 states have return successors, (275), 114 states have call predecessors, (275), 109 states have call successors, (275) [2024-11-19 15:00:10,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 516 states to 516 states and 764 transitions. [2024-11-19 15:00:10,148 INFO L240 hiAutomatonCegarLoop]: Abstraction has 516 states and 764 transitions. [2024-11-19 15:00:10,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-19 15:00:10,149 INFO L425 stractBuchiCegarLoop]: Abstraction has 516 states and 764 transitions. [2024-11-19 15:00:10,149 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-19 15:00:10,149 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 516 states and 764 transitions. [2024-11-19 15:00:10,151 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2024-11-19 15:00:10,152 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:10,152 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:10,152 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:10,153 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-19 15:00:10,153 INFO L745 eck$LassoCheckResult]: Stem: 4040#$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(12, 2);call #Ultimate.allocInit(12, 3); 4041#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 := 10; 4033#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 4034#$Ultimate##0 ~n := #in~n; 4085#L8 assume !(~n < 1); 4084#L10 assume !(1 == ~n); 4080#L13 call #t~ret4 := fibo(~n - 1);< 4083#$Ultimate##0 ~n := #in~n; 4082#L8 assume !(~n < 1); 4081#L10 assume !(1 == ~n); 4076#L13 call #t~ret4 := fibo(~n - 1);< 4079#$Ultimate##0 ~n := #in~n; 4078#L8 assume !(~n < 1); 4077#L10 assume !(1 == ~n); 4072#L13 call #t~ret4 := fibo(~n - 1);< 4075#$Ultimate##0 ~n := #in~n; 4074#L8 assume !(~n < 1); 4073#L10 assume !(1 == ~n); 4050#L13 call #t~ret4 := fibo(~n - 1);< 4071#$Ultimate##0 ~n := #in~n; 4070#L8 assume !(~n < 1); 4069#L10 assume !(1 == ~n); 4065#L13 call #t~ret4 := fibo(~n - 1);< 4067#$Ultimate##0 ~n := #in~n; 4068#L8 assume !(~n < 1); 4064#L10 assume !(1 == ~n); 4060#L13 call #t~ret4 := fibo(~n - 1);< 4058#$Ultimate##0 ~n := #in~n; 4061#L8 assume !(~n < 1); 4066#L10 assume !(1 == ~n); 4059#L13 call #t~ret4 := fibo(~n - 1);< 4058#$Ultimate##0 ~n := #in~n; 4062#L8 assume !(~n < 1); 4286#L10 assume 1 == ~n;#res := 1; 4284#fiboFINAL assume true; 4281#fiboEXIT >#35#return; 4193#L13-1 call #t~ret5 := fibo(~n - 2);< 4244#$Ultimate##0 ~n := #in~n; 4387#L8 assume !(~n < 1); 4386#L10 assume !(1 == ~n); 4384#L13 call #t~ret4 := fibo(~n - 1);< 4385#$Ultimate##0 ~n := #in~n; 4505#L8 assume !(~n < 1); 4503#L10 assume !(1 == ~n); 4056#L13 call #t~ret4 := fibo(~n - 1);< 4511#$Ultimate##0 [2024-11-19 15:00:10,153 INFO L747 eck$LassoCheckResult]: Loop: 4511#$Ultimate##0 ~n := #in~n; 4054#L8 assume !(~n < 1); 4057#L10 assume !(1 == ~n); 4055#L13 call #t~ret4 := fibo(~n - 1);< 4511#$Ultimate##0 [2024-11-19 15:00:10,153 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:10,153 INFO L85 PathProgramCache]: Analyzing trace with hash 1746618538, now seen corresponding path program 1 times [2024-11-19 15:00:10,153 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:10,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1372377126] [2024-11-19 15:00:10,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:10,154 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:10,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:10,386 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-19 15:00:10,387 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:00:10,387 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1372377126] [2024-11-19 15:00:10,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1372377126] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:00:10,387 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1029420144] [2024-11-19 15:00:10,387 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:00:10,387 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:00:10,387 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,389 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,390 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2024-11-19 15:00:10,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:10,425 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-19 15:00:10,427 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:10,471 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-19 15:00:10,471 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:00:10,675 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-19 15:00:10,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1029420144] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:00:10,675 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:00:10,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 23 [2024-11-19 15:00:10,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380908104] [2024-11-19 15:00:10,676 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:00:10,676 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-19 15:00:10,677 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:10,677 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 2 times [2024-11-19 15:00:10,677 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:10,677 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1624756789] [2024-11-19 15:00:10,677 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 15:00:10,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:10,679 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2024-11-19 15:00:10,679 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:00:10,680 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:10,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:10,681 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:10,712 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:10,712 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:10,712 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:10,712 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:10,713 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 15:00:10,713 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,713 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:10,713 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:10,713 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration5_Loop [2024-11-19 15:00:10,713 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:10,713 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:10,714 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,716 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,719 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,720 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,726 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,756 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:10,756 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 15:00:10,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,758 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,759 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-19 15:00:10,761 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:10,761 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:10,773 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:10,773 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-19 15:00:10,784 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-11-19 15:00:10,787 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,788 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,789 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,791 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-19 15:00:10,792 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:10,792 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:10,803 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:10,803 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 15:00:10,814 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2024-11-19 15:00:10,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,814 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,816 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,817 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-19 15:00:10,818 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:10,818 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:10,829 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:10,829 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 15:00:10,840 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2024-11-19 15:00:10,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,842 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,843 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-19 15:00:10,844 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:10,844 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:10,868 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2024-11-19 15:00:10,869 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,869 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,870 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-19 15:00:10,873 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 15:00:10,873 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:10,898 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 15:00:10,902 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Ended with exit code 0 [2024-11-19 15:00:10,902 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:10,903 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:10,903 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:10,903 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:10,903 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 15:00:10,903 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,903 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:10,903 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:10,903 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration5_Loop [2024-11-19 15:00:10,903 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:10,903 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:10,904 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,905 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,906 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,911 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,913 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:10,941 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:10,941 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 15:00:10,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,941 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,942 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,947 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-11-19 15:00:10,948 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-19 15:00:10,957 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:10,958 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:10,958 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:10,958 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:10,958 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:10,958 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:10,958 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:10,960 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:10,971 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-19 15:00:10,971 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,973 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,973 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-19 15:00:10,974 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-19 15:00:10,984 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:10,984 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:10,984 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:10,984 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:10,984 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:10,984 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:10,984 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:10,985 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:10,995 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-11-19 15:00:10,996 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:10,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:10,997 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 15:00:10,998 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-19 15:00:10,999 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-19 15:00:11,008 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:11,009 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:11,009 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:11,009 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:11,009 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:11,009 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:11,009 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:11,011 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:11,022 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Ended with exit code 0 [2024-11-19 15:00:11,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:11,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:11,023 INFO L229 MonitoredProcess]: Starting monitored process 43 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-19 15:00:11,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2024-11-19 15:00:11,024 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-19 15:00:11,034 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:11,034 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:11,034 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:11,034 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:11,034 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:11,034 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:11,035 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:11,035 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:11,046 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2024-11-19 15:00:11,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:11,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:11,047 INFO L229 MonitoredProcess]: Starting monitored process 44 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-19 15:00:11,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2024-11-19 15:00:11,048 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-19 15:00:11,058 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:11,058 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:11,058 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:11,058 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:11,058 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:11,059 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:11,059 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:11,061 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 15:00:11,063 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-19 15:00:11,063 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 15:00:11,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:11,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:11,064 INFO L229 MonitoredProcess]: Starting monitored process 45 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-19 15:00:11,067 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2024-11-19 15:00:11,067 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 15:00:11,067 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 15:00:11,067 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 15:00:11,067 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-19 15:00:11,078 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Ended with exit code 0 [2024-11-19 15:00:11,079 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 15:00:11,087 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:11,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:11,136 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-19 15:00:11,137 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:11,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:11,213 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 15:00:11,214 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:11,236 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-19 15:00:11,236 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-19 15:00:11,237 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 516 states and 764 transitions. cyclomatic complexity: 255 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:11,283 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 516 states and 764 transitions. cyclomatic complexity: 255. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 538 states and 786 transitions. Complement of second has 15 states. [2024-11-19 15:00:11,284 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-19 15:00:11,285 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:11,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-19 15:00:11,285 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-19 15:00:11,285 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:11,285 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 15:00:11,293 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:11,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:11,335 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-19 15:00:11,336 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:11,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:11,421 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 15:00:11,422 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:11,440 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-19 15:00:11,441 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-19 15:00:11,441 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 516 states and 764 transitions. cyclomatic complexity: 255 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:11,487 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 516 states and 764 transitions. cyclomatic complexity: 255. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 538 states and 786 transitions. Complement of second has 15 states. [2024-11-19 15:00:11,488 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-19 15:00:11,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:11,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-19 15:00:11,489 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-19 15:00:11,489 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:11,489 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 15:00:11,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:11,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:11,544 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-19 15:00:11,545 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:11,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:11,620 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 15:00:11,621 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:11,639 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-19 15:00:11,640 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-19 15:00:11,640 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 516 states and 764 transitions. cyclomatic complexity: 255 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:11,694 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Ended with exit code 0 [2024-11-19 15:00:11,728 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 516 states and 764 transitions. cyclomatic complexity: 255. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 695 states and 946 transitions. Complement of second has 19 states. [2024-11-19 15:00:11,729 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-19 15:00:11,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:11,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-19 15:00:11,730 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-11-19 15:00:11,732 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:11,732 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-19 15:00:11,733 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:11,733 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-11-19 15:00:11,733 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:11,733 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 695 states and 946 transitions. [2024-11-19 15:00:11,741 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2024-11-19 15:00:11,747 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 695 states to 556 states and 805 transitions. [2024-11-19 15:00:11,747 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 205 [2024-11-19 15:00:11,747 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 211 [2024-11-19 15:00:11,747 INFO L73 IsDeterministic]: Start isDeterministic. Operand 556 states and 805 transitions. [2024-11-19 15:00:11,748 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:11,748 INFO L218 hiAutomatonCegarLoop]: Abstraction has 556 states and 805 transitions. [2024-11-19 15:00:11,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 556 states and 805 transitions. [2024-11-19 15:00:11,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 556 to 546. [2024-11-19 15:00:11,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 546 states, 342 states have (on average 1.1345029239766082) internal successors, (388), 369 states have internal predecessors, (388), 118 states have call successors, (128), 62 states have call predecessors, (128), 86 states have return successors, (275), 114 states have call predecessors, (275), 109 states have call successors, (275) [2024-11-19 15:00:11,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 546 states to 546 states and 791 transitions. [2024-11-19 15:00:11,762 INFO L240 hiAutomatonCegarLoop]: Abstraction has 546 states and 791 transitions. [2024-11-19 15:00:11,763 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:00:11,763 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-19 15:00:11,763 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=396, Unknown=0, NotChecked=0, Total=506 [2024-11-19 15:00:11,763 INFO L87 Difference]: Start difference. First operand 546 states and 791 transitions. Second operand has 23 states, 21 states have (on average 1.7619047619047619) internal successors, (37), 15 states have internal predecessors, (37), 11 states have call successors, (13), 10 states have call predecessors, (13), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-19 15:00:12,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:00:12,042 INFO L93 Difference]: Finished difference Result 787 states and 1157 transitions. [2024-11-19 15:00:12,042 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 787 states and 1157 transitions. [2024-11-19 15:00:12,048 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2024-11-19 15:00:12,055 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 787 states to 744 states and 1095 transitions. [2024-11-19 15:00:12,055 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 259 [2024-11-19 15:00:12,056 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 265 [2024-11-19 15:00:12,056 INFO L73 IsDeterministic]: Start isDeterministic. Operand 744 states and 1095 transitions. [2024-11-19 15:00:12,056 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:12,056 INFO L218 hiAutomatonCegarLoop]: Abstraction has 744 states and 1095 transitions. [2024-11-19 15:00:12,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 744 states and 1095 transitions. [2024-11-19 15:00:12,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 744 to 689. [2024-11-19 15:00:12,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 689 states, 435 states have (on average 1.1172413793103448) internal successors, (486), 463 states have internal predecessors, (486), 158 states have call successors, (170), 87 states have call predecessors, (170), 96 states have return successors, (294), 138 states have call predecessors, (294), 146 states have call successors, (294) [2024-11-19 15:00:12,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 689 states to 689 states and 950 transitions. [2024-11-19 15:00:12,074 INFO L240 hiAutomatonCegarLoop]: Abstraction has 689 states and 950 transitions. [2024-11-19 15:00:12,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-19 15:00:12,075 INFO L425 stractBuchiCegarLoop]: Abstraction has 689 states and 950 transitions. [2024-11-19 15:00:12,076 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-19 15:00:12,076 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 689 states and 950 transitions. [2024-11-19 15:00:12,079 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2024-11-19 15:00:12,080 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:00:12,080 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:00:12,081 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [13, 13, 12, 11, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:00:12,082 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-19 15:00:12,082 INFO L745 eck$LassoCheckResult]: Stem: 8492#$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(12, 2);call #Ultimate.allocInit(12, 3); 8493#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 := 10; 8479#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 8480#$Ultimate##0 ~n := #in~n; 8635#L8 assume !(~n < 1); 8627#L10 assume !(1 == ~n); 8624#L13 call #t~ret4 := fibo(~n - 1);< 8625#$Ultimate##0 ~n := #in~n; 8685#L8 assume !(~n < 1); 8683#L10 assume !(1 == ~n); 8612#L13 call #t~ret4 := fibo(~n - 1);< 8681#$Ultimate##0 ~n := #in~n; 8679#L8 assume !(~n < 1); 8677#L10 assume !(1 == ~n); 8672#L13 call #t~ret4 := fibo(~n - 1);< 8675#$Ultimate##0 ~n := #in~n; 8928#L8 assume !(~n < 1); 8927#L10 assume !(1 == ~n); 8700#L13 call #t~ret4 := fibo(~n - 1);< 8701#$Ultimate##0 ~n := #in~n; 8711#L8 assume !(~n < 1); 8710#L10 assume !(1 == ~n); 8695#L13 call #t~ret4 := fibo(~n - 1);< 8705#$Ultimate##0 ~n := #in~n; 8716#L8 assume !(~n < 1); 8714#L10 assume !(1 == ~n); 8707#L13 call #t~ret4 := fibo(~n - 1);< 8713#$Ultimate##0 ~n := #in~n; 8777#L8 assume !(~n < 1); 8774#L10 assume !(1 == ~n); 8771#L13 call #t~ret4 := fibo(~n - 1);< 8772#$Ultimate##0 ~n := #in~n; 8890#L8 assume !(~n < 1); 8889#L10 assume !(1 == ~n); 8731#L13 call #t~ret4 := fibo(~n - 1);< 8888#$Ultimate##0 ~n := #in~n; 8943#L8 assume !(~n < 1); 8942#L10 assume !(1 == ~n); 8724#L13 call #t~ret4 := fibo(~n - 1);< 8888#$Ultimate##0 ~n := #in~n; 8945#L8 assume !(~n < 1); 9056#L10 assume 1 == ~n;#res := 1; 9052#fiboFINAL assume true; 9023#fiboEXIT >#35#return; 8726#L13-1 call #t~ret5 := fibo(~n - 2);< 8896#$Ultimate##0 ~n := #in~n; 9103#L8 assume !(~n < 1); 8899#L10 assume !(1 == ~n); 8900#L13 call #t~ret4 := fibo(~n - 1);< 9120#$Ultimate##0 ~n := #in~n; 9127#L8 assume !(~n < 1); 9132#L10 assume !(1 == ~n); 8513#L13 call #t~ret4 := fibo(~n - 1);< 8511#$Ultimate##0 ~n := #in~n; 8515#L8 assume !(~n < 1); 9137#L10 assume !(1 == ~n); 8512#L13 [2024-11-19 15:00:12,082 INFO L747 eck$LassoCheckResult]: Loop: 8512#L13 call #t~ret4 := fibo(~n - 1);< 8511#$Ultimate##0 ~n := #in~n; 8515#L8 assume !(~n < 1); 9137#L10 assume !(1 == ~n); 8512#L13 [2024-11-19 15:00:12,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:12,082 INFO L85 PathProgramCache]: Analyzing trace with hash -1585625609, now seen corresponding path program 2 times [2024-11-19 15:00:12,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:12,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [484658956] [2024-11-19 15:00:12,083 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 15:00:12,083 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:12,094 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 15:00:12,095 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 15:00:12,390 INFO L134 CoverageAnalysis]: Checked inductivity of 289 backedges. 256 proven. 27 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-19 15:00:12,390 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:00:12,390 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [484658956] [2024-11-19 15:00:12,390 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [484658956] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:00:12,391 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2067559390] [2024-11-19 15:00:12,391 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 15:00:12,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:00:12,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:12,392 INFO L229 MonitoredProcess]: Starting monitored process 46 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 15:00:12,393 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Waiting until timeout for monitored process [2024-11-19 15:00:12,428 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 15:00:12,428 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 15:00:12,429 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-19 15:00:12,430 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:12,484 INFO L134 CoverageAnalysis]: Checked inductivity of 289 backedges. 256 proven. 27 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-19 15:00:12,485 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:00:12,675 INFO L134 CoverageAnalysis]: Checked inductivity of 289 backedges. 256 proven. 27 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-19 15:00:12,676 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2067559390] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:00:12,676 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:00:12,676 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23, 23] total 23 [2024-11-19 15:00:12,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [862167944] [2024-11-19 15:00:12,676 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:00:12,677 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-19 15:00:12,677 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:12,677 INFO L85 PathProgramCache]: Analyzing trace with hash 1955414, now seen corresponding path program 3 times [2024-11-19 15:00:12,677 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:00:12,677 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2130958214] [2024-11-19 15:00:12,677 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 15:00:12,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:00:12,680 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2024-11-19 15:00:12,680 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:00:12,680 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:00:12,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:00:12,682 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:00:12,726 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:12,726 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:12,726 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:12,726 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:12,726 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 15:00:12,726 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:12,726 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:12,726 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:12,727 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration6_Loop [2024-11-19 15:00:12,727 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:12,727 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:12,727 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:12,732 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:12,738 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:12,740 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:12,772 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:12,772 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 15:00:12,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:12,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:12,778 INFO L229 MonitoredProcess]: Starting monitored process 47 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-19 15:00:12,780 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2024-11-19 15:00:12,780 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:12,780 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:12,791 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 15:00:12,791 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 15:00:12,801 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2024-11-19 15:00:12,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:12,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:12,802 INFO L229 MonitoredProcess]: Starting monitored process 48 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-19 15:00:12,803 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Waiting until timeout for monitored process [2024-11-19 15:00:12,804 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 15:00:12,804 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:12,832 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Ended with exit code 0 [2024-11-19 15:00:12,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:12,833 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:12,834 INFO L229 MonitoredProcess]: Starting monitored process 49 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-19 15:00:12,834 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Waiting until timeout for monitored process [2024-11-19 15:00:12,835 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 15:00:12,835 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 15:00:13,514 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 15:00:13,519 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Ended with exit code 0 [2024-11-19 15:00:13,519 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 15:00:13,519 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 15:00:13,519 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 15:00:13,519 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 15:00:13,519 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 15:00:13,519 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:13,519 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 15:00:13,519 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 15:00:13,519 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration6_Loop [2024-11-19 15:00:13,519 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 15:00:13,519 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 15:00:13,520 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:13,522 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:13,527 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:13,529 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 15:00:13,556 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 15:00:13,556 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 15:00:13,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:13,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:13,558 INFO L229 MonitoredProcess]: Starting monitored process 50 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-19 15:00:13,559 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Waiting until timeout for monitored process [2024-11-19 15:00:13,559 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-19 15:00:13,569 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:13,570 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:13,570 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:13,570 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:13,570 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:13,570 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:13,570 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:13,571 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 15:00:13,582 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Ended with exit code 0 [2024-11-19 15:00:13,583 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:13,583 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:13,584 INFO L229 MonitoredProcess]: Starting monitored process 51 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-19 15:00:13,585 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Waiting until timeout for monitored process [2024-11-19 15:00:13,585 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-19 15:00:13,595 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 15:00:13,595 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 15:00:13,595 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 15:00:13,595 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 15:00:13,595 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 15:00:13,598 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 15:00:13,598 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 15:00:13,600 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 15:00:13,603 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 15:00:13,603 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-19 15:00:13,604 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:00:13,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:00:13,605 INFO L229 MonitoredProcess]: Starting monitored process 52 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-19 15:00:13,606 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (52)] Waiting until timeout for monitored process [2024-11-19 15:00:13,606 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 15:00:13,606 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 15:00:13,606 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 15:00:13,606 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-19 15:00:13,616 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Ended with exit code 0 [2024-11-19 15:00:13,617 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 15:00:13,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:13,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:13,677 INFO L255 TraceCheckSpWp]: Trace formula consists of 497 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-19 15:00:13,679 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:13,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:13,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 15:00:13,771 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:13,798 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-19 15:00:13,799 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-19 15:00:13,799 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 689 states and 950 transitions. cyclomatic complexity: 268 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:13,837 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 689 states and 950 transitions. cyclomatic complexity: 268. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 714 states and 976 transitions. Complement of second has 18 states. [2024-11-19 15:00:13,837 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-19 15:00:13,838 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:13,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-19 15:00:13,838 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 56 letters. Loop has 4 letters. [2024-11-19 15:00:13,839 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:13,839 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 15:00:13,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:00:13,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:13,904 INFO L255 TraceCheckSpWp]: Trace formula consists of 497 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-19 15:00:13,906 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:14,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:00:14,020 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 15:00:14,021 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:00:14,028 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (52)] Ended with exit code 0 [2024-11-19 15:00:14,053 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-19 15:00:14,054 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-19 15:00:14,054 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 689 states and 950 transitions. cyclomatic complexity: 268 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:14,123 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 689 states and 950 transitions. cyclomatic complexity: 268. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 934 states and 1293 transitions. Complement of second has 22 states. [2024-11-19 15:00:14,124 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-19 15:00:14,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:14,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-19 15:00:14,124 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-11-19 15:00:14,125 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:14,125 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 60 letters. Loop has 4 letters. [2024-11-19 15:00:14,125 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:14,125 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 8 letters. [2024-11-19 15:00:14,125 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 15:00:14,125 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 934 states and 1293 transitions. [2024-11-19 15:00:14,134 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 42 [2024-11-19 15:00:14,142 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 934 states to 861 states and 1212 transitions. [2024-11-19 15:00:14,142 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 273 [2024-11-19 15:00:14,143 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 301 [2024-11-19 15:00:14,143 INFO L73 IsDeterministic]: Start isDeterministic. Operand 861 states and 1212 transitions. [2024-11-19 15:00:14,143 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 15:00:14,143 INFO L218 hiAutomatonCegarLoop]: Abstraction has 861 states and 1212 transitions. [2024-11-19 15:00:14,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 861 states and 1212 transitions. [2024-11-19 15:00:14,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 861 to 841. [2024-11-19 15:00:14,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 841 states, 535 states have (on average 1.1102803738317757) internal successors, (594), 570 states have internal predecessors, (594), 191 states have call successors, (221), 112 states have call predecessors, (221), 115 states have return successors, (373), 158 states have call predecessors, (373), 179 states have call successors, (373) [2024-11-19 15:00:14,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 841 states to 841 states and 1188 transitions. [2024-11-19 15:00:14,164 INFO L240 hiAutomatonCegarLoop]: Abstraction has 841 states and 1188 transitions. [2024-11-19 15:00:14,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:00:14,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-19 15:00:14,164 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=373, Unknown=0, NotChecked=0, Total=506 [2024-11-19 15:00:14,165 INFO L87 Difference]: Start difference. First operand 841 states and 1188 transitions. Second operand has 23 states, 22 states have (on average 1.7272727272727273) internal successors, (38), 13 states have internal predecessors, (38), 11 states have call successors, (12), 12 states have call predecessors, (12), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:00:14,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:00:14,437 INFO L93 Difference]: Finished difference Result 535 states and 633 transitions. [2024-11-19 15:00:14,437 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 535 states and 633 transitions. [2024-11-19 15:00:14,442 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 15:00:14,442 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 535 states to 0 states and 0 transitions. [2024-11-19 15:00:14,443 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-19 15:00:14,443 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-19 15:00:14,443 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-19 15:00:14,443 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 15:00:14,443 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 15:00:14,443 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 15:00:14,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-19 15:00:14,444 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 15:00:14,444 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-19 15:00:14,444 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-19 15:00:14,444 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 15:00:14,444 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-19 15:00:14,451 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 19.11 03:00:14 BoogieIcfgContainer [2024-11-19 15:00:14,451 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-19 15:00:14,451 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-19 15:00:14,451 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-19 15:00:14,452 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-19 15:00:14,452 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 03:00:04" (3/4) ... [2024-11-19 15:00:14,454 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-19 15:00:14,455 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-19 15:00:14,455 INFO L158 Benchmark]: Toolchain (without parser) took 10320.04ms. Allocated memory was 155.2MB in the beginning and 224.4MB in the end (delta: 69.2MB). Free memory was 119.7MB in the beginning and 137.6MB in the end (delta: -17.9MB). Peak memory consumption was 49.9MB. Max. memory is 16.1GB. [2024-11-19 15:00:14,455 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 155.2MB. Free memory is still 122.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 15:00:14,455 INFO L158 Benchmark]: CACSL2BoogieTranslator took 195.95ms. Allocated memory is still 155.2MB. Free memory was 119.7MB in the beginning and 107.8MB in the end (delta: 11.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-19 15:00:14,456 INFO L158 Benchmark]: Boogie Procedure Inliner took 36.34ms. Allocated memory is still 155.2MB. Free memory was 107.8MB in the beginning and 106.5MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 15:00:14,456 INFO L158 Benchmark]: Boogie Preprocessor took 29.15ms. Allocated memory is still 155.2MB. Free memory was 106.5MB in the beginning and 105.0MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 15:00:14,456 INFO L158 Benchmark]: RCFGBuilder took 235.27ms. Allocated memory is still 155.2MB. Free memory was 105.0MB in the beginning and 120.3MB in the end (delta: -15.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-19 15:00:14,456 INFO L158 Benchmark]: BuchiAutomizer took 9816.23ms. Allocated memory was 155.2MB in the beginning and 224.4MB in the end (delta: 69.2MB). Free memory was 120.3MB in the beginning and 137.6MB in the end (delta: -17.2MB). Peak memory consumption was 52.7MB. Max. memory is 16.1GB. [2024-11-19 15:00:14,456 INFO L158 Benchmark]: Witness Printer took 3.33ms. Allocated memory is still 224.4MB. Free memory is still 137.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 15:00:14,457 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.18ms. Allocated memory is still 155.2MB. Free memory is still 122.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 195.95ms. Allocated memory is still 155.2MB. Free memory was 119.7MB in the beginning and 107.8MB in the end (delta: 11.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 36.34ms. Allocated memory is still 155.2MB. Free memory was 107.8MB in the beginning and 106.5MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 29.15ms. Allocated memory is still 155.2MB. Free memory was 106.5MB in the beginning and 105.0MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 235.27ms. Allocated memory is still 155.2MB. Free memory was 105.0MB in the beginning and 120.3MB in the end (delta: -15.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 9816.23ms. Allocated memory was 155.2MB in the beginning and 224.4MB in the end (delta: 69.2MB). Free memory was 120.3MB in the beginning and 137.6MB in the end (delta: -17.2MB). Peak memory consumption was 52.7MB. Max. memory is 16.1GB. * Witness Printer took 3.33ms. Allocated memory is still 224.4MB. Free memory is still 137.6MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 10 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 9.7s and 7 iterations. TraceHistogramMax:13. Analysis of lassos took 5.1s. Construction of modules took 0.9s. Büchi inclusion checks took 3.4s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 248 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 0/6 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 534 SdHoareTripleChecker+Valid, 1.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 510 mSDsluCounter, 689 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 456 mSDsCounter, 315 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1503 IncrementalHoareTripleChecker+Invalid, 1818 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 315 mSolverCounterUnsat, 233 mSDtfsCounter, 1503 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI1 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp82 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf92 smp80 dnf100 smp100 tf112 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 20ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 12 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.1s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-19 15:00:14,479 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Ended with exit code 0 [2024-11-19 15:00:14,682 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Ended with exit code 0 [2024-11-19 15:00:14,882 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-19 15:00:15,083 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-19 15:00:15,284 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