./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_10-1.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-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-10 23:16:57,054 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-10 23:16:57,127 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:57,131 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-10 23:16:57,132 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-10 23:16:57,132 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2024-11-10 23:16:57,165 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-10 23:16:57,167 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-10 23:16:57,168 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-10 23:16:57,169 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-10 23:16:57,170 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-10 23:16:57,171 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-10 23:16:57,171 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-10 23:16:57,172 INFO L153 SettingsManager]: * Use SBE=true [2024-11-10 23:16:57,172 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-10 23:16:57,172 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-10 23:16:57,173 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-10 23:16:57,173 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-10 23:16:57,173 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-10 23:16:57,173 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-10 23:16:57,173 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-10 23:16:57,176 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-10 23:16:57,176 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-10 23:16:57,177 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-10 23:16:57,177 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-10 23:16:57,177 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-10 23:16:57,177 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-10 23:16:57,178 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-10 23:16:57,178 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-10 23:16:57,178 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-10 23:16:57,179 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-10 23:16:57,179 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-10 23:16:57,179 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-10 23:16:57,180 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-10 23:16:57,180 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-10 23:16:57,180 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-10 23:16:57,180 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-10 23:16:57,180 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-10 23:16:57,181 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-10 23:16:57,181 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-10 23:16:57,181 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 -> acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 [2024-11-10 23:16:57,429 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-10 23:16:57,454 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-10 23:16:57,457 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-10 23:16:57,458 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-10 23:16:57,459 INFO L274 PluginConnector]: CDTParser initialized [2024-11-10 23:16:57,460 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-11-10 23:16:58,902 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-10 23:16:59,079 INFO L384 CDTParser]: Found 1 translation units. [2024-11-10 23:16:59,079 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-11-10 23:16:59,090 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/357ee90ef/096d79f92ef74bf498145eba1c3c0e45/FLAGd8a30ac95 [2024-11-10 23:16:59,463 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/357ee90ef/096d79f92ef74bf498145eba1c3c0e45 [2024-11-10 23:16:59,465 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-10 23:16:59,467 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-10 23:16:59,469 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-10 23:16:59,469 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-10 23:16:59,474 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-10 23:16:59,475 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,476 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@12c2952d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59, skipping insertion in model container [2024-11-10 23:16:59,476 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,493 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-10 23:16:59,665 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:16:59,681 INFO L200 MainTranslator]: Completed pre-run [2024-11-10 23:16:59,696 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:16:59,714 INFO L204 MainTranslator]: Completed translation [2024-11-10 23:16:59,714 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59 WrapperNode [2024-11-10 23:16:59,714 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-10 23:16:59,715 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-10 23:16:59,715 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-10 23:16:59,716 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-10 23:16:59,722 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:16:59" (1/1) ... [2024-11-10 23:16:59,729 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:16:59" (1/1) ... [2024-11-10 23:16:59,744 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-10 23:16:59,744 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-10 23:16:59,745 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-10 23:16:59,745 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-10 23:16:59,746 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-10 23:16:59,755 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,755 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,756 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,766 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:16:59,767 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,767 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,770 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,773 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,774 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,775 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,777 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-10 23:16:59,778 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-10 23:16:59,779 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-10 23:16:59,779 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-10 23:16:59,780 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (1/1) ... [2024-11-10 23:16:59,785 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:16:59,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:16:59,814 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:16:59,817 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:16:59,872 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-10 23:16:59,872 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-10 23:16:59,872 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-10 23:16:59,872 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-10 23:16:59,873 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-10 23:16:59,873 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-10 23:16:59,924 INFO L256 CfgBuilder]: Building ICFG [2024-11-10 23:16:59,925 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-10 23:17:00,009 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2024-11-10 23:17:00,022 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-10 23:17:00,022 INFO L307 CfgBuilder]: Performing block encoding [2024-11-10 23:17:00,034 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-10 23:17:00,034 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-10 23:17:00,034 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,034 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-10 23:17:00,035 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-10 23:17:00,035 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-10 23:17:00,039 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-10 23:17:00,039 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:00,039 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 10.11 11:16:59" (1/3) ... [2024-11-10 23:17:00,040 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@38cc5d58 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,040 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:00,040 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:16:59" (2/3) ... [2024-11-10 23:17:00,041 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@38cc5d58 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,041 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:00,041 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,042 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_10-1.c [2024-11-10 23:17:00,097 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-10 23:17:00,098 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-10 23:17:00,098 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-10 23:17:00,098 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-10 23:17:00,098 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-10 23:17:00,099 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-10 23:17:00,099 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-10 23:17:00,099 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-10 23:17:00,102 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,121 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:00,122 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:00,122 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:00,128 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:00,128 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:00,128 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-10 23:17:00,129 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,131 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:00,132 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:00,132 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:00,133 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:00,133 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:00,139 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,140 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,148 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:00,149 INFO L85 PathProgramCache]: Analyzing trace with hash 39702, now seen corresponding path program 1 times [2024-11-10 23:17:00,158 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:00,159 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1138677619] [2024-11-10 23:17:00,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:00,163 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:00,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,267 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:00,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,302 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:00,306 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:00,306 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 1 times [2024-11-10 23:17:00,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:00,306 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1334155598] [2024-11-10 23:17:00,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:00,307 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:00,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,319 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:00,323 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,326 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:00,330 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:00,331 INFO L85 PathProgramCache]: Analyzing trace with hash -1988460259, now seen corresponding path program 1 times [2024-11-10 23:17:00,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:00,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237261848] [2024-11-10 23:17:00,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:00,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:00,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,348 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:00,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:00,368 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:00,527 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:00,528 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:00,528 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:00,528 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:00,529 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:00,529 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,529 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:00,529 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:00,529 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-11-10 23:17:00,530 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:00,530 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:00,545 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,557 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,562 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,566 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,571 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,655 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:00,656 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:00,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,660 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:00,662 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:00,663 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:00,664 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:00,686 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:00,686 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:00,702 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-10 23:17:00,703 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,705 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:00,707 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:00,708 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:00,708 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:00,724 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:00,725 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:00,736 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:00,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,738 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:00,740 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:00,740 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:00,740 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:00,753 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:00,753 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:00,769 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:00,770 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,770 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,772 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:00,774 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:00,775 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:00,775 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:00,789 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:00,789 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:00,804 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:00,805 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,808 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:00,810 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:00,811 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:00,811 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:00,842 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:00,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:00,845 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:00,848 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:00,849 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:00,849 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:00,911 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:00,915 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:00,916 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:00,916 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:00,916 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:00,916 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:00,916 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:00,916 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:00,916 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:00,917 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:00,917 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-11-10 23:17:00,917 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:00,917 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:00,919 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,923 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,926 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,935 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:00,938 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:01,001 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:01,007 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:01,008 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,009 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,010 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,012 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,014 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,027 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,028 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,028 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,028 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,029 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,031 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,031 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,033 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,049 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-10 23:17:01,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,051 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,052 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,055 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,067 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,067 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,067 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,067 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,067 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,068 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,068 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,069 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,082 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,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,085 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,086 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,088 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,100 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,101 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,101 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,101 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,101 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,102 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,102 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,105 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,120 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-11-10 23:17:01,121 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,121 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,122 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,124 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,125 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,138 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,138 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,138 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,139 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,139 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,139 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,140 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,143 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:01,158 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-11-10 23:17:01,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,160 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,163 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,163 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,173 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:01,174 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:01,174 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:01,174 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:01,174 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:01,175 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:01,175 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:01,195 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:01,199 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:01,199 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:01,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:01,200 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:01,225 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,226 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,227 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:01,227 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:01,227 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:01,227 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,240 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,243 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:01,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:01,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,286 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-10 23:17:01,287 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:01,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,318 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:01,319 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:01,366 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,401 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,403 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:01,504 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:01,507 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:01,512 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:01,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-10 23:17:01,515 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-10 23:17:01,516 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:01,516 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-10 23:17:01,517 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:01,517 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-10 23:17:01,517 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:01,518 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-10 23:17:01,521 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:01,525 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-10 23:17:01,526 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-10 23:17:01,526 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-10 23:17:01,527 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-10 23:17:01,527 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:01,528 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-10 23:17:01,542 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-10 23:17:01,553 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-10 23:17:01,553 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:01,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-10 23:17:01,558 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:01,559 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:01,560 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-10 23:17:01,560 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-10 23:17:01,561 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:01,561 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:01,561 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:01,562 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:01,562 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:01,564 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:01,564 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:01,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:01,565 INFO L85 PathProgramCache]: Analyzing trace with hash 1475604923, now seen corresponding path program 1 times [2024-11-10 23:17:01,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:01,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [998637132] [2024-11-10 23:17:01,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:01,567 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:01,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,704 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:01,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,749 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:01,750 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:01,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [998637132] [2024-11-10 23:17:01,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [998637132] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:01,751 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:01,751 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:01,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [850227864] [2024-11-10 23:17:01,752 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:01,754 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:01,754 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:01,754 INFO L85 PathProgramCache]: Analyzing trace with hash 93365724, now seen corresponding path program 1 times [2024-11-10 23:17:01,754 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:01,755 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [857216667] [2024-11-10 23:17:01,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:01,755 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:01,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,795 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:01,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:01,825 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:01,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:01,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [857216667] [2024-11-10 23:17:01,825 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [857216667] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:01,825 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:01,826 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:01,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [596851190] [2024-11-10 23:17:01,826 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:01,826 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:01,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:01,828 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-10 23:17:01,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-10 23:17:01,830 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:01,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:01,912 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-10 23:17:01,912 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-10 23:17:01,914 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:01,916 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-10 23:17:01,917 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-10 23:17:01,917 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-10 23:17:01,917 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-10 23:17:01,918 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:01,918 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:01,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-10 23:17:01,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-10 23:17:01,921 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:01,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-10 23:17:01,924 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:01,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 23:17:01,925 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:01,927 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-10 23:17:01,927 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-10 23:17:01,927 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:01,929 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:01,929 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:01,930 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:01,930 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:01,930 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:01,930 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:01,931 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:01,931 INFO L85 PathProgramCache]: Analyzing trace with hash -1500686953, now seen corresponding path program 1 times [2024-11-10 23:17:01,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:01,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [324442362] [2024-11-10 23:17:01,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:01,933 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:01,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,012 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:02,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,060 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,060 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:02,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [324442362] [2024-11-10 23:17:02,061 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [324442362] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:02,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2122501909] [2024-11-10 23:17:02,061 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,061 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:02,062 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:02,063 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,065 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,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:02,097 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:02,098 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:02,142 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,142 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:02,254 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,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2122501909] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:02,255 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:02,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-10 23:17:02,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [713778650] [2024-11-10 23:17:02,256 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:02,257 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:02,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:02,258 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 1 times [2024-11-10 23:17:02,258 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:02,258 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [250625038] [2024-11-10 23:17:02,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:02,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:02,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:02,269 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:02,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:02,283 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:02,578 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:02,579 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:02,579 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:02,579 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:02,579 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:02,579 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:02,579 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:02,579 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:02,579 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-11-10 23:17:02,579 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:02,579 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:02,580 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:02,584 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:02,586 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:02,595 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:02,660 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:02,661 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:02,661 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:02,661 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:02,663 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:02,664 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:02,666 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:02,666 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:02,684 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:02,684 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:02,699 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-10 23:17:02,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:02,700 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:02,701 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:02,703 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:02,704 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:02,704 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:02,718 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:02,718 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:02,733 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:02,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:02,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:02,737 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:02,739 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:02,740 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:02,740 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:02,778 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:02,778 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:02,778 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:02,780 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:02,781 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:02,783 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:02,783 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:03,253 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:03,258 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:03,258 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:03,259 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:03,259 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:03,259 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:03,259 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:03,259 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,259 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:03,259 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:03,259 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-11-10 23:17:03,259 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:03,259 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:03,260 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,271 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,273 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,276 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:03,325 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:03,326 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:03,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,328 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,329 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,330 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,340 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:03,340 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:03,340 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:03,341 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:03,341 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:03,342 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:03,342 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:03,345 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:03,348 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:03,348 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:03,349 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:03,349 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:03,351 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,353 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,354 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:03,354 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:03,354 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:03,354 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:03,369 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,370 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:03,384 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:03,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:03,406 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:03,407 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:03,516 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-10 23:17:03,532 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,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:03,567 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:03,569 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:03,734 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:03,735 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:03,735 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:03,996 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:03,999 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,000 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,001 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-10 23:17:04,001 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,002 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:04,002 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,003 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:04,003 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,005 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:04,005 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-10 23:17:04,017 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:04,022 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-10 23:17:04,022 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-10 23:17:04,023 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-10 23:17:04,024 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-10 23:17:04,024 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:04,024 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-10 23:17:04,025 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-10 23:17:04,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-10 23:17:04,037 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,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-10 23:17:04,039 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-10 23:17:04,039 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:04,039 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-10 23:17:04,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-10 23:17:04,040 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,185 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:04,185 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-10 23:17:04,185 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-10 23:17:04,189 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:04,194 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-10 23:17:04,195 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-10 23:17:04,195 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-10 23:17:04,195 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-10 23:17:04,196 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:04,196 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-10 23:17:04,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-10 23:17:04,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-10 23:17:04,205 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,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-10 23:17:04,207 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:04,207 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:04,208 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:04,208 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-10 23:17:04,208 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-10 23:17:04,211 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:04,211 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:04,211 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:04,212 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,212 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-10 23:17:04,212 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,212 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,213 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:04,213 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 1 times [2024-11-10 23:17:04,213 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:04,213 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2000032066] [2024-11-10 23:17:04,213 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:04,214 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:04,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,341 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:04,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:04,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,420 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:04,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,426 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,427 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:04,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2000032066] [2024-11-10 23:17:04,427 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2000032066] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:04,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1308340845] [2024-11-10 23:17:04,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:04,428 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:04,428 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:04,429 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,431 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,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,470 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:04,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:04,536 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,537 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:04,810 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:04,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1308340845] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:04,810 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:04,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-10 23:17:04,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [159947697] [2024-11-10 23:17:04,811 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:04,811 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:04,811 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:04,812 INFO L85 PathProgramCache]: Analyzing trace with hash -1547808212, now seen corresponding path program 1 times [2024-11-10 23:17:04,812 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:04,812 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237403975] [2024-11-10 23:17:04,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:04,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:04,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,829 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:04,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,852 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:04,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,868 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:04,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,894 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:04,895 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:04,895 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [237403975] [2024-11-10 23:17:04,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [237403975] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:04,895 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113075435] [2024-11-10 23:17:04,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:04,895 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:04,896 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:04,897 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:04,899 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:04,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:04,934 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:04,935 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:04,968 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:04,968 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:05,084 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,085 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113075435] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:05,085 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:05,085 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-10 23:17:05,085 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [14372793] [2024-11-10 23:17:05,085 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:05,086 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:05,086 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:05,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-10 23:17:05,086 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-10 23:17:05,087 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,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:05,196 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-10 23:17:05,196 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-10 23:17:05,197 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:05,198 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-10 23:17:05,199 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-10 23:17:05,199 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-10 23:17:05,199 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-10 23:17:05,199 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:05,199 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:05,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-10 23:17:05,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-10 23:17:05,203 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,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-10 23:17:05,204 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:05,208 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:05,209 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:05,209 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-10 23:17:05,209 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-10 23:17:05,210 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:05,210 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:05,210 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:05,211 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,211 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:05,211 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,211 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,212 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:05,212 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 2 times [2024-11-10 23:17:05,212 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:05,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [327585642] [2024-11-10 23:17:05,213 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:05,213 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:05,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,302 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:05,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,346 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:05,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:05,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:05,369 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,370 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:05,370 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [327585642] [2024-11-10 23:17:05,370 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [327585642] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:05,370 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [897964674] [2024-11-10 23:17:05,370 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-10 23:17:05,370 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:05,371 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:05,372 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,374 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,416 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-10 23:17:05,417 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:05,417 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:05,419 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:05,472 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,472 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:05,728 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,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [897964674] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:05,729 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:05,729 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-10 23:17:05,729 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [25296435] [2024-11-10 23:17:05,730 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:05,730 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:05,732 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:05,732 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 2 times [2024-11-10 23:17:05,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:05,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1595532511] [2024-11-10 23:17:05,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:05,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:05,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:05,738 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:05,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:05,742 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:05,924 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:05,925 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:05,925 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:05,925 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:05,925 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:05,925 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:05,925 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:05,925 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:05,925 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration5_Loop [2024-11-10 23:17:05,925 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:05,925 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:05,926 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:05,929 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:05,934 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:05,936 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:05,938 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:05,974 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:05,975 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:05,975 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:05,975 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:05,977 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:05,979 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:05,981 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:05,981 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:05,994 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:05,995 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,005 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,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,007 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,007 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,008 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:06,008 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:06,032 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2024-11-10 23:17:06,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,032 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,033 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,035 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,035 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:06,035 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:06,047 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:06,058 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-11-10 23:17:06,058 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:06,058 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:06,058 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:06,058 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:06,058 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:06,058 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,058 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:06,058 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:06,058 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration5_Loop [2024-11-10 23:17:06,058 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:06,059 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:06,059 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,065 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,068 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,070 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,071 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:06,099 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:06,099 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:06,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,102 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,103 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,104 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,116 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:06,117 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:06,117 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:06,117 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:06,117 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:06,118 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:06,118 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:06,121 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:06,124 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:06,124 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:06,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:06,124 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:06,126 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,126 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,127 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:06,127 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:06,127 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:06,127 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:06,137 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-11-10 23:17:06,138 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:06,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:06,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:06,187 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:06,188 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:06,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:06,404 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:06,405 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:06,534 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:06,535 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:06,535 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:06,630 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:06,631 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:06,631 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:06,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:06,632 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:06,632 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:06,632 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:06,641 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:06,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:06,684 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:06,685 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:06,715 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:06,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:06,889 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:06,890 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,002 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,003 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,003 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,099 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,100 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,100 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,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:07,101 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,101 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:07,101 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:07,111 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:07,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,149 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,151 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:07,331 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:07,333 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:07,453 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,454 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:07,454 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,691 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:07,693 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:07,693 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,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-10 23:17:07,695 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:07,696 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:07,696 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-10 23:17:07,697 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:07,697 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-10 23:17:07,700 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:07,702 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-10 23:17:07,709 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:07,718 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-10 23:17:07,718 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-10 23:17:07,719 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-10 23:17:07,719 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-10 23:17:07,719 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:07,719 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-10 23:17:07,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-10 23:17:07,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-10 23:17:07,736 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:07,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-10 23:17:07,738 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-10 23:17:07,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:07,739 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-10 23:17:07,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-11-10 23:17:07,740 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,054 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:08,054 INFO L93 Difference]: Finished difference Result 380 states and 491 transitions. [2024-11-10 23:17:08,054 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 380 states and 491 transitions. [2024-11-10 23:17:08,060 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:08,064 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 380 states to 356 states and 457 transitions. [2024-11-10 23:17:08,065 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 177 [2024-11-10 23:17:08,065 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 177 [2024-11-10 23:17:08,065 INFO L73 IsDeterministic]: Start isDeterministic. Operand 356 states and 457 transitions. [2024-11-10 23:17:08,066 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:08,066 INFO L218 hiAutomatonCegarLoop]: Abstraction has 356 states and 457 transitions. [2024-11-10 23:17:08,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 356 states and 457 transitions. [2024-11-10 23:17:08,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 356 to 332. [2024-11-10 23:17:08,093 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,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 428 transitions. [2024-11-10 23:17:08,098 INFO L240 hiAutomatonCegarLoop]: Abstraction has 332 states and 428 transitions. [2024-11-10 23:17:08,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-10 23:17:08,099 INFO L425 stractBuchiCegarLoop]: Abstraction has 332 states and 428 transitions. [2024-11-10 23:17:08,100 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-10 23:17:08,100 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 332 states and 428 transitions. [2024-11-10 23:17:08,102 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:08,102 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:08,102 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:08,103 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,105 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:08,105 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,105 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,106 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:08,106 INFO L85 PathProgramCache]: Analyzing trace with hash -1417466561, now seen corresponding path program 3 times [2024-11-10 23:17:08,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:08,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [571553537] [2024-11-10 23:17:08,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:08,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:08,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:08,388 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-10 23:17:08,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:08,445 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:08,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:08,478 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:08,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:08,484 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:08,486 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:08,486 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [571553537] [2024-11-10 23:17:08,486 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [571553537] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:08,486 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [742518553] [2024-11-10 23:17:08,487 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-10 23:17:08,487 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:08,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:08,489 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:08,491 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:08,535 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-10 23:17:08,535 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:08,536 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-10 23:17:08,537 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:08,636 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:08,637 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:08,878 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:08,880 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [742518553] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:08,880 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:08,880 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 9, 10] total 28 [2024-11-10 23:17:08,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1850682073] [2024-11-10 23:17:08,882 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:08,882 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:08,883 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:08,883 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 2 times [2024-11-10 23:17:08,883 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:08,883 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1702126034] [2024-11-10 23:17:08,883 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:08,883 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:08,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:08,886 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:08,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:08,888 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:08,922 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:08,922 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:08,922 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:08,922 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:08,922 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:08,922 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:08,922 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:08,922 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:08,923 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-11-10 23:17:08,923 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:08,923 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:08,923 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:08,926 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:08,931 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:08,934 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:08,936 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:08,965 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:08,965 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:08,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:08,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:08,968 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:08,969 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:08,970 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:08,970 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:08,984 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:08,984 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:08,998 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:08,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:08,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,001 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,002 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,003 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:09,003 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:09,029 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,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,030 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,031 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,031 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:09,032 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:09,083 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:09,088 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,088 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:09,088 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:09,088 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:09,088 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:09,088 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:09,089 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,089 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:09,089 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:09,089 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-11-10 23:17:09,089 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:09,089 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:09,090 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,092 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,098 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,100 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,102 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:09,127 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:09,127 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:09,128 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,128 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,129 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,130 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,131 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,140 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:09,141 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:09,141 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:09,141 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:09,141 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:09,141 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:09,141 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:09,143 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:09,153 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,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,156 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,157 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,158 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,172 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:09,172 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:09,172 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:09,172 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:09,172 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:09,173 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:09,174 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:09,177 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:09,182 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:09,182 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:09,182 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:09,183 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:09,185 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,186 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,187 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:09,187 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:09,187 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:09,188 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,202 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2024-11-10 23:17:09,203 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:09,218 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:09,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,291 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-10 23:17:09,293 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:09,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,483 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:09,483 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:09,533 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:09,534 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:09,534 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:09,537 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:09,592 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:09,593 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:09,594 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:09,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:09,594 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-10 23:17:09,595 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:09,595 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:09,609 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:09,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,682 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-10 23:17:09,684 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:09,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:09,905 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:09,906 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:09,928 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:09,929 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:09,929 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:09,988 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:09,988 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:09,989 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:09,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:09,989 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-10 23:17:09,989 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:09,989 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:10,001 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:10,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,068 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,070 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:10,248 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:10,248 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:10,272 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,273 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,273 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,343 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,345 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,345 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,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-10 23:17:10,347 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,347 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,347 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,348 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,348 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,348 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:10,348 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 441 states and 538 transitions. [2024-11-10 23:17:10,355 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:10,359 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 441 states to 342 states and 438 transitions. [2024-11-10 23:17:10,359 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 138 [2024-11-10 23:17:10,360 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-10 23:17:10,360 INFO L73 IsDeterministic]: Start isDeterministic. Operand 342 states and 438 transitions. [2024-11-10 23:17:10,361 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:10,361 INFO L218 hiAutomatonCegarLoop]: Abstraction has 342 states and 438 transitions. [2024-11-10 23:17:10,361 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states and 438 transitions. [2024-11-10 23:17:10,369 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 340. [2024-11-10 23:17:10,370 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:10,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 340 states to 340 states and 436 transitions. [2024-11-10 23:17:10,372 INFO L240 hiAutomatonCegarLoop]: Abstraction has 340 states and 436 transitions. [2024-11-10 23:17:10,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:10,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-10 23:17:10,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=625, Unknown=0, NotChecked=0, Total=756 [2024-11-10 23:17:10,373 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:10,795 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:10,796 INFO L93 Difference]: Finished difference Result 552 states and 741 transitions. [2024-11-10 23:17:10,796 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 552 states and 741 transitions. [2024-11-10 23:17:10,802 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:10,808 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 552 states to 517 states and 697 transitions. [2024-11-10 23:17:10,808 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 199 [2024-11-10 23:17:10,809 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 212 [2024-11-10 23:17:10,809 INFO L73 IsDeterministic]: Start isDeterministic. Operand 517 states and 697 transitions. [2024-11-10 23:17:10,809 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:10,809 INFO L218 hiAutomatonCegarLoop]: Abstraction has 517 states and 697 transitions. [2024-11-10 23:17:10,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 517 states and 697 transitions. [2024-11-10 23:17:10,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 517 to 421. [2024-11-10 23:17:10,825 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:10,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 421 states to 421 states and 546 transitions. [2024-11-10 23:17:10,829 INFO L240 hiAutomatonCegarLoop]: Abstraction has 421 states and 546 transitions. [2024-11-10 23:17:10,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-10 23:17:10,830 INFO L425 stractBuchiCegarLoop]: Abstraction has 421 states and 546 transitions. [2024-11-10 23:17:10,830 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-10 23:17:10,830 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 421 states and 546 transitions. [2024-11-10 23:17:10,833 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:10,833 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:10,833 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:10,834 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:10,834 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:10,835 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:10,835 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:10,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:10,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1215864849, now seen corresponding path program 4 times [2024-11-10 23:17:10,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:10,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1431282444] [2024-11-10 23:17:10,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:10,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:10,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,163 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-10 23:17:11,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,172 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:11,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,176 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:11,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,177 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:11,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,179 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-10 23:17:11,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:11,181 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,181 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:11,181 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1431282444] [2024-11-10 23:17:11,181 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1431282444] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:11,181 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1268139177] [2024-11-10 23:17:11,182 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-10 23:17:11,182 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:11,182 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:11,184 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,191 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,253 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-10 23:17:11,254 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:11,255 INFO L255 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:11,257 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:11,388 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:11,388 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:11,851 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:11,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1268139177] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:11,852 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:11,852 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23, 25] total 29 [2024-11-10 23:17:11,852 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [919929786] [2024-11-10 23:17:11,852 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:11,853 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:11,853 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:11,853 INFO L85 PathProgramCache]: Analyzing trace with hash 1717914, now seen corresponding path program 3 times [2024-11-10 23:17:11,853 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:11,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [142755053] [2024-11-10 23:17:11,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:11,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:11,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:11,856 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:11,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:11,858 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:11,900 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:11,900 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:11,900 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:11,900 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:11,901 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:11,901 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:11,901 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:11,901 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:11,901 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-11-10 23:17:11,901 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:11,901 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:11,901 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:11,903 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:11,913 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:11,915 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:11,941 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:11,941 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:11,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:11,941 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:11,943 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:11,944 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:11,946 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:11,946 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:11,957 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:11,958 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:11,968 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:11,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:11,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:11,969 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:11,970 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:11,971 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:11,971 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:11,999 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:11,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:11,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,000 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,001 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,002 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:12,002 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:12,639 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:12,644 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:12,644 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:12,645 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:12,645 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:12,645 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:12,645 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:12,645 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,645 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:12,645 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:12,645 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-11-10 23:17:12,645 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:12,645 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:12,646 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,648 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,654 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,655 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:12,681 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:12,682 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:12,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,682 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,686 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:12,689 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:12,690 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:12,699 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:12,699 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:12,699 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:12,699 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:12,699 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:12,700 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:12,700 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:12,701 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:12,711 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:12,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,712 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:12,713 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:12,713 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:12,723 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:12,723 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:12,723 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:12,723 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:12,723 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:12,724 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:12,724 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:12,726 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:12,728 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:12,728 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:12,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:12,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:12,730 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:12,731 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:12,731 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:12,731 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:12,731 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:12,731 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:12,744 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:12,745 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:12,753 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:12,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:12,831 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 23:17:12,833 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:13,095 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Ended with exit code 0 [2024-11-10 23:17:13,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:13,121 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:13,121 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:13,152 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,153 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,153 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,202 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,202 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,203 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,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-10 23:17:13,203 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,203 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:13,204 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:13,213 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:13,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:13,297 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 23:17:13,300 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:13,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:13,566 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:13,567 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:13,598 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 23:17:13,598 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:13,598 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,678 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:13,679 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:13,680 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,680 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-10 23:17:13,681 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-10 23:17:13,681 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:13,681 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:13,691 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:13,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:13,778 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 23:17:13,780 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:14,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:14,057 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:14,058 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:14,089 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,090 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,090 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,153 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,154 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,155 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,155 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 20 transitions. [2024-11-10 23:17:14,155 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,155 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,155 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,156 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,156 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,156 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:14,156 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 558 states and 718 transitions. [2024-11-10 23:17:14,162 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:14,166 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 558 states to 429 states and 555 transitions. [2024-11-10 23:17:14,166 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 130 [2024-11-10 23:17:14,166 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-10 23:17:14,167 INFO L73 IsDeterministic]: Start isDeterministic. Operand 429 states and 555 transitions. [2024-11-10 23:17:14,167 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:14,167 INFO L218 hiAutomatonCegarLoop]: Abstraction has 429 states and 555 transitions. [2024-11-10 23:17:14,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 429 states and 555 transitions. [2024-11-10 23:17:14,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 429 to 419. [2024-11-10 23:17:14,177 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,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 419 states to 419 states and 544 transitions. [2024-11-10 23:17:14,179 INFO L240 hiAutomatonCegarLoop]: Abstraction has 419 states and 544 transitions. [2024-11-10 23:17:14,179 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:14,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-10 23:17:14,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=152, Invalid=660, Unknown=0, NotChecked=0, Total=812 [2024-11-10 23:17:14,180 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:14,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:14,817 INFO L93 Difference]: Finished difference Result 456 states and 518 transitions. [2024-11-10 23:17:14,817 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 456 states and 518 transitions. [2024-11-10 23:17:14,821 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:14,821 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 456 states to 0 states and 0 transitions. [2024-11-10 23:17:14,821 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-10 23:17:14,822 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-10 23:17:14,822 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-10 23:17:14,822 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-10 23:17:14,822 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:14,822 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:14,822 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-10 23:17:14,823 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:14,823 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-10 23:17:14,823 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-10 23:17:14,823 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:14,823 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-10 23:17:14,831 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 10.11 11:17:14 BoogieIcfgContainer [2024-11-10 23:17:14,831 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-10 23:17:14,832 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-10 23:17:14,832 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-10 23:17:14,832 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-10 23:17:14,832 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:14,834 INFO L146 WitnessPrinter]: No result that supports witness generation found [2024-11-10 23:17:14,835 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-10 23:17:14,836 INFO L158 Benchmark]: Toolchain (without parser) took 15369.13ms. Allocated memory was 184.5MB in the beginning and 289.4MB in the end (delta: 104.9MB). Free memory was 126.9MB in the beginning and 212.2MB in the end (delta: -85.3MB). Peak memory consumption was 21.3MB. Max. memory is 16.1GB. [2024-11-10 23:17:14,836 INFO L158 Benchmark]: CDTParser took 0.20ms. Allocated memory is still 184.5MB. Free memory is still 148.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:14,836 INFO L158 Benchmark]: CACSL2BoogieTranslator took 245.98ms. Allocated memory is still 184.5MB. Free memory was 126.9MB in the beginning and 115.1MB in the end (delta: 11.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-10 23:17:14,836 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.25ms. Allocated memory is still 184.5MB. Free memory was 115.1MB in the beginning and 113.9MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:14,837 INFO L158 Benchmark]: Boogie Preprocessor took 31.90ms. Allocated memory is still 184.5MB. Free memory was 113.5MB in the beginning and 112.2MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:14,838 INFO L158 Benchmark]: IcfgBuilder took 256.78ms. Allocated memory is still 184.5MB. Free memory was 112.2MB in the beginning and 101.8MB in the end (delta: 10.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-10 23:17:14,838 INFO L158 Benchmark]: BuchiAutomizer took 14795.76ms. Allocated memory was 184.5MB in the beginning and 289.4MB in the end (delta: 104.9MB). Free memory was 101.8MB in the beginning and 212.2MB in the end (delta: -110.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:14,838 INFO L158 Benchmark]: Witness Printer took 3.66ms. Allocated memory is still 289.4MB. Free memory is still 212.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:14,839 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.20ms. Allocated memory is still 184.5MB. Free memory is still 148.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 245.98ms. Allocated memory is still 184.5MB. Free memory was 126.9MB in the beginning and 115.1MB in the end (delta: 11.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.25ms. Allocated memory is still 184.5MB. Free memory was 115.1MB in the beginning and 113.9MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 31.90ms. Allocated memory is still 184.5MB. Free memory was 113.5MB in the beginning and 112.2MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 256.78ms. Allocated memory is still 184.5MB. Free memory was 112.2MB in the beginning and 101.8MB in the end (delta: 10.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 14795.76ms. Allocated memory was 184.5MB in the beginning and 289.4MB in the end (delta: 104.9MB). Free memory was 101.8MB in the beginning and 212.2MB in the end (delta: -110.4MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.66ms. Allocated memory is still 289.4MB. Free memory is still 212.2MB. 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.7s and 8 iterations. TraceHistogramMax:16. Analysis of lassos took 7.6s. Construction of modules took 1.2s. 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.1s 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: 25ms 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:14,862 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,065 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Ended with exit code 0 [2024-11-10 23:17:15,265 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:15,466 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Ended with exit code 0 [2024-11-10 23:17:15,666 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-10 23:17:15,867 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,068 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