./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_10-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-simple/fibo_10-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a6546395432109233bf3e1991428a566548dd822bb23ca198622322bf4db5a8a --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-10 23:16:57,972 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-10 23:16:58,038 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-10 23:16:58,046 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-10 23:16:58,048 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-10 23:16:58,049 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2024-11-10 23:16:58,078 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-10 23:16:58,080 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-10 23:16:58,081 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-10 23:16:58,082 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-10 23:16:58,083 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-10 23:16:58,083 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-10 23:16:58,084 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-10 23:16:58,085 INFO L153 SettingsManager]: * Use SBE=true [2024-11-10 23:16:58,085 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-10 23:16:58,085 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-10 23:16:58,086 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-10 23:16:58,086 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-10 23:16:58,089 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-10 23:16:58,089 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-10 23:16:58,089 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-10 23:16:58,090 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-10 23:16:58,090 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-10 23:16:58,090 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-10 23:16:58,091 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-10 23:16:58,091 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-10 23:16:58,091 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-10 23:16:58,091 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-10 23:16:58,092 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-10 23:16:58,092 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-10 23:16:58,093 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-10 23:16:58,093 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-10 23:16:58,093 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-10 23:16:58,093 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-10 23:16:58,093 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-10 23:16:58,093 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-10 23:16:58,094 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-10 23:16:58,094 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-10 23:16:58,094 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-10 23:16:58,095 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-10 23:16:58,095 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> a6546395432109233bf3e1991428a566548dd822bb23ca198622322bf4db5a8a [2024-11-10 23:16:58,310 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-10 23:16:58,335 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-10 23:16:58,339 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-10 23:16:58,340 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-10 23:16:58,341 INFO L274 PluginConnector]: CDTParser initialized [2024-11-10 23:16:58,342 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_10-2.c [2024-11-10 23:16:59,787 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-10 23:16:59,982 INFO L384 CDTParser]: Found 1 translation units. [2024-11-10 23:16:59,983 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-2.c [2024-11-10 23:16:59,992 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/55f1c1775/3441efc8abae49dfb8abbc04b407c10a/FLAG385d22443 [2024-11-10 23:17:00,009 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/55f1c1775/3441efc8abae49dfb8abbc04b407c10a [2024-11-10 23:17:00,013 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-10 23:17:00,014 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-10 23:17:00,016 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-10 23:17:00,017 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-10 23:17:00,022 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-10 23:17:00,023 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,024 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1f4c00aa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00, skipping insertion in model container [2024-11-10 23:17:00,025 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,044 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-10 23:17:00,216 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:17:00,226 INFO L200 MainTranslator]: Completed pre-run [2024-11-10 23:17:00,238 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:17:00,254 INFO L204 MainTranslator]: Completed translation [2024-11-10 23:17:00,255 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00 WrapperNode [2024-11-10 23:17:00,255 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-10 23:17:00,256 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-10 23:17:00,257 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-10 23:17:00,257 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-10 23:17:00,264 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,271 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,285 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-10 23:17:00,286 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-10 23:17:00,287 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-10 23:17:00,287 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-10 23:17:00,287 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-10 23:17:00,296 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,297 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,298 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,306 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-10 23:17:00,306 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,306 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,308 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,309 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,309 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,310 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,311 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-10 23:17:00,312 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-10 23:17:00,312 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-10 23:17:00,312 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-10 23:17:00,313 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (1/1) ... [2024-11-10 23:17:00,322 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,337 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,352 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-10 23:17:00,354 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-10 23:17:00,398 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-10 23:17:00,398 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-10 23:17:00,398 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-10 23:17:00,398 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-10 23:17:00,398 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-10 23:17:00,398 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-10 23:17:00,448 INFO L256 CfgBuilder]: Building ICFG [2024-11-10 23:17:00,450 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-10 23:17:00,538 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2024-11-10 23:17:00,549 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-10 23:17:00,549 INFO L307 CfgBuilder]: Performing block encoding [2024-11-10 23:17:00,560 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-10 23:17:00,560 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-10 23:17:00,560 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:00 BoogieIcfgContainer [2024-11-10 23:17:00,560 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-10 23:17:00,561 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-10 23:17:00,562 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-10 23:17:00,565 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-10 23:17:00,565 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:00,565 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 10.11 11:17:00" (1/3) ... [2024-11-10 23:17:00,566 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1041bd78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.11 11:17:00, skipping insertion in model container [2024-11-10 23:17:00,566 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:00,566 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:00" (2/3) ... [2024-11-10 23:17:00,567 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1041bd78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.11 11:17:00, skipping insertion in model container [2024-11-10 23:17:00,567 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:00,567 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:00" (3/3) ... [2024-11-10 23:17:00,569 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_10-2.c [2024-11-10 23:17:00,617 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-10 23:17:00,617 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-10 23:17:00,617 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-10 23:17:00,617 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-10 23:17:00,618 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-10 23:17:00,618 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-10 23:17:00,618 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-10 23:17:00,618 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-10 23:17:00,622 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-10 23:17:00,646 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:00,646 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:00,647 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:00,654 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:00,655 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:00,655 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-10 23:17:00,655 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-10 23:17:00,659 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:00,659 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:00,659 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:00,660 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:00,660 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:00,666 INFO L745 eck$LassoCheckResult]: Stem: 3#ULTIMATE.startENTRYtrue assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 12#ULTIMATE.init_returnLabel#1true assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 18#L27-1true call main_#t~ret6#1 := fibo(main_~x~0#1);< 7#fiboENTRYtrue [2024-11-10 23:17:00,667 INFO L747 eck$LassoCheckResult]: Loop: 7#fiboENTRYtrue ~n := #in~n; 8#L8true assume !(~n < 1); 9#L10true assume !(1 == ~n); 19#L13-3true call #t~ret4 := fibo(~n - 1);< 7#fiboENTRYtrue [2024-11-10 23:17:00,675 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:00,678 INFO L85 PathProgramCache]: Analyzing trace with hash 39702, now seen corresponding path program 1 times [2024-11-10 23:17:00,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:00,701 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [68706428] [2024-11-10 23:17:00,701 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:00,702 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:00,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,829 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:00,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,865 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:00,867 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:00,868 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 1 times [2024-11-10 23:17:00,868 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:00,868 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [867650509] [2024-11-10 23:17:00,869 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:00,869 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:00,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,879 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:00,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,890 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:00,891 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:00,892 INFO L85 PathProgramCache]: Analyzing trace with hash -1988460259, now seen corresponding path program 1 times [2024-11-10 23:17:00,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:00,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1885410920] [2024-11-10 23:17:00,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:00,893 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:00,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,913 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:00,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,927 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:01,087 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:01,088 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:01,088 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:01,088 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:01,088 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:01,088 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,089 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:01,089 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:01,089 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration1_Loop [2024-11-10 23:17:01,089 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:01,089 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:01,109 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,121 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,130 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,134 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,222 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:01,223 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:01,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,228 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-10 23:17:01,230 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-10 23:17:01,231 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:01,231 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:01,252 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:01,253 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-10 23:17:01,264 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:01,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,266 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-10 23:17:01,267 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-10 23:17:01,268 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:01,268 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:01,283 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:01,283 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-10 23:17:01,294 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-10 23:17:01,294 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,295 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,297 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-10 23:17:01,298 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-10 23:17:01,299 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:01,299 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:01,317 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:01,317 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-10 23:17:01,332 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-10 23:17:01,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,336 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-10 23:17:01,338 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-10 23:17:01,340 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:01,340 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:01,362 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:01,362 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-10 23:17:01,381 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-10 23:17:01,381 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,382 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,383 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-10 23:17:01,384 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-10 23:17:01,385 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:01,385 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:01,414 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-11-10 23:17:01,415 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,415 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,417 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-10 23:17:01,419 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-10 23:17:01,420 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:01,421 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:01,479 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:01,484 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-10 23:17:01,485 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:01,485 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:01,485 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:01,485 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:01,485 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:01,485 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,485 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:01,485 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:01,486 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration1_Loop [2024-11-10 23:17:01,486 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:01,486 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:01,488 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,492 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,495 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,499 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,502 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,571 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:01,575 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:01,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,578 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-10 23:17:01,579 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-10 23:17:01,580 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-10 23:17:01,590 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,590 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,591 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,591 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,591 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,593 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,593 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,598 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,609 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:01,609 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,609 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,611 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-10 23:17:01,613 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-10 23:17:01,614 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-10 23:17:01,625 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,625 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,625 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,625 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,626 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,626 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,627 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,631 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,641 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-10 23:17:01,642 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,642 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,643 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-10 23:17:01,644 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-10 23:17:01,645 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-10 23:17:01,655 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,655 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,655 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,655 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,655 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,656 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,656 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,657 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,668 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-10 23:17:01,668 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,669 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,670 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-10 23:17:01,670 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-10 23:17:01,671 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-10 23:17:01,681 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,682 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,682 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,682 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,682 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,682 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,682 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,687 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,699 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:01,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,700 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,702 INFO L229 MonitoredProcess]: Starting monitored process 12 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-10 23:17:01,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-11-10 23:17:01,703 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-10 23:17:01,714 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,714 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,714 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,714 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,714 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,715 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,715 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,718 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:01,721 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:01,721 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:01,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,738 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-10 23:17:01,739 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-10 23:17:01,740 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:01,740 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:01,740 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:01,741 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-10 23:17:01,754 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-10 23:17:01,757 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:01,787 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:01,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,812 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-10 23:17:01,813 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:01,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,833 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:01,834 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:01,885 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-10 23:17:01,910 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-10 23:17:01,912 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-10 23:17:02,007 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-10 23:17:02,011 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-10 23:17:02,016 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-10 23:17:02,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-10 23:17:02,019 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-10 23:17:02,019 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:02,020 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-10 23:17:02,020 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:02,020 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-10 23:17:02,020 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:02,020 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-10 23:17:02,023 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:02,028 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-10 23:17:02,028 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-10 23:17:02,029 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-10 23:17:02,029 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-10 23:17:02,030 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:02,030 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-10 23:17:02,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-10 23:17:02,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-10 23:17:02,050 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-10 23:17:02,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-10 23:17:02,055 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:02,055 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:02,055 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-10 23:17:02,055 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-10 23:17:02,056 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:02,056 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:02,056 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:02,057 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:02,057 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:02,057 INFO L745 eck$LassoCheckResult]: Stem: 120#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 121#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 124#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 129#fiboENTRY ~n := #in~n; 130#L8 assume !(~n < 1); 134#L10 assume !(1 == ~n); 123#L13-3 call #t~ret4 := fibo(~n - 1);< 131#fiboENTRY ~n := #in~n; 132#L8 assume ~n < 1;#res := 0; 127#fiboFINAL assume true; 128#fiboEXIT >#27#return; 122#L13-2 [2024-11-10 23:17:02,058 INFO L747 eck$LassoCheckResult]: Loop: 122#L13-2 call #t~ret5 := fibo(~n - 2);< 126#fiboENTRY ~n := #in~n; 139#L8 assume !(~n < 1); 138#L10 assume !(1 == ~n); 125#L13-3 call #t~ret4 := fibo(~n - 1);< 126#fiboENTRY ~n := #in~n; 139#L8 assume ~n < 1;#res := 0; 136#fiboFINAL assume true; 137#fiboEXIT >#27#return; 122#L13-2 [2024-11-10 23:17:02,058 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:02,058 INFO L85 PathProgramCache]: Analyzing trace with hash 1475604923, now seen corresponding path program 1 times [2024-11-10 23:17:02,058 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:02,058 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [958484699] [2024-11-10 23:17:02,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:02,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,182 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:02,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,235 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 23:17:02,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:02,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [958484699] [2024-11-10 23:17:02,237 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [958484699] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:02,238 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:02,238 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:02,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [546917279] [2024-11-10 23:17:02,239 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:02,241 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:02,241 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:02,241 INFO L85 PathProgramCache]: Analyzing trace with hash 93365724, now seen corresponding path program 1 times [2024-11-10 23:17:02,242 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:02,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [417674036] [2024-11-10 23:17:02,242 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,242 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:02,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,292 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:02,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,347 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 23:17:02,348 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:02,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [417674036] [2024-11-10 23:17:02,348 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [417674036] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:02,348 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:02,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:02,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515080368] [2024-11-10 23:17:02,349 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:02,349 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:02,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:02,352 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-10 23:17:02,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-10 23:17:02,353 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-10 23:17:02,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:02,430 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-10 23:17:02,430 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-10 23:17:02,432 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:02,433 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-10 23:17:02,433 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-10 23:17:02,435 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-10 23:17:02,435 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-10 23:17:02,435 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:02,435 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:02,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-10 23:17:02,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-10 23:17:02,439 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-10 23:17:02,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-10 23:17:02,442 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:02,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 23:17:02,443 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:02,443 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-10 23:17:02,444 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-10 23:17:02,444 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:02,444 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:02,444 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:02,447 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:02,448 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:02,448 INFO L745 eck$LassoCheckResult]: Stem: 191#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 192#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 193#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 208#fiboENTRY ~n := #in~n; 200#L8 assume !(~n < 1); 206#L10 assume !(1 == ~n); 196#L13-3 call #t~ret4 := fibo(~n - 1);< 199#fiboENTRY ~n := #in~n; 201#L8 assume !(~n < 1); 205#L10 assume 1 == ~n;#res := 1; 207#fiboFINAL assume true; 204#fiboEXIT >#27#return; 194#L13-2 [2024-11-10 23:17:02,448 INFO L747 eck$LassoCheckResult]: Loop: 194#L13-2 call #t~ret5 := fibo(~n - 2);< 197#fiboENTRY ~n := #in~n; 198#L8 assume !(~n < 1); 212#L10 assume !(1 == ~n); 195#L13-3 call #t~ret4 := fibo(~n - 1);< 197#fiboENTRY ~n := #in~n; 198#L8 assume !(~n < 1); 212#L10 assume !(1 == ~n); 195#L13-3 call #t~ret4 := fibo(~n - 1);< 197#fiboENTRY ~n := #in~n; 198#L8 assume !(~n < 1); 212#L10 assume 1 == ~n;#res := 1; 202#fiboFINAL assume true; 203#fiboEXIT >#27#return; 194#L13-2 call #t~ret5 := fibo(~n - 2);< 197#fiboENTRY ~n := #in~n; 198#L8 assume ~n < 1;#res := 0; 213#fiboFINAL assume true; 211#fiboEXIT >#25#return; 209#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 210#fiboFINAL assume true; 214#fiboEXIT >#27#return; 194#L13-2 [2024-11-10 23:17:02,448 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:02,448 INFO L85 PathProgramCache]: Analyzing trace with hash -1500686953, now seen corresponding path program 1 times [2024-11-10 23:17:02,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:02,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649861131] [2024-11-10 23:17:02,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:02,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,516 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:02,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,554 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-10 23:17:02,555 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:02,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1649861131] [2024-11-10 23:17:02,555 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1649861131] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:02,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [473113203] [2024-11-10 23:17:02,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,555 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:02,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:02,558 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-10 23:17:02,559 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-10 23:17:02,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,599 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:02,600 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:02,646 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-10 23:17:02,646 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:02,776 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-10 23:17:02,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [473113203] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:02,777 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:02,777 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-10 23:17:02,777 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [306842987] [2024-11-10 23:17:02,777 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:02,778 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:02,778 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:02,778 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 1 times [2024-11-10 23:17:02,778 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:02,778 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [264968335] [2024-11-10 23:17:02,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,779 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:02,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:02,791 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:02,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:02,804 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:03,023 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-10 23:17:03,141 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:03,141 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:03,141 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:03,141 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:03,142 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:03,142 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,142 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:03,142 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:03,142 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration3_Loop [2024-11-10 23:17:03,142 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:03,144 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:03,144 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,149 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,151 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,212 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:03,213 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:03,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,216 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-10 23:17:03,218 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-10 23:17:03,219 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:03,219 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:03,230 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:03,230 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-10 23:17:03,241 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-10 23:17:03,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,242 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,243 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-10 23:17:03,244 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-10 23:17:03,245 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:03,245 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:03,259 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:03,259 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-10 23:17:03,270 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-10 23:17:03,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,271 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,272 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-10 23:17:03,273 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-10 23:17:03,274 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:03,274 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:03,304 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-10 23:17:03,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,306 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-10 23:17:03,307 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-10 23:17:03,307 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:03,308 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:03,764 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:03,769 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-10 23:17:03,769 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:03,769 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:03,769 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:03,770 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:03,770 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:03,770 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,770 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:03,770 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:03,770 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration3_Loop [2024-11-10 23:17:03,770 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:03,770 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:03,771 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,783 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,785 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,788 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,846 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:03,847 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:03,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,847 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,849 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-10 23:17:03,850 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-10 23:17:03,851 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-10 23:17:03,862 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:03,862 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:03,862 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:03,863 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:03,863 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:03,864 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:03,864 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:03,866 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:03,868 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:03,869 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:03,869 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,869 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,870 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-10 23:17:03,872 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-10 23:17:03,872 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:03,872 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:03,872 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:03,872 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:03,883 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:03,884 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:03,895 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:03,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:03,920 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:03,921 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:04,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,018 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:04,020 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:04,184 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-10 23:17:04,185 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-10 23:17:04,186 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-10 23:17:04,445 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 152 states and 210 transitions. Complement of second has 54 states. [2024-11-10 23:17:04,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-10 23:17:04,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-10 23:17:04,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-10 23:17:04,447 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-10 23:17:04,447 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:04,447 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-10 23:17:04,448 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:04,448 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-10 23:17:04,449 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:04,449 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-10 23:17:04,454 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:04,459 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-10 23:17:04,459 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-10 23:17:04,459 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-10 23:17:04,459 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-10 23:17:04,460 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:04,460 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-10 23:17:04,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-10 23:17:04,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-10 23:17:04,472 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 70 states have internal predecessors, (81), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (35), 22 states have call predecessors, (35), 23 states have call successors, (35) [2024-11-10 23:17:04,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-10 23:17:04,474 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-10 23:17:04,474 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:04,474 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-10 23:17:04,475 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-10 23:17:04,475 INFO L87 Difference]: Start difference. First operand 106 states and 142 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-10 23:17:04,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:04,602 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-10 23:17:04,602 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-10 23:17:04,609 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:04,613 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-10 23:17:04,613 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-10 23:17:04,613 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-10 23:17:04,614 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-10 23:17:04,614 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:04,614 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-10 23:17:04,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-10 23:17:04,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-10 23:17:04,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 74 states have (on average 1.2027027027027026) internal successors, (89), 78 states have internal predecessors, (89), 28 states have call successors, (29), 15 states have call predecessors, (29), 16 states have return successors, (39), 24 states have call predecessors, (39), 26 states have call successors, (39) [2024-11-10 23:17:04,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-10 23:17:04,626 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:04,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:04,627 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:04,627 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-10 23:17:04,627 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-10 23:17:04,629 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:04,629 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:04,629 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:04,631 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:04,631 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-10 23:17:04,631 INFO L745 eck$LassoCheckResult]: Stem: 881#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 882#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 884#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 916#fiboENTRY ~n := #in~n; 950#L8 assume !(~n < 1); 949#L10 assume !(1 == ~n); 894#L13-3 call #t~ret4 := fibo(~n - 1);< 893#fiboENTRY ~n := #in~n; 895#L8 assume !(~n < 1); 908#L10 assume !(1 == ~n); 915#L13-3 call #t~ret4 := fibo(~n - 1);< 943#fiboENTRY ~n := #in~n; 947#L8 assume !(~n < 1); 945#L10 assume !(1 == ~n); 940#L13-3 call #t~ret4 := fibo(~n - 1);< 943#fiboENTRY ~n := #in~n; 947#L8 assume !(~n < 1); 945#L10 assume !(1 == ~n); 940#L13-3 call #t~ret4 := fibo(~n - 1);< 943#fiboENTRY ~n := #in~n; 948#L8 assume !(~n < 1); 946#L10 assume 1 == ~n;#res := 1; 944#fiboFINAL assume true; 942#fiboEXIT >#27#return; 887#L13-2 call #t~ret5 := fibo(~n - 2);< 941#fiboENTRY ~n := #in~n; 996#L8 assume ~n < 1;#res := 0; 995#fiboFINAL assume true; 994#fiboEXIT >#25#return; 992#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 989#fiboFINAL assume true; 979#fiboEXIT >#27#return; 912#L13-2 [2024-11-10 23:17:04,631 INFO L747 eck$LassoCheckResult]: Loop: 912#L13-2 call #t~ret5 := fibo(~n - 2);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume !(1 == ~n); 911#L13-3 call #t~ret4 := fibo(~n - 1);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume !(1 == ~n); 911#L13-3 call #t~ret4 := fibo(~n - 1);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume 1 == ~n;#res := 1; 914#fiboFINAL assume true; 983#fiboEXIT >#27#return; 912#L13-2 call #t~ret5 := fibo(~n - 2);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume 1 == ~n;#res := 1; 914#fiboFINAL assume true; 983#fiboEXIT >#25#return; 981#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 988#fiboFINAL assume true; 980#fiboEXIT >#27#return; 912#L13-2 [2024-11-10 23:17:04,631 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:04,631 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 1 times [2024-11-10 23:17:04,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:04,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1008276165] [2024-11-10 23:17:04,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:04,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:04,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,761 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:04,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,834 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:04,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,866 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:04,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,877 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 23:17:04,877 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:04,877 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1008276165] [2024-11-10 23:17:04,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1008276165] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:04,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1763049881] [2024-11-10 23:17:04,878 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:04,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:04,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:04,880 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-10 23:17:04,880 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-10 23:17:04,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,922 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:04,924 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:04,972 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-10 23:17:05,011 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 23:17:05,011 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:05,306 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-10 23:17:05,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1763049881] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:05,307 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:05,307 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-10 23:17:05,307 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1053020138] [2024-11-10 23:17:05,307 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:05,308 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:05,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:05,308 INFO L85 PathProgramCache]: Analyzing trace with hash -1547808212, now seen corresponding path program 1 times [2024-11-10 23:17:05,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:05,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [269454107] [2024-11-10 23:17:05,308 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:05,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:05,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,344 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:05,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,367 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:05,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,393 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:05,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,424 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-10 23:17:05,424 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:05,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [269454107] [2024-11-10 23:17:05,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [269454107] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:05,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1617734239] [2024-11-10 23:17:05,424 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:05,424 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:05,424 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:05,426 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 23:17:05,427 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-11-10 23:17:05,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,460 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:05,461 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:05,491 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-10 23:17:05,492 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:05,625 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-10 23:17:05,625 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1617734239] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:05,625 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:05,625 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-10 23:17:05,626 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1761925604] [2024-11-10 23:17:05,626 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:05,626 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:05,626 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:05,626 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-10 23:17:05,626 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-10 23:17:05,627 INFO L87 Difference]: Start difference. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 2 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:05,725 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:05,725 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-10 23:17:05,725 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-10 23:17:05,726 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:05,727 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-10 23:17:05,728 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-10 23:17:05,728 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-10 23:17:05,728 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-10 23:17:05,728 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:05,728 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:05,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-10 23:17:05,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-10 23:17:05,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-10 23:17:05,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-10 23:17:05,733 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:05,734 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:05,734 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:05,735 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-10 23:17:05,735 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-10 23:17:05,736 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:05,736 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:05,736 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:05,737 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:05,737 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:05,737 INFO L745 eck$LassoCheckResult]: Stem: 1472#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 1473#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 1480#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1499#fiboENTRY ~n := #in~n; 1508#L8 assume !(~n < 1); 1510#L10 assume !(1 == ~n); 1485#L13-3 call #t~ret4 := fibo(~n - 1);< 1484#fiboENTRY ~n := #in~n; 1486#L8 assume !(~n < 1); 1498#L10 assume !(1 == ~n); 1493#L13-3 call #t~ret4 := fibo(~n - 1);< 1502#fiboENTRY ~n := #in~n; 1492#L8 assume !(~n < 1); 1495#L10 assume !(1 == ~n); 1494#L13-3 call #t~ret4 := fibo(~n - 1);< 1502#fiboENTRY ~n := #in~n; 1492#L8 assume !(~n < 1); 1495#L10 assume !(1 == ~n); 1494#L13-3 call #t~ret4 := fibo(~n - 1);< 1502#fiboENTRY ~n := #in~n; 1509#L8 assume !(~n < 1); 1496#L10 assume 1 == ~n;#res := 1; 1497#fiboFINAL assume true; 1515#fiboEXIT >#27#return; 1482#L13-2 call #t~ret5 := fibo(~n - 2);< 1481#fiboENTRY ~n := #in~n; 1483#L8 assume ~n < 1;#res := 0; 1491#fiboFINAL assume true; 1489#fiboEXIT >#25#return; 1490#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1523#fiboFINAL assume true; 1522#fiboEXIT >#27#return; 1478#L13-2 [2024-11-10 23:17:05,738 INFO L747 eck$LassoCheckResult]: Loop: 1478#L13-2 call #t~ret5 := fibo(~n - 2);< 1501#fiboENTRY ~n := #in~n; 1506#L8 assume !(~n < 1); 1504#L10 assume !(1 == ~n); 1476#L13-3 call #t~ret4 := fibo(~n - 1);< 1501#fiboENTRY ~n := #in~n; 1506#L8 assume !(~n < 1); 1504#L10 assume !(1 == ~n); 1476#L13-3 call #t~ret4 := fibo(~n - 1);< 1501#fiboENTRY ~n := #in~n; 1506#L8 assume !(~n < 1); 1504#L10 assume 1 == ~n;#res := 1; 1505#fiboFINAL assume true; 1512#fiboEXIT >#27#return; 1474#L13-2 call #t~ret5 := fibo(~n - 2);< 1479#fiboENTRY ~n := #in~n; 1525#L8 assume ~n < 1;#res := 0; 1507#fiboFINAL assume true; 1520#fiboEXIT >#25#return; 1503#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1487#fiboFINAL assume true; 1488#fiboEXIT >#27#return; 1478#L13-2 [2024-11-10 23:17:05,738 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:05,738 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 2 times [2024-11-10 23:17:05,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:05,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [720246154] [2024-11-10 23:17:05,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:05,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:05,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,825 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:05,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,870 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:05,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,891 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:05,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,895 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 23:17:05,896 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:05,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [720246154] [2024-11-10 23:17:05,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [720246154] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:05,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [292874028] [2024-11-10 23:17:05,896 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-10 23:17:05,897 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:05,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:05,899 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 23:17:05,901 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2024-11-10 23:17:05,950 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-10 23:17:05,950 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:05,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:05,952 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:06,005 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 23:17:06,006 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:06,287 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-10 23:17:06,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [292874028] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:06,287 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:06,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-10 23:17:06,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [856826984] [2024-11-10 23:17:06,288 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:06,288 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:06,288 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:06,289 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 2 times [2024-11-10 23:17:06,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:06,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [423775627] [2024-11-10 23:17:06,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:06,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:06,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:06,294 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:06,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:06,299 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:06,489 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:06,490 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:06,490 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:06,490 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:06,490 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:06,490 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,490 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:06,490 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:06,490 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration5_Loop [2024-11-10 23:17:06,490 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:06,490 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:06,491 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,494 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,499 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,501 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,503 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,539 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:06,539 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:06,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,540 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,541 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-10 23:17:06,544 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-10 23:17:06,545 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:06,545 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:06,562 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:06,562 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-10 23:17:06,573 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-10 23:17:06,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,574 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,575 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-10 23:17:06,575 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-10 23:17:06,576 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:06,576 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:06,599 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-10 23:17:06,599 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,600 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-10 23:17:06,602 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-10 23:17:06,602 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:06,602 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:06,614 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:06,625 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:06,625 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:06,625 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:06,625 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:06,626 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:06,626 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:06,626 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,626 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:06,626 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:06,626 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration5_Loop [2024-11-10 23:17:06,626 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:06,626 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:06,626 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,632 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,634 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,644 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,646 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,679 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:06,679 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:06,679 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,681 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-10 23:17:06,682 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-10 23:17:06,683 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-10 23:17:06,696 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:06,696 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:06,696 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:06,696 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:06,696 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:06,697 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:06,697 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:06,699 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:06,708 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:06,708 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:06,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,710 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-10 23:17:06,712 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-10 23:17:06,712 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:06,712 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:06,712 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:06,712 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:06,725 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-10 23:17:06,725 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:06,734 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:06,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:06,784 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:06,787 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,043 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,046 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,171 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-10 23:17:07,172 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-10 23:17:07,172 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:07,259 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-11-10 23:17:07,259 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-10 23:17:07,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:07,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:07,260 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:07,260 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:07,260 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:07,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:07,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,307 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,309 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,468 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-11-10 23:17:07,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,515 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,517 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,643 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-10 23:17:07,643 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-10 23:17:07,643 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:07,733 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-11-10 23:17:07,733 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-10 23:17:07,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:07,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:07,734 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:07,734 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:07,734 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:07,745 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:07,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,781 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,783 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,962 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,963 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:08,074 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-10 23:17:08,075 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-10 23:17:08,075 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:08,328 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 408 states and 526 transitions. Complement of second has 132 states. [2024-11-10 23:17:08,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-10 23:17:08,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:08,332 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-10 23:17:08,332 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:08,333 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:08,333 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-10 23:17:08,334 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:08,334 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-10 23:17:08,340 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:08,340 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-10 23:17:08,355 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:08,362 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-10 23:17:08,363 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-10 23:17:08,363 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-10 23:17:08,363 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-10 23:17:08,363 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:08,363 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-10 23:17:08,364 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-10 23:17:08,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-10 23:17:08,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 115 states have (on average 1.1391304347826088) internal successors, (131), 122 states have internal predecessors, (131), 43 states have call successors, (48), 25 states have call predecessors, (48), 29 states have return successors, (67), 39 states have call predecessors, (67), 39 states have call successors, (67) [2024-11-10 23:17:08,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-10 23:17:08,385 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-10 23:17:08,385 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:08,386 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-10 23:17:08,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-11-10 23:17:08,386 INFO L87 Difference]: Start difference. First operand 187 states and 246 transitions. Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-10 23:17:08,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:08,722 INFO L93 Difference]: Finished difference Result 380 states and 491 transitions. [2024-11-10 23:17:08,722 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 380 states and 491 transitions. [2024-11-10 23:17:08,729 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:08,737 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 380 states to 356 states and 457 transitions. [2024-11-10 23:17:08,737 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 177 [2024-11-10 23:17:08,738 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 177 [2024-11-10 23:17:08,738 INFO L73 IsDeterministic]: Start isDeterministic. Operand 356 states and 457 transitions. [2024-11-10 23:17:08,738 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:08,738 INFO L218 hiAutomatonCegarLoop]: Abstraction has 356 states and 457 transitions. [2024-11-10 23:17:08,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 356 states and 457 transitions. [2024-11-10 23:17:08,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 356 to 332. [2024-11-10 23:17:08,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 332 states, 203 states have (on average 1.0886699507389161) internal successors, (221), 216 states have internal predecessors, (221), 78 states have call successors, (82), 41 states have call predecessors, (82), 51 states have return successors, (125), 74 states have call predecessors, (125), 69 states have call successors, (125) [2024-11-10 23:17:08,765 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 428 transitions. [2024-11-10 23:17:08,769 INFO L240 hiAutomatonCegarLoop]: Abstraction has 332 states and 428 transitions. [2024-11-10 23:17:08,771 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-10 23:17:08,771 INFO L425 stractBuchiCegarLoop]: Abstraction has 332 states and 428 transitions. [2024-11-10 23:17:08,772 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-10 23:17:08,772 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 332 states and 428 transitions. [2024-11-10 23:17:08,775 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:08,776 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:08,776 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:08,777 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 11, 10, 10, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:08,778 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:08,778 INFO L745 eck$LassoCheckResult]: Stem: 3572#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 3573#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 3574#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 3615#fiboENTRY ~n := #in~n; 3652#L8 assume !(~n < 1); 3651#L10 assume !(1 == ~n); 3647#L13-3 call #t~ret4 := fibo(~n - 1);< 3650#fiboENTRY ~n := #in~n; 3649#L8 assume !(~n < 1); 3648#L10 assume !(1 == ~n); 3643#L13-3 call #t~ret4 := fibo(~n - 1);< 3646#fiboENTRY ~n := #in~n; 3645#L8 assume !(~n < 1); 3644#L10 assume !(1 == ~n); 3639#L13-3 call #t~ret4 := fibo(~n - 1);< 3642#fiboENTRY ~n := #in~n; 3641#L8 assume !(~n < 1); 3640#L10 assume !(1 == ~n); 3635#L13-3 call #t~ret4 := fibo(~n - 1);< 3638#fiboENTRY ~n := #in~n; 3637#L8 assume !(~n < 1); 3636#L10 assume !(1 == ~n); 3630#L13-3 call #t~ret4 := fibo(~n - 1);< 3633#fiboENTRY ~n := #in~n; 3634#L8 assume !(~n < 1); 3631#L10 assume !(1 == ~n); 3626#L13-3 call #t~ret4 := fibo(~n - 1);< 3625#fiboENTRY ~n := #in~n; 3628#L8 assume !(~n < 1); 3632#L10 assume !(1 == ~n); 3627#L13-3 call #t~ret4 := fibo(~n - 1);< 3625#fiboENTRY ~n := #in~n; 3628#L8 assume !(~n < 1); 3632#L10 assume !(1 == ~n); 3627#L13-3 call #t~ret4 := fibo(~n - 1);< 3625#fiboENTRY ~n := #in~n; 3629#L8 assume !(~n < 1); 3888#L10 assume 1 == ~n;#res := 1; 3886#fiboFINAL assume true; 3879#fiboEXIT >#27#return; 3876#L13-2 call #t~ret5 := fibo(~n - 2);< 3877#fiboENTRY ~n := #in~n; 3897#L8 assume ~n < 1;#res := 0; 3896#fiboFINAL assume true; 3875#fiboEXIT >#25#return; 3853#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3852#fiboFINAL assume true; 3828#fiboEXIT >#27#return; 3751#L13-2 call #t~ret5 := fibo(~n - 2);< 3754#fiboENTRY ~n := #in~n; 3868#L8 assume !(~n < 1); 3866#L10 assume !(1 == ~n); 3601#L13-3 call #t~ret4 := fibo(~n - 1);< 3864#fiboENTRY ~n := #in~n; 3872#L8 assume !(~n < 1); 3870#L10 assume !(1 == ~n); 3671#L13-3 call #t~ret4 := fibo(~n - 1);< 3675#fiboENTRY [2024-11-10 23:17:08,779 INFO L747 eck$LassoCheckResult]: Loop: 3675#fiboENTRY ~n := #in~n; 3679#L8 assume !(~n < 1); 3677#L10 assume !(1 == ~n); 3668#L13-3 call #t~ret4 := fibo(~n - 1);< 3675#fiboENTRY [2024-11-10 23:17:08,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:08,779 INFO L85 PathProgramCache]: Analyzing trace with hash -1417466561, now seen corresponding path program 3 times [2024-11-10 23:17:08,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:08,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [77142734] [2024-11-10 23:17:08,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:08,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:08,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:08,994 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-10 23:17:08,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,047 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:09,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,072 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:09,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,078 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 77 proven. 153 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-10 23:17:09,078 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:09,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [77142734] [2024-11-10 23:17:09,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [77142734] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:09,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1438481564] [2024-11-10 23:17:09,079 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-10 23:17:09,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:09,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,085 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 23:17:09,092 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Waiting until timeout for monitored process [2024-11-10 23:17:09,133 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-10 23:17:09,133 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:09,134 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-10 23:17:09,135 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:09,227 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 108 proven. 14 refuted. 0 times theorem prover too weak. 117 trivial. 0 not checked. [2024-11-10 23:17:09,227 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:09,465 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 108 proven. 16 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2024-11-10 23:17:09,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1438481564] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:09,466 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:09,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 9, 10] total 28 [2024-11-10 23:17:09,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1589777380] [2024-11-10 23:17:09,467 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:09,467 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:09,467 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:09,468 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 2 times [2024-11-10 23:17:09,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:09,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1095417599] [2024-11-10 23:17:09,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:09,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:09,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:09,471 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:09,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:09,473 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:09,509 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:09,509 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:09,509 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:09,509 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:09,509 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:09,510 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,510 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:09,510 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:09,510 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration6_Loop [2024-11-10 23:17:09,510 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:09,510 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:09,511 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,512 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,519 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,521 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,522 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,552 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:09,552 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:09,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,555 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-10 23:17:09,556 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-10 23:17:09,557 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:09,557 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:09,573 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:09,573 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-10 23:17:09,587 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-10 23:17:09,588 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,588 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,590 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-10 23:17:09,591 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-10 23:17:09,592 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:09,592 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:09,620 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-10 23:17:09,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,622 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-10 23:17:09,624 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-10 23:17:09,625 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:09,625 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:09,696 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:09,701 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-11-10 23:17:09,701 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:09,701 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:09,701 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:09,702 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:09,702 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:09,702 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,702 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:09,702 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:09,702 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration6_Loop [2024-11-10 23:17:09,702 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:09,702 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:09,703 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,707 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,713 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,715 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,717 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,768 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:09,768 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:09,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,771 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-10 23:17:09,772 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-10 23:17:09,774 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-10 23:17:09,786 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:09,786 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:09,786 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:09,786 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:09,786 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:09,788 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:09,788 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:09,792 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:09,806 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:09,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,809 INFO L229 MonitoredProcess]: Starting monitored process 34 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-10 23:17:09,810 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-10 23:17:09,811 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-10 23:17:09,823 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:09,823 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:09,824 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:09,824 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:09,824 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:09,825 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:09,825 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:09,827 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:09,831 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:09,832 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:09,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,834 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-10 23:17:09,836 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-10 23:17:09,836 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:09,836 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:09,837 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:09,837 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-10 23:17:09,852 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:09,853 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:09,863 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:09,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,947 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-10 23:17:09,950 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,152 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,153 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,175 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-10 23:17:10,175 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-10 23:17:10,176 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100 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-10 23:17:10,238 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100. 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 354 states and 450 transitions. Complement of second has 15 states. [2024-11-10 23:17:10,239 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-10 23:17:10,239 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-10 23:17:10,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:10,240 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-10 23:17:10,240 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,240 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:10,250 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:10,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,317 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,319 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,503 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,503 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,529 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-10 23:17:10,529 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-10 23:17:10,530 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100 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-10 23:17:10,585 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100. 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 354 states and 450 transitions. Complement of second has 15 states. [2024-11-10 23:17:10,586 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-10 23:17:10,588 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-10 23:17:10,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:10,588 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-10 23:17:10,589 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,589 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:10,599 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:10,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,673 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,675 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,890 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,891 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,912 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-11-10 23:17:10,918 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-10 23:17:10,918 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-10 23:17:10,919 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100 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-10 23:17:10,994 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100. 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 441 states and 538 transitions. Complement of second has 19 states. [2024-11-10 23:17:10,997 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-10 23:17:10,997 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-10 23:17:10,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-10 23:17:10,998 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-10 23:17:10,998 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,998 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 4 letters. [2024-11-10 23:17:10,999 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,999 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 57 letters. Loop has 8 letters. [2024-11-10 23:17:10,999 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,999 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 441 states and 538 transitions. [2024-11-10 23:17:11,003 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:11,007 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 441 states to 342 states and 438 transitions. [2024-11-10 23:17:11,007 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 138 [2024-11-10 23:17:11,008 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-10 23:17:11,008 INFO L73 IsDeterministic]: Start isDeterministic. Operand 342 states and 438 transitions. [2024-11-10 23:17:11,008 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:11,008 INFO L218 hiAutomatonCegarLoop]: Abstraction has 342 states and 438 transitions. [2024-11-10 23:17:11,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states and 438 transitions. [2024-11-10 23:17:11,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 340. [2024-11-10 23:17:11,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 340 states, 211 states have (on average 1.085308056872038) internal successors, (229), 224 states have internal predecessors, (229), 78 states have call successors, (82), 41 states have call predecessors, (82), 51 states have return successors, (125), 74 states have call predecessors, (125), 69 states have call successors, (125) [2024-11-10 23:17:11,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 340 states to 340 states and 436 transitions. [2024-11-10 23:17:11,026 INFO L240 hiAutomatonCegarLoop]: Abstraction has 340 states and 436 transitions. [2024-11-10 23:17:11,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:11,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-10 23:17:11,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=625, Unknown=0, NotChecked=0, Total=756 [2024-11-10 23:17:11,028 INFO L87 Difference]: Start difference. First operand 340 states and 436 transitions. Second operand has 28 states, 25 states have (on average 2.16) internal successors, (54), 18 states have internal predecessors, (54), 17 states have call successors, (19), 11 states have call predecessors, (19), 3 states have return successors, (7), 4 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-10 23:17:11,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:11,452 INFO L93 Difference]: Finished difference Result 552 states and 741 transitions. [2024-11-10 23:17:11,452 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 552 states and 741 transitions. [2024-11-10 23:17:11,458 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:11,465 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 552 states to 517 states and 697 transitions. [2024-11-10 23:17:11,465 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 199 [2024-11-10 23:17:11,466 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 212 [2024-11-10 23:17:11,466 INFO L73 IsDeterministic]: Start isDeterministic. Operand 517 states and 697 transitions. [2024-11-10 23:17:11,466 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:11,466 INFO L218 hiAutomatonCegarLoop]: Abstraction has 517 states and 697 transitions. [2024-11-10 23:17:11,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 517 states and 697 transitions. [2024-11-10 23:17:11,479 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 517 to 421. [2024-11-10 23:17:11,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 421 states, 262 states have (on average 1.083969465648855) internal successors, (284), 269 states have internal predecessors, (284), 105 states have call successors, (113), 57 states have call predecessors, (113), 54 states have return successors, (149), 94 states have call predecessors, (149), 94 states have call successors, (149) [2024-11-10 23:17:11,483 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 421 states to 421 states and 546 transitions. [2024-11-10 23:17:11,483 INFO L240 hiAutomatonCegarLoop]: Abstraction has 421 states and 546 transitions. [2024-11-10 23:17:11,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-10 23:17:11,484 INFO L425 stractBuchiCegarLoop]: Abstraction has 421 states and 546 transitions. [2024-11-10 23:17:11,484 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-10 23:17:11,484 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 421 states and 546 transitions. [2024-11-10 23:17:11,486 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:11,486 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:11,486 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:11,488 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [16, 15, 13, 12, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:11,488 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:11,488 INFO L745 eck$LassoCheckResult]: Stem: 6996#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 6997#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 6998#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 7038#fiboENTRY ~n := #in~n; 7204#L8 assume !(~n < 1); 7203#L10 assume !(1 == ~n); 7195#L13-3 call #t~ret4 := fibo(~n - 1);< 7200#fiboENTRY ~n := #in~n; 7198#L8 assume !(~n < 1); 7197#L10 assume !(1 == ~n); 7184#L13-3 call #t~ret4 := fibo(~n - 1);< 7193#fiboENTRY ~n := #in~n; 7192#L8 assume !(~n < 1); 7191#L10 assume !(1 == ~n); 7188#L13-3 call #t~ret4 := fibo(~n - 1);< 7190#fiboENTRY ~n := #in~n; 7254#L8 assume !(~n < 1); 7242#L10 assume !(1 == ~n); 7235#L13-3 call #t~ret4 := fibo(~n - 1);< 7238#fiboENTRY ~n := #in~n; 7250#L8 assume !(~n < 1); 7240#L10 assume !(1 == ~n); 7212#L13-3 call #t~ret4 := fibo(~n - 1);< 7236#fiboENTRY ~n := #in~n; 7262#L8 assume !(~n < 1); 7261#L10 assume !(1 == ~n); 7256#L13-3 call #t~ret4 := fibo(~n - 1);< 7260#fiboENTRY ~n := #in~n; 7281#L8 assume !(~n < 1); 7279#L10 assume !(1 == ~n); 7247#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7315#L8 assume !(~n < 1); 7314#L10 assume !(1 == ~n); 7245#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7315#L8 assume !(~n < 1); 7314#L10 assume !(1 == ~n); 7245#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7315#L8 assume !(~n < 1); 7314#L10 assume !(1 == ~n); 7245#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7316#L8 assume !(~n < 1); 7371#L10 assume 1 == ~n;#res := 1; 7370#fiboFINAL assume true; 7369#fiboEXIT >#27#return; 7362#L13-2 call #t~ret5 := fibo(~n - 2);< 7364#fiboENTRY ~n := #in~n; 7367#L8 assume ~n < 1;#res := 0; 7365#fiboFINAL assume true; 7361#fiboEXIT >#25#return; 7360#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 7359#fiboFINAL assume true; 7355#fiboEXIT >#27#return; 7319#L13-2 call #t~ret5 := fibo(~n - 2);< 7321#fiboENTRY ~n := #in~n; 7326#L8 assume !(~n < 1); 7322#L10 assume 1 == ~n;#res := 1; 7272#fiboFINAL assume true; 7318#fiboEXIT >#25#return; 7228#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 7312#fiboFINAL assume true; 7243#fiboEXIT >#27#return; 7246#L13-2 call #t~ret5 := fibo(~n - 2);< 7249#fiboENTRY ~n := #in~n; 7324#L8 assume !(~n < 1); 7325#L10 assume !(1 == ~n); 7024#L13-3 call #t~ret4 := fibo(~n - 1);< 7067#fiboENTRY ~n := #in~n; 7392#L8 assume !(~n < 1); 7387#L10 assume !(1 == ~n); 7056#L13-3 call #t~ret4 := fibo(~n - 1);< 7055#fiboENTRY ~n := #in~n; 7062#L8 assume !(~n < 1); 7385#L10 assume !(1 == ~n); 7059#L13-3 [2024-11-10 23:17:11,489 INFO L747 eck$LassoCheckResult]: Loop: 7059#L13-3 call #t~ret4 := fibo(~n - 1);< 7055#fiboENTRY ~n := #in~n; 7062#L8 assume !(~n < 1); 7385#L10 assume !(1 == ~n); 7059#L13-3 [2024-11-10 23:17:11,489 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:11,489 INFO L85 PathProgramCache]: Analyzing trace with hash -1215864849, now seen corresponding path program 4 times [2024-11-10 23:17:11,489 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:11,489 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1761610240] [2024-11-10 23:17:11,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:11,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:11,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,823 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-10 23:17:11,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,832 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:11,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,835 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:11,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,837 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:11,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,838 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-10 23:17:11,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,840 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 254 proven. 128 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2024-11-10 23:17:11,840 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:11,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1761610240] [2024-11-10 23:17:11,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1761610240] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:11,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [732721633] [2024-11-10 23:17:11,841 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-10 23:17:11,841 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:11,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:11,843 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 23:17:11,844 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (36)] Waiting until timeout for monitored process [2024-11-10 23:17:11,896 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-10 23:17:11,897 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:11,901 INFO L255 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:11,903 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:12,046 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 262 proven. 145 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-10 23:17:12,046 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:12,488 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 262 proven. 150 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-10 23:17:12,488 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [732721633] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:12,488 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:12,488 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23, 25] total 29 [2024-11-10 23:17:12,489 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1778695512] [2024-11-10 23:17:12,489 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:12,489 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:12,489 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:12,489 INFO L85 PathProgramCache]: Analyzing trace with hash 1717914, now seen corresponding path program 3 times [2024-11-10 23:17:12,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:12,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1859092862] [2024-11-10 23:17:12,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:12,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:12,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:12,495 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:12,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:12,496 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:12,553 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:12,553 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:12,553 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:12,553 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:12,553 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:12,553 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,553 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:12,553 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:12,553 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration7_Loop [2024-11-10 23:17:12,553 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:12,553 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:12,554 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,556 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,563 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,565 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,595 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:12,595 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:12,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,595 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,597 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-10 23:17:12,598 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-10 23:17:12,599 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:12,599 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:12,610 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:12,611 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-10 23:17:12,623 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:12,623 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,624 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-10 23:17:12,625 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-10 23:17:12,626 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:12,626 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:12,656 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2024-11-10 23:17:12,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,658 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-10 23:17:12,658 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-10 23:17:12,659 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:12,659 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:13,314 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:13,319 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Ended with exit code 0 [2024-11-10 23:17:13,319 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:13,320 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:13,320 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:13,320 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:13,320 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:13,320 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:13,320 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:13,320 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:13,320 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-2.c_Iteration7_Loop [2024-11-10 23:17:13,320 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:13,320 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:13,321 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:13,323 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:13,331 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:13,333 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:13,364 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:13,364 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:13,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:13,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:13,365 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-10 23:17:13,367 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-10 23:17:13,367 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-10 23:17:13,377 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:13,377 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:13,377 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:13,377 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:13,377 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:13,378 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:13,378 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:13,381 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:13,393 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:13,393 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:13,393 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:13,394 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-10 23:17:13,395 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-10 23:17:13,396 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-10 23:17:13,405 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:13,405 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:13,405 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:13,405 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:13,405 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:13,406 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:13,406 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:13,408 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:13,411 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:13,411 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:13,412 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:13,412 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:13,413 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-10 23:17:13,414 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-10 23:17:13,414 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:13,414 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:13,414 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:13,414 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:13,425 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-10 23:17:13,426 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:13,434 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:13,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:13,508 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 23:17:13,510 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:13,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:13,806 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:13,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:13,841 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-10 23:17:13,842 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-10 23:17:13,842 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:13,909 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 443 states and 569 transitions. Complement of second has 18 states. [2024-11-10 23:17:13,915 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-10 23:17:13,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:13,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-10 23:17:13,920 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-10 23:17:13,921 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:13,921 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:13,927 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-10 23:17:13,935 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:14,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:14,020 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 23:17:14,023 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:14,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:14,285 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:14,286 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:14,314 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-10 23:17:14,315 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-10 23:17:14,315 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:14,381 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 451 states and 577 transitions. Complement of second has 17 states. [2024-11-10 23:17:14,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-10 23:17:14,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:14,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-10 23:17:14,383 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-10 23:17:14,383 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,383 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:14,394 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:14,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:14,489 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 23:17:14,491 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:14,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:14,768 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:14,769 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:14,802 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-10 23:17:14,803 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 4 loop predicates [2024-11-10 23:17:14,803 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:14,871 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 558 states and 718 transitions. Complement of second has 21 states. [2024-11-10 23:17:14,872 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-10 23:17:14,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 23:17:14,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 20 transitions. [2024-11-10 23:17:14,873 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-10 23:17:14,873 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,873 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 81 letters. Loop has 4 letters. [2024-11-10 23:17:14,874 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,874 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 77 letters. Loop has 8 letters. [2024-11-10 23:17:14,874 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,874 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 558 states and 718 transitions. [2024-11-10 23:17:14,883 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:14,888 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 558 states to 429 states and 555 transitions. [2024-11-10 23:17:14,888 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 130 [2024-11-10 23:17:14,889 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-10 23:17:14,889 INFO L73 IsDeterministic]: Start isDeterministic. Operand 429 states and 555 transitions. [2024-11-10 23:17:14,889 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:14,889 INFO L218 hiAutomatonCegarLoop]: Abstraction has 429 states and 555 transitions. [2024-11-10 23:17:14,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 429 states and 555 transitions. [2024-11-10 23:17:14,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 429 to 419. [2024-11-10 23:17:14,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 419 states, 260 states have (on average 1.0846153846153845) internal successors, (282), 269 states have internal predecessors, (282), 105 states have call successors, (113), 55 states have call predecessors, (113), 54 states have return successors, (149), 94 states have call predecessors, (149), 94 states have call successors, (149) [2024-11-10 23:17:14,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 419 states to 419 states and 544 transitions. [2024-11-10 23:17:14,904 INFO L240 hiAutomatonCegarLoop]: Abstraction has 419 states and 544 transitions. [2024-11-10 23:17:14,904 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:14,905 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-10 23:17:14,905 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=152, Invalid=660, Unknown=0, NotChecked=0, Total=812 [2024-11-10 23:17:14,905 INFO L87 Difference]: Start difference. First operand 419 states and 544 transitions. Second operand has 29 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 20 states have internal predecessors, (57), 16 states have call successors, (19), 11 states have call predecessors, (19), 4 states have return successors, (10), 5 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-10 23:17:15,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:15,564 INFO L93 Difference]: Finished difference Result 456 states and 518 transitions. [2024-11-10 23:17:15,564 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 456 states and 518 transitions. [2024-11-10 23:17:15,568 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:15,568 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 456 states to 0 states and 0 transitions. [2024-11-10 23:17:15,568 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-10 23:17:15,568 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-10 23:17:15,568 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-10 23:17:15,568 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-10 23:17:15,568 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:15,568 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:15,569 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-10 23:17:15,569 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:15,569 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-10 23:17:15,569 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-10 23:17:15,569 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:15,570 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-10 23:17:15,577 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 10.11 11:17:15 BoogieIcfgContainer [2024-11-10 23:17:15,577 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-10 23:17:15,578 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-10 23:17:15,578 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-10 23:17:15,578 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-10 23:17:15,579 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:00" (3/4) ... [2024-11-10 23:17:15,581 INFO L146 WitnessPrinter]: No result that supports witness generation found [2024-11-10 23:17:15,582 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-10 23:17:15,583 INFO L158 Benchmark]: Toolchain (without parser) took 15568.39ms. Allocated memory was 151.0MB in the beginning and 224.4MB in the end (delta: 73.4MB). Free memory was 94.9MB in the beginning and 129.0MB in the end (delta: -34.1MB). Peak memory consumption was 41.5MB. Max. memory is 16.1GB. [2024-11-10 23:17:15,583 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 151.0MB. Free memory is still 111.0MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:15,583 INFO L158 Benchmark]: CACSL2BoogieTranslator took 239.11ms. Allocated memory is still 151.0MB. Free memory was 94.5MB in the beginning and 82.2MB in the end (delta: 12.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-10 23:17:15,583 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.53ms. Allocated memory is still 151.0MB. Free memory was 82.2MB in the beginning and 80.9MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:15,584 INFO L158 Benchmark]: Boogie Preprocessor took 24.90ms. Allocated memory is still 151.0MB. Free memory was 80.9MB in the beginning and 79.4MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:15,584 INFO L158 Benchmark]: IcfgBuilder took 248.36ms. Allocated memory is still 151.0MB. Free memory was 79.4MB in the beginning and 69.4MB in the end (delta: 10.0MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-10 23:17:15,584 INFO L158 Benchmark]: BuchiAutomizer took 15015.90ms. Allocated memory was 151.0MB in the beginning and 224.4MB in the end (delta: 73.4MB). Free memory was 69.4MB in the beginning and 129.0MB in the end (delta: -59.6MB). Peak memory consumption was 16.4MB. Max. memory is 16.1GB. [2024-11-10 23:17:15,585 INFO L158 Benchmark]: Witness Printer took 4.40ms. Allocated memory is still 224.4MB. Free memory is still 129.0MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:15,586 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.17ms. Allocated memory is still 151.0MB. Free memory is still 111.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 239.11ms. Allocated memory is still 151.0MB. Free memory was 94.5MB in the beginning and 82.2MB in the end (delta: 12.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.53ms. Allocated memory is still 151.0MB. Free memory was 82.2MB in the beginning and 80.9MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 24.90ms. Allocated memory is still 151.0MB. Free memory was 80.9MB in the beginning and 79.4MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 248.36ms. Allocated memory is still 151.0MB. Free memory was 79.4MB in the beginning and 69.4MB in the end (delta: 10.0MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * BuchiAutomizer took 15015.90ms. Allocated memory was 151.0MB in the beginning and 224.4MB in the end (delta: 73.4MB). Free memory was 69.4MB in the beginning and 129.0MB in the end (delta: -59.6MB). Peak memory consumption was 16.4MB. Max. memory is 16.1GB. * Witness Printer took 4.40ms. Allocated memory is still 224.4MB. Free memory is still 129.0MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 11 terminating modules (6 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One nondeterministic module has affine ranking function n and consists of 11 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. One nondeterministic module has affine ranking function n and consists of 6 locations. 6 modules have a trivial ranking function, the largest among these consists of 29 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 14.9s and 8 iterations. TraceHistogramMax:16. Analysis of lassos took 7.8s. Construction of modules took 1.1s. Büchi inclusion checks took 5.6s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 10. Automata minimization 0.2s AutomataMinimizationTime, 10 MinimizatonAttempts, 238 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 602 SdHoareTripleChecker+Valid, 1.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 564 mSDsluCounter, 829 SdHoareTripleChecker+Invalid, 1.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 583 mSDsCounter, 415 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1674 IncrementalHoareTripleChecker+Invalid, 2089 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 415 mSolverCounterUnsat, 246 mSDtfsCounter, 1674 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI2 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital16 mio100 ax100 hnf100 lsp88 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq179 hnf93 smp75 dnf100 smp100 tf111 neg100 sie107 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 21ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-10 23:17:15,611 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (36)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:15,811 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:16,011 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Ended with exit code 0 [2024-11-10 23:17:16,212 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:16,413 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-10 23:17:16,612 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-10 23:17:16,814 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE