./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_5-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 8be7027f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-simple/fibo_5-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 2199d5dae92fc703178378f6dd7dec10a5f129181c51bc9a88c002f6d4f76a67 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dk.perfect-tracechecks-8be7027-m [2024-11-12 21:42:39,324 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-12 21:42:39,407 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-12 21:42:39,414 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-12 21:42:39,415 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-12 21:42:39,445 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-12 21:42:39,447 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-12 21:42:39,447 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-12 21:42:39,448 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-12 21:42:39,449 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-12 21:42:39,450 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-12 21:42:39,451 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-12 21:42:39,451 INFO L153 SettingsManager]: * Use SBE=true [2024-11-12 21:42:39,453 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-12 21:42:39,453 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-12 21:42:39,453 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-12 21:42:39,453 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-12 21:42:39,454 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-12 21:42:39,454 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-12 21:42:39,457 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-12 21:42:39,458 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-12 21:42:39,458 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-12 21:42:39,458 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-12 21:42:39,459 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-12 21:42:39,459 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-12 21:42:39,459 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-12 21:42:39,459 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-12 21:42:39,460 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-12 21:42:39,460 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-12 21:42:39,460 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-12 21:42:39,460 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-12 21:42:39,461 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-12 21:42:39,461 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-12 21:42:39,461 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-12 21:42:39,461 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-12 21:42:39,461 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-12 21:42:39,462 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-12 21:42:39,462 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-12 21:42:39,463 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-12 21:42:39,463 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 2199d5dae92fc703178378f6dd7dec10a5f129181c51bc9a88c002f6d4f76a67 [2024-11-12 21:42:39,702 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-12 21:42:39,727 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-12 21:42:39,730 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-12 21:42:39,731 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-12 21:42:39,731 INFO L274 PluginConnector]: CDTParser initialized [2024-11-12 21:42:39,732 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_5-1.c [2024-11-12 21:42:41,100 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-12 21:42:41,327 INFO L384 CDTParser]: Found 1 translation units. [2024-11-12 21:42:41,328 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c [2024-11-12 21:42:41,334 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/57adda319/47641f14735243efba8e92f7daa6d33c/FLAGfe4aadc34 [2024-11-12 21:42:41,719 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/57adda319/47641f14735243efba8e92f7daa6d33c [2024-11-12 21:42:41,721 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-12 21:42:41,722 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-12 21:42:41,723 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-12 21:42:41,723 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-12 21:42:41,729 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-12 21:42:41,730 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,731 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@596af6b8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41, skipping insertion in model container [2024-11-12 21:42:41,731 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,751 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-12 21:42:41,910 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-12 21:42:41,920 INFO L200 MainTranslator]: Completed pre-run [2024-11-12 21:42:41,931 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-12 21:42:41,944 INFO L204 MainTranslator]: Completed translation [2024-11-12 21:42:41,944 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41 WrapperNode [2024-11-12 21:42:41,944 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-12 21:42:41,945 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-12 21:42:41,946 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-12 21:42:41,946 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-12 21:42:41,951 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,956 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,972 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-12 21:42:41,974 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-12 21:42:41,975 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-12 21:42:41,975 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-12 21:42:41,975 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-12 21:42:41,983 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,984 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,984 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,992 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-12 21:42:41,992 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,992 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,994 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,995 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,996 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,997 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:41,998 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-12 21:42:41,999 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-12 21:42:41,999 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-12 21:42:41,999 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-12 21:42:41,999 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (1/1) ... [2024-11-12 21:42:42,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:42,031 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-12 21:42:42,038 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-12 21:42:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-12 21:42:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-12 21:42:42,085 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-12 21:42:42,085 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-12 21:42:42,085 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-12 21:42:42,085 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-12 21:42:42,145 INFO L238 CfgBuilder]: Building ICFG [2024-11-12 21:42:42,147 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-12 21:42:42,258 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-12 21:42:42,258 INFO L287 CfgBuilder]: Performing block encoding [2024-11-12 21:42:42,271 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-12 21:42:42,271 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-12 21:42:42,272 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 09:42:42 BoogieIcfgContainer [2024-11-12 21:42:42,272 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-12 21:42:42,273 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-12 21:42:42,274 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-12 21:42:42,278 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-12 21:42:42,279 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-12 21:42:42,279 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 12.11 09:42:41" (1/3) ... [2024-11-12 21:42:42,280 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@579f4bd4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 12.11 09:42:42, skipping insertion in model container [2024-11-12 21:42:42,280 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-12 21:42:42,280 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 09:42:41" (2/3) ... [2024-11-12 21:42:42,282 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@579f4bd4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 12.11 09:42:42, skipping insertion in model container [2024-11-12 21:42:42,282 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-12 21:42:42,282 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 09:42:42" (3/3) ... [2024-11-12 21:42:42,283 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_5-1.c [2024-11-12 21:42:42,338 INFO L301 stractBuchiCegarLoop]: Interprodecural is true [2024-11-12 21:42:42,339 INFO L302 stractBuchiCegarLoop]: Hoare is None [2024-11-12 21:42:42,339 INFO L303 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-12 21:42:42,339 INFO L304 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-12 21:42:42,340 INFO L305 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-12 21:42:42,340 INFO L306 stractBuchiCegarLoop]: Difference is false [2024-11-12 21:42:42,340 INFO L307 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-12 21:42:42,341 INFO L311 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-12 21:42:42,345 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-12 21:42:42,367 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-12 21:42:42,368 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-12 21:42:42,368 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-12 21:42:42,374 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-12 21:42:42,374 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-12 21:42:42,375 INFO L333 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-12 21:42:42,375 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-12 21:42:42,378 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-12 21:42:42,378 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-12 21:42:42,378 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-12 21:42:42,378 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-12 21:42:42,378 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-12 21:42:42,386 INFO L747 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< [2024-11-12 21:42:42,386 INFO L749 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< [2024-11-12 21:42:42,393 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:42,393 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-11-12 21:42:42,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:42,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [989025619] [2024-11-12 21:42:42,401 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:42,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:42,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:42,474 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:42,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:42,503 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:42,506 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:42,506 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-11-12 21:42:42,507 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:42,507 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1719059587] [2024-11-12 21:42:42,507 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:42,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:42,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:42,518 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:42,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:42,522 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:42,524 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:42,524 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-11-12 21:42:42,525 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:42,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [229815935] [2024-11-12 21:42:42,525 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:42,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:42,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:42,543 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:42,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:42,558 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:42,678 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:42,679 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:42,679 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:42,679 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:42,679 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-12 21:42:42,679 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,679 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:42,679 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:42,679 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2024-11-12 21:42:42,680 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:42,680 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:42,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:42,700 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:42,703 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:42,711 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:42,721 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:42,796 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:42,796 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-12 21:42:42,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,799 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:42,801 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-12 21:42:42,802 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-12 21:42:42,804 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:42,804 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:42,823 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:42,824 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-12 21:42:42,842 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-12 21:42:42,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:42,845 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-12 21:42:42,847 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-12 21:42:42,849 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:42,849 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:42,863 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:42,863 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-12 21:42:42,879 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-12 21:42:42,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:42,882 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-12 21:42:42,884 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-12 21:42:42,885 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:42,886 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:42,898 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:42,898 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-12 21:42:42,910 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-12 21:42:42,911 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,911 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:42,914 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-12 21:42:42,915 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-12 21:42:42,916 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:42,916 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:42,939 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:42,940 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:42,940 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:42,941 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-12 21:42:42,942 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-12 21:42:42,943 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-12 21:42:42,943 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:43,019 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-12 21:42:43,024 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:43,025 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:43,025 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:43,025 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:43,025 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:43,025 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-12 21:42:43,025 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:43,026 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:43,026 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:43,026 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2024-11-12 21:42:43,038 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:43,038 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:43,043 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:43,048 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:43,052 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:43,057 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:43,066 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:43,138 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:43,142 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-12 21:42:43,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:43,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:43,145 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-12 21:42:43,147 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-12 21:42:43,148 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-12 21:42:43,158 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:43,159 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:43,159 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:43,160 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:43,160 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:43,161 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:43,162 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:43,166 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:43,179 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:43,180 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:43,180 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:43,181 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-12 21:42:43,182 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-12 21:42:43,184 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-12 21:42:43,194 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:43,194 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:43,194 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:43,194 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:43,194 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:43,195 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:43,195 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:43,197 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:43,208 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-12 21:42:43,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:43,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:43,211 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-12 21:42:43,212 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-12 21:42:43,212 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-12 21:42:43,222 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:43,223 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:43,223 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:43,223 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:43,223 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:43,224 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:43,224 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:43,226 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:43,237 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-12 21:42:43,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:43,238 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:43,239 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-12 21:42:43,240 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-12 21:42:43,241 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-12 21:42:43,251 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:43,251 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:43,251 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:43,251 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:43,251 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:43,252 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:43,252 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:43,256 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-12 21:42:43,261 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-12 21:42:43,261 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-12 21:42:43,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:43,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:43,281 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-12 21:42:43,282 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-12 21:42:43,283 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-12 21:42:43,283 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-12 21:42:43,283 INFO L474 LassoAnalysis]: Proved termination. [2024-11-12 21:42:43,284 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-12 21:42:43,294 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-12 21:42:43,297 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-12 21:42:43,327 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:43,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:43,352 INFO L256 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-12 21:42:43,353 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:43,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:43,373 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-12 21:42:43,374 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:43,418 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-12 21:42:43,453 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-12 21:42:43,455 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-12 21:42:43,543 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-12 21:42:43,545 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-12 21:42:43,549 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-12 21:42:43,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-12 21:42:43,551 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-12 21:42:43,552 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:43,552 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-12 21:42:43,552 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:43,552 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-12 21:42:43,552 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:43,553 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-12 21:42:43,556 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-12 21:42:43,560 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-12 21:42:43,561 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-12 21:42:43,561 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-12 21:42:43,562 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-12 21:42:43,563 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-12 21:42:43,563 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-12 21:42:43,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-12 21:42:43,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-12 21:42:43,582 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-12 21:42:43,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-12 21:42:43,584 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-12 21:42:43,584 INFO L426 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-12 21:42:43,584 INFO L333 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-12 21:42:43,584 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-12 21:42:43,585 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-12 21:42:43,585 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-12 21:42:43,585 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-12 21:42:43,586 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:43,586 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:43,587 INFO L747 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#35#return;" [2024-11-12 21:42:43,587 INFO L749 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#35#return;" [2024-11-12 21:42:43,587 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:43,587 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-11-12 21:42:43,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:43,588 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [119747648] [2024-11-12 21:42:43,588 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:43,588 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:43,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:43,727 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-12 21:42:43,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:43,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-12 21:42:43,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [119747648] [2024-11-12 21:42:43,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [119747648] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-12 21:42:43,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [862917107] [2024-11-12 21:42:43,775 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:43,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-12 21:42:43,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:43,780 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-12 21:42:43,782 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-12 21:42:43,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:43,816 INFO L256 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-12 21:42:43,817 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:43,885 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-12 21:42:43,982 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [862917107] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-12 21:42:43,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-12 21:42:43,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6, 6] total 12 [2024-11-12 21:42:43,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1911121804] [2024-11-12 21:42:43,984 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-12 21:42:43,986 INFO L752 eck$LassoCheckResult]: stem already infeasible [2024-11-12 21:42:43,986 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:43,987 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-11-12 21:42:43,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:43,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [23621995] [2024-11-12 21:42:43,987 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:43,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:43,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:44,021 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-12 21:42:44,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:44,066 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-12 21:42:44,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [23621995] [2024-11-12 21:42:44,067 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [23621995] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-12 21:42:44,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1715675225] [2024-11-12 21:42:44,067 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:44,067 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-12 21:42:44,068 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:44,070 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-12 21:42:44,071 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-12 21:42:44,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:44,106 INFO L256 TraceCheckSpWp]: Trace formula consists of 22 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-12 21:42:44,107 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:44,154 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-12 21:42:44,223 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1715675225] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-12 21:42:44,224 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-12 21:42:44,224 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 7 [2024-11-12 21:42:44,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1016483860] [2024-11-12 21:42:44,224 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-12 21:42:44,225 INFO L764 eck$LassoCheckResult]: loop already infeasible [2024-11-12 21:42:44,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-12 21:42:44,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-12 21:42:44,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-12 21:42:44,232 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 7 states have internal predecessors, (10), 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-12 21:42:44,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-12 21:42:44,304 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-12 21:42:44,304 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-12 21:42:44,305 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-12 21:42:44,308 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-12 21:42:44,309 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-12 21:42:44,310 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-12 21:42:44,310 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-12 21:42:44,310 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-12 21:42:44,310 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-12 21:42:44,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-12 21:42:44,313 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-12 21:42:44,314 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-12 21:42:44,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-12 21:42:44,315 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-12 21:42:44,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-12 21:42:44,316 INFO L426 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-12 21:42:44,317 INFO L333 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-12 21:42:44,317 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-12 21:42:44,318 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-12 21:42:44,319 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-12 21:42:44,319 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-12 21:42:44,319 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:44,319 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:44,320 INFO L747 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#35#return;" [2024-11-12 21:42:44,320 INFO L749 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#35#return;" [2024-11-12 21:42:44,320 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:44,321 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-11-12 21:42:44,321 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:44,321 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1639253164] [2024-11-12 21:42:44,321 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:44,321 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:44,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:44,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-12 21:42:44,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:44,418 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-12 21:42:44,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1639253164] [2024-11-12 21:42:44,419 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1639253164] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-12 21:42:44,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [540208218] [2024-11-12 21:42:44,419 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:44,419 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-12 21:42:44,419 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:44,420 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-12 21:42:44,422 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-12 21:42:44,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:44,455 INFO L256 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-12 21:42:44,457 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:44,496 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-12 21:42:44,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [540208218] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-12 21:42:44,610 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-12 21:42:44,610 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-12 21:42:44,610 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1660930042] [2024-11-12 21:42:44,610 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-12 21:42:44,611 INFO L752 eck$LassoCheckResult]: stem already infeasible [2024-11-12 21:42:44,611 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:44,611 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-11-12 21:42:44,611 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:44,611 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1589600624] [2024-11-12 21:42:44,611 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:44,611 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:44,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:44,623 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:44,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:44,630 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:44,756 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:44,756 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:44,757 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:44,757 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:44,757 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-12 21:42:44,757 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:44,757 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:44,757 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:44,757 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2024-11-12 21:42:44,757 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:44,757 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:44,758 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,762 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,767 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,774 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,776 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,814 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:44,815 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-12 21:42:44,815 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:44,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:44,818 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-12 21:42:44,819 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-12 21:42:44,820 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:44,820 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:44,832 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:44,833 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-12 21:42:44,843 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-12 21:42:44,844 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:44,844 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:44,845 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-12 21:42:44,847 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-12 21:42:44,847 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:44,848 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:44,873 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-12 21:42:44,874 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:44,874 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:44,875 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-12 21:42:44,877 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-12 21:42:44,878 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-12 21:42:44,878 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:44,894 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-12 21:42:44,910 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-12 21:42:44,910 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:44,910 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:44,910 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:44,910 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:44,910 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-12 21:42:44,911 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:44,911 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:44,911 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:44,911 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2024-11-12 21:42:44,911 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:44,911 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:44,912 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,917 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,925 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,927 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,929 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:44,967 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:44,967 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-12 21:42:44,967 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:44,967 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:44,971 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-12 21:42:44,972 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-12 21:42:44,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-12 21:42:44,986 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:44,986 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:44,986 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:44,986 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:44,986 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:44,987 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:44,987 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:44,989 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:45,003 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-12 21:42:45,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:45,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:45,007 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-12 21:42:45,009 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-12 21:42:45,009 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-12 21:42:45,022 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:45,022 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:45,022 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:45,023 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:45,023 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:45,024 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:45,024 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:45,027 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-12 21:42:45,029 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-12 21:42:45,030 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-12 21:42:45,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:45,030 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:45,034 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-12 21:42:45,037 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-12 21:42:45,038 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-12 21:42:45,038 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-12 21:42:45,038 INFO L474 LassoAnalysis]: Proved termination. [2024-11-12 21:42:45,038 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-12 21:42:45,053 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-12 21:42:45,054 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-12 21:42:45,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:45,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,089 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-12 21:42:45,090 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:45,131 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-12 21:42:45,145 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-12 21:42:45,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,224 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-12 21:42:45,225 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:45,307 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-12 21:42:45,308 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-12 21:42:45,308 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-12 21:42:45,501 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-12 21:42:45,501 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-12 21:42:45,502 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-12 21:42:45,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-12 21:42:45,503 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-11-12 21:42:45,503 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:45,503 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-11-12 21:42:45,504 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:45,504 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-11-12 21:42:45,504 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:45,504 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-11-12 21:42:45,509 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-12 21:42:45,514 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-11-12 21:42:45,516 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-11-12 21:42:45,517 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-11-12 21:42:45,517 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-11-12 21:42:45,517 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-12 21:42:45,517 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-11-12 21:42:45,517 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-11-12 21:42:45,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-11-12 21:42:45,535 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-12 21:42:45,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-11-12 21:42:45,538 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-11-12 21:42:45,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-12 21:42:45,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-12 21:42:45,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-12 21:42:45,540 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-12 21:42:45,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-12 21:42:45,662 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-11-12 21:42:45,662 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-11-12 21:42:45,668 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-12 21:42:45,671 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-11-12 21:42:45,673 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-12 21:42:45,673 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-12 21:42:45,673 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-11-12 21:42:45,674 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-12 21:42:45,674 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-11-12 21:42:45,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-11-12 21:42:45,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-11-12 21:42:45,689 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-12 21:42:45,691 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-11-12 21:42:45,691 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-12 21:42:45,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-12 21:42:45,694 INFO L426 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-12 21:42:45,694 INFO L333 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-12 21:42:45,694 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-11-12 21:42:45,696 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-12 21:42:45,697 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-12 21:42:45,698 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-12 21:42:45,700 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:45,701 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:45,701 INFO L747 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#35#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#37#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#35#return;" [2024-11-12 21:42:45,701 INFO L749 eck$LassoCheckResult]: Loop: "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#35#return;" [2024-11-12 21:42:45,702 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:45,702 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-11-12 21:42:45,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:45,702 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635577931] [2024-11-12 21:42:45,702 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:45,702 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:45,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:45,727 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:45,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:45,738 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:45,738 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:45,739 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 2 times [2024-11-12 21:42:45,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:45,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [498543689] [2024-11-12 21:42:45,739 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:45,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:45,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:45,743 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:45,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:45,746 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:45,746 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:45,746 INFO L85 PathProgramCache]: Analyzing trace with hash -1521208943, now seen corresponding path program 2 times [2024-11-12 21:42:45,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:45,747 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1230854164] [2024-11-12 21:42:45,747 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:45,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:45,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,922 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-12 21:42:45,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,932 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-12 21:42:45,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,934 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-12 21:42:45,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,936 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-12 21:42:45,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:45,939 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-12 21:42:45,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1230854164] [2024-11-12 21:42:45,939 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1230854164] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-12 21:42:45,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [353895890] [2024-11-12 21:42:45,940 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-12 21:42:45,940 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-12 21:42:45,940 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:45,941 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-12 21:42:45,943 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-12 21:42:45,978 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-12 21:42:45,978 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-12 21:42:45,978 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-11-12 21:42:45,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [357186476] [2024-11-12 21:42:45,978 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-12 21:42:46,064 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:46,064 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:46,064 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:46,064 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:46,065 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-12 21:42:46,065 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,065 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:46,065 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:46,065 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration4_Loop [2024-11-12 21:42:46,065 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:46,065 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:46,065 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,068 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,071 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,073 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,075 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,111 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:46,112 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-12 21:42:46,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,114 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-12 21:42:46,115 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-12 21:42:46,116 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:46,116 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:46,131 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:46,132 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-12 21:42:46,147 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-11-12 21:42:46,148 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,148 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,150 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-12 21:42:46,152 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-12 21:42:46,153 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:46,153 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:46,170 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:46,170 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-12 21:42:46,184 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,186 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-12 21:42:46,187 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-12 21:42:46,187 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:46,187 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:46,202 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:46,202 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-12 21:42:46,218 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,218 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,220 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-12 21:42:46,221 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-12 21:42:46,222 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:46,222 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:46,238 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:46,238 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-12 21:42:46,253 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,255 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,256 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-12 21:42:46,258 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-12 21:42:46,258 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:46,258 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:46,284 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-11-12 21:42:46,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,286 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-12 21:42:46,287 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-12 21:42:46,288 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-12 21:42:46,288 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:46,301 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-12 21:42:46,312 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,312 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:46,312 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:46,312 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:46,312 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:46,312 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-12 21:42:46,312 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,312 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:46,313 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:46,313 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration4_Loop [2024-11-12 21:42:46,313 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:46,313 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:46,313 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,316 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,318 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,321 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,322 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:46,364 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:46,364 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-12 21:42:46,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,368 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-12 21:42:46,372 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-12 21:42:46,376 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-12 21:42:46,385 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:46,385 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:46,385 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:46,385 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:46,385 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:46,385 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:46,385 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:46,387 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:46,401 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,402 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,403 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-12 21:42:46,404 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-12 21:42:46,405 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-12 21:42:46,419 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:46,420 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:46,420 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:46,420 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:46,420 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:46,421 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:46,421 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:46,425 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:46,439 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-12 21:42:46,440 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,441 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-12 21:42:46,443 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-12 21:42:46,443 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-12 21:42:46,454 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:46,454 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:46,454 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:46,454 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:46,454 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:46,455 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:46,455 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:46,457 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:46,466 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,467 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,468 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-12 21:42:46,469 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-12 21:42:46,469 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-12 21:42:46,479 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:46,479 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:46,479 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:46,479 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:46,479 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:46,480 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:46,480 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:46,481 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:46,495 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:46,496 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,497 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-12 21:42:46,499 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-12 21:42:46,500 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-12 21:42:46,512 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:46,512 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:46,513 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:46,513 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:46,513 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:46,515 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:46,515 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:46,517 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-12 21:42:46,519 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-12 21:42:46,519 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-12 21:42:46,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:46,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:46,522 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-12 21:42:46,523 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-12 21:42:46,523 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-12 21:42:46,523 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-12 21:42:46,524 INFO L474 LassoAnalysis]: Proved termination. [2024-11-12 21:42:46,524 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-12 21:42:46,538 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-12 21:42:46,539 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-12 21:42:46,553 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:46,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:46,594 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-12 21:42:46,595 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:46,737 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2024-11-12 21:42:46,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:46,826 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-12 21:42:46,827 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:46,899 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-12 21:42:46,900 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-12 21:42:46,900 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-12 21:42:47,090 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-12 21:42:47,092 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-12 21:42:47,093 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-12 21:42:47,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-12 21:42:47,094 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-12 21:42:47,094 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:47,095 INFO L683 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-12 21:42:47,107 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:47,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:47,149 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-12 21:42:47,151 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:47,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:47,332 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-12 21:42:47,333 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:47,408 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-12 21:42:47,409 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-12 21:42:47,409 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-12 21:42:47,573 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-12 21:42:47,574 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-12 21:42:47,574 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-12 21:42:47,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-11-12 21:42:47,575 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-12 21:42:47,575 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:47,575 INFO L683 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-12 21:42:47,585 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:47,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:47,624 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-12 21:42:47,626 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:47,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:47,797 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-12 21:42:47,798 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:47,869 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-12 21:42:47,870 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-12 21:42:47,870 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-12 21:42:48,101 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-12 21:42:48,102 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-12 21:42:48,102 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-12 21:42:48,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-11-12 21:42:48,103 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-11-12 21:42:48,103 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:48,103 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-11-12 21:42:48,104 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:48,104 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-11-12 21:42:48,105 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:48,106 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 817 states and 1129 transitions. [2024-11-12 21:42:48,121 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-11-12 21:42:48,134 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 817 states to 418 states and 629 transitions. [2024-11-12 21:42:48,135 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 162 [2024-11-12 21:42:48,136 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 182 [2024-11-12 21:42:48,136 INFO L73 IsDeterministic]: Start isDeterministic. Operand 418 states and 629 transitions. [2024-11-12 21:42:48,136 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-12 21:42:48,136 INFO L218 hiAutomatonCegarLoop]: Abstraction has 418 states and 629 transitions. [2024-11-12 21:42:48,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 418 states and 629 transitions. [2024-11-12 21:42:48,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 418 to 356. [2024-11-12 21:42:48,175 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-12 21:42:48,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 356 states to 356 states and 493 transitions. [2024-11-12 21:42:48,178 INFO L240 hiAutomatonCegarLoop]: Abstraction has 356 states and 493 transitions. [2024-11-12 21:42:48,178 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-12 21:42:48,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-12 21:42:48,179 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=95, Unknown=0, NotChecked=0, Total=132 [2024-11-12 21:42:48,179 INFO L87 Difference]: Start difference. First operand 356 states and 493 transitions. Second operand has 12 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (8), 5 states have call predecessors, (8), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-12 21:42:48,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-12 21:42:48,310 INFO L93 Difference]: Finished difference Result 139 states and 169 transitions. [2024-11-12 21:42:48,310 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 139 states and 169 transitions. [2024-11-12 21:42:48,312 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-12 21:42:48,313 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 139 states to 137 states and 165 transitions. [2024-11-12 21:42:48,314 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2024-11-12 21:42:48,315 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 97 [2024-11-12 21:42:48,317 INFO L73 IsDeterministic]: Start isDeterministic. Operand 137 states and 165 transitions. [2024-11-12 21:42:48,317 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-12 21:42:48,317 INFO L218 hiAutomatonCegarLoop]: Abstraction has 137 states and 165 transitions. [2024-11-12 21:42:48,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states and 165 transitions. [2024-11-12 21:42:48,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 104. [2024-11-12 21:42:48,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 70 states have (on average 1.1142857142857143) internal successors, (78), 70 states have internal predecessors, (78), 20 states have call successors, (24), 16 states have call predecessors, (24), 14 states have return successors, (22), 17 states have call predecessors, (22), 17 states have call successors, (22) [2024-11-12 21:42:48,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 124 transitions. [2024-11-12 21:42:48,330 INFO L240 hiAutomatonCegarLoop]: Abstraction has 104 states and 124 transitions. [2024-11-12 21:42:48,330 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-12 21:42:48,331 INFO L426 stractBuchiCegarLoop]: Abstraction has 104 states and 124 transitions. [2024-11-12 21:42:48,331 INFO L333 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-12 21:42:48,331 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 104 states and 124 transitions. [2024-11-12 21:42:48,331 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-12 21:42:48,331 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-12 21:42:48,332 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-12 21:42:48,332 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 6, 5, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-12 21:42:48,332 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-12 21:42:48,332 INFO L747 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5;" "call main_#t~ret6#1 := fibo(main_~x~0#1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume 1 == ~n;#res := 1;" "assume true;" >"#35#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume ~n < 1;#res := 0;" "assume true;" >"#37#return;" "#res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#35#return;" "call #t~ret5 := fibo(~n - 2);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< [2024-11-12 21:42:48,333 INFO L749 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n < 1);" "assume !(1 == ~n);" "call #t~ret4 := fibo(~n - 1);"< [2024-11-12 21:42:48,333 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:48,333 INFO L85 PathProgramCache]: Analyzing trace with hash 977790313, now seen corresponding path program 3 times [2024-11-12 21:42:48,333 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:48,333 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1874215942] [2024-11-12 21:42:48,333 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:48,333 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:48,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:48,426 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-12 21:42:48,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:48,474 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-12 21:42:48,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:48,492 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-12 21:42:48,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:48,497 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-12 21:42:48,497 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1874215942] [2024-11-12 21:42:48,497 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1874215942] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-12 21:42:48,497 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [322014066] [2024-11-12 21:42:48,497 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-12 21:42:48,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-12 21:42:48,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,499 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-12 21:42:48,500 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-12 21:42:48,531 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-12 21:42:48,532 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-12 21:42:48,532 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2024-11-12 21:42:48,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [750531738] [2024-11-12 21:42:48,532 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-12 21:42:48,532 INFO L752 eck$LassoCheckResult]: stem already infeasible [2024-11-12 21:42:48,533 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:48,533 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 2 times [2024-11-12 21:42:48,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-12 21:42:48,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1643917849] [2024-11-12 21:42:48,533 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-12 21:42:48,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-12 21:42:48,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:48,535 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-12 21:42:48,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-12 21:42:48,537 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-12 21:42:48,569 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:48,569 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:48,569 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:48,569 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:48,570 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-12 21:42:48,570 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,570 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:48,570 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:48,570 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration5_Loop [2024-11-12 21:42:48,570 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:48,570 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:48,571 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,573 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,574 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,576 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,582 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,617 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:48,618 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-12 21:42:48,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,620 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-12 21:42:48,621 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-12 21:42:48,622 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:48,622 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:48,638 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:48,639 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-12 21:42:48,653 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:48,653 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,654 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,655 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-12 21:42:48,657 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-12 21:42:48,658 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:48,658 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:48,674 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:48,674 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-12 21:42:48,688 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:48,688 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,690 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-12 21:42:48,691 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-12 21:42:48,692 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:48,692 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:48,710 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-12 21:42:48,710 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-12 21:42:48,724 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-12 21:42:48,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,726 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-12 21:42:48,727 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-12 21:42:48,728 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-12 21:42:48,728 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:48,756 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:48,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,757 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,758 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-12 21:42:48,759 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-12 21:42:48,760 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-12 21:42:48,760 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-12 21:42:48,801 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-12 21:42:48,807 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:48,807 INFO L204 LassoAnalysis]: Preferences: [2024-11-12 21:42:48,807 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-12 21:42:48,807 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-12 21:42:48,807 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-12 21:42:48,807 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-12 21:42:48,807 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,807 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-12 21:42:48,807 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-12 21:42:48,807 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration5_Loop [2024-11-12 21:42:48,807 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-12 21:42:48,807 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-12 21:42:48,808 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,813 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,815 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,817 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,819 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-12 21:42:48,858 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-12 21:42:48,858 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-12 21:42:48,858 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,862 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-12 21:42:48,863 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-12 21:42:48,864 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-12 21:42:48,876 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:48,876 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:48,877 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:48,877 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:48,877 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:48,878 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:48,878 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:48,881 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:48,895 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Ended with exit code 0 [2024-11-12 21:42:48,895 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,895 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,897 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-12 21:42:48,898 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-12 21:42:48,899 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-12 21:42:48,910 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:48,911 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:48,911 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:48,911 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:48,911 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:48,911 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:48,911 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:48,913 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:48,927 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-12 21:42:48,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,929 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-12 21:42:48,931 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-12 21:42:48,932 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-12 21:42:48,945 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:48,945 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:48,945 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:48,945 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:48,945 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:48,946 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:48,946 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:48,949 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:48,963 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:48,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,965 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-12 21:42:48,966 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-12 21:42:48,968 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-12 21:42:48,980 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:48,981 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:48,982 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:48,982 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:48,982 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:48,982 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:48,982 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:48,984 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-12 21:42:48,994 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:48,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:48,995 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:48,996 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-12 21:42:48,996 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-12 21:42:48,997 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-12 21:42:49,007 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-12 21:42:49,007 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-12 21:42:49,008 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-12 21:42:49,008 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-12 21:42:49,008 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-12 21:42:49,009 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-12 21:42:49,009 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-12 21:42:49,011 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-12 21:42:49,013 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-12 21:42:49,013 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-12 21:42:49,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-12 21:42:49,014 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-12 21:42:49,015 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-12 21:42:49,017 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-12 21:42:49,017 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-12 21:42:49,017 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-12 21:42:49,018 INFO L474 LassoAnalysis]: Proved termination. [2024-11-12 21:42:49,018 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-12 21:42:49,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:49,029 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-12 21:42:49,042 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:49,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:49,089 INFO L256 TraceCheckSpWp]: Trace formula consists of 322 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-12 21:42:49,093 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:49,269 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:49,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:49,281 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-12 21:42:49,282 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:49,309 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-12 21:42:49,309 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-12 21:42:49,310 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 104 states and 124 transitions. cyclomatic complexity: 23 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-12 21:42:49,370 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 104 states and 124 transitions. cyclomatic complexity: 23. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 114 states and 134 transitions. Complement of second has 15 states. [2024-11-12 21:42:49,371 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-12 21:42:49,371 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-12 21:42:49,371 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-12 21:42:49,371 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 37 letters. Loop has 4 letters. [2024-11-12 21:42:49,372 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:49,372 INFO L683 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-12 21:42:49,383 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:49,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:49,435 INFO L256 TraceCheckSpWp]: Trace formula consists of 322 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-12 21:42:49,437 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:49,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:49,626 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-12 21:42:49,627 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:49,651 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-12 21:42:49,652 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-12 21:42:49,652 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 104 states and 124 transitions. cyclomatic complexity: 23 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-12 21:42:49,709 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 104 states and 124 transitions. cyclomatic complexity: 23. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 114 states and 134 transitions. Complement of second has 15 states. [2024-11-12 21:42:49,710 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-12 21:42:49,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-12 21:42:49,711 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-12 21:42:49,711 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 37 letters. Loop has 4 letters. [2024-11-12 21:42:49,711 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:49,711 INFO L683 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-12 21:42:49,722 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-12 21:42:49,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:49,772 INFO L256 TraceCheckSpWp]: Trace formula consists of 322 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-12 21:42:49,773 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:49,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-12 21:42:49,944 INFO L256 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-12 21:42:49,944 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-12 21:42:49,969 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-12 21:42:49,969 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-12 21:42:49,970 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 104 states and 124 transitions. cyclomatic complexity: 23 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-12 21:42:50,043 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 104 states and 124 transitions. cyclomatic complexity: 23. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 155 states and 177 transitions. Complement of second has 19 states. [2024-11-12 21:42:50,043 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-12 21:42:50,044 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-12 21:42:50,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-12 21:42:50,044 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 37 letters. Loop has 4 letters. [2024-11-12 21:42:50,045 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:50,045 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 41 letters. Loop has 4 letters. [2024-11-12 21:42:50,045 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:50,045 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 37 letters. Loop has 8 letters. [2024-11-12 21:42:50,046 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-12 21:42:50,046 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 155 states and 177 transitions. [2024-11-12 21:42:50,047 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-12 21:42:50,048 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 155 states to 0 states and 0 transitions. [2024-11-12 21:42:50,048 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-12 21:42:50,048 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-12 21:42:50,048 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-12 21:42:50,048 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-12 21:42:50,048 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-12 21:42:50,048 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-12 21:42:50,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-12 21:42:50,049 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-12 21:42:50,049 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2024-11-12 21:42:50,049 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-12 21:42:50,049 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-12 21:42:50,049 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-11-12 21:42:50,049 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-11-12 21:42:50,049 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-12 21:42:50,050 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-11-12 21:42:50,050 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-12 21:42:50,050 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-12 21:42:50,050 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-12 21:42:50,050 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-12 21:42:50,050 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-12 21:42:50,050 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-12 21:42:50,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-12 21:42:50,051 INFO L426 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-12 21:42:50,051 INFO L333 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-12 21:42:50,051 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-12 21:42:50,051 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-12 21:42:50,051 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-12 21:42:50,058 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 12.11 09:42:50 BoogieIcfgContainer [2024-11-12 21:42:50,058 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-12 21:42:50,059 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-12 21:42:50,059 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-12 21:42:50,060 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-12 21:42:50,060 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 09:42:42" (3/4) ... [2024-11-12 21:42:50,062 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-12 21:42:50,064 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-12 21:42:50,065 INFO L158 Benchmark]: Toolchain (without parser) took 8342.17ms. Allocated memory was 155.2MB in the beginning and 239.1MB in the end (delta: 83.9MB). Free memory was 118.6MB in the beginning and 119.4MB in the end (delta: -753.4kB). Peak memory consumption was 83.6MB. Max. memory is 16.1GB. [2024-11-12 21:42:50,065 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 155.2MB. Free memory is still 116.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-12 21:42:50,065 INFO L158 Benchmark]: CACSL2BoogieTranslator took 221.47ms. Allocated memory is still 155.2MB. Free memory was 118.2MB in the beginning and 106.7MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-12 21:42:50,065 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.14ms. Allocated memory is still 155.2MB. Free memory was 106.5MB in the beginning and 105.2MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-12 21:42:50,066 INFO L158 Benchmark]: Boogie Preprocessor took 22.78ms. Allocated memory is still 155.2MB. Free memory was 105.2MB in the beginning and 103.5MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-12 21:42:50,066 INFO L158 Benchmark]: RCFGBuilder took 273.66ms. Allocated memory is still 155.2MB. Free memory was 103.5MB in the beginning and 93.9MB in the end (delta: 9.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-12 21:42:50,066 INFO L158 Benchmark]: BuchiAutomizer took 7785.37ms. Allocated memory was 155.2MB in the beginning and 239.1MB in the end (delta: 83.9MB). Free memory was 93.4MB in the beginning and 119.4MB in the end (delta: -25.9MB). Peak memory consumption was 58.4MB. Max. memory is 16.1GB. [2024-11-12 21:42:50,066 INFO L158 Benchmark]: Witness Printer took 5.22ms. Allocated memory is still 239.1MB. Free memory is still 119.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-12 21:42:50,068 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.19ms. Allocated memory is still 155.2MB. Free memory is still 116.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 221.47ms. Allocated memory is still 155.2MB. Free memory was 118.2MB in the beginning and 106.7MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.14ms. Allocated memory is still 155.2MB. Free memory was 106.5MB in the beginning and 105.2MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 22.78ms. Allocated memory is still 155.2MB. Free memory was 105.2MB in the beginning and 103.5MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 273.66ms. Allocated memory is still 155.2MB. Free memory was 103.5MB in the beginning and 93.9MB in the end (delta: 9.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 7785.37ms. Allocated memory was 155.2MB in the beginning and 239.1MB in the end (delta: 83.9MB). Free memory was 93.4MB in the beginning and 119.4MB in the end (delta: -25.9MB). Peak memory consumption was 58.4MB. Max. memory is 16.1GB. * Witness Printer took 5.22ms. Allocated memory is still 239.1MB. Free memory is still 119.4MB. 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 8 terminating modules (4 trivial, 2 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 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. 4 modules have a trivial ranking function, the largest among these consists of 12 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 7.7s and 6 iterations. TraceHistogramMax:7. Analysis of lassos took 3.8s. Construction of modules took 0.5s. Büchi inclusion checks took 3.1s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 117 StatesRemovedByMinimization, 5 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 0/6 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 287 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 275 mSDsluCounter, 363 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 206 mSDsCounter, 152 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 719 IncrementalHoareTripleChecker+Invalid, 871 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 152 mSolverCounterUnsat, 157 mSDtfsCounter, 719 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT1 SILN0 SILU0 SILI1 SILT2 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp78 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf91 smp82 dnf100 smp100 tf113 neg100 sie105 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 21ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 11 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.5s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-12 21:42:50,090 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:50,290 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:50,491 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-12 21:42:50,691 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-12 21:42:50,891 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-12 21:42:51,093 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE