./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_5-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-simple/fibo_5-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 02dc726982da9e300f34803a4bdbb3c0165037d3f4471bd0e009c42cfb19ed24 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 16:05:29,780 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 16:05:29,846 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-09 16:05:29,849 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 16:05:29,852 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 16:05:29,876 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 16:05:29,877 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 16:05:29,877 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 16:05:29,878 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 16:05:29,879 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 16:05:29,879 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 16:05:29,879 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 16:05:29,880 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 16:05:29,880 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 16:05:29,881 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 16:05:29,881 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 16:05:29,882 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 16:05:29,882 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 16:05:29,882 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 16:05:29,882 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 16:05:29,882 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 16:05:29,885 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 16:05:29,886 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 16:05:29,886 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 16:05:29,886 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 16:05:29,886 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 16:05:29,886 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 16:05:29,887 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 16:05:29,888 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 16:05:29,888 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 16:05:29,888 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 16:05:29,888 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 16:05:29,889 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 16:05:29,889 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 -> 02dc726982da9e300f34803a4bdbb3c0165037d3f4471bd0e009c42cfb19ed24 [2024-11-09 16:05:30,098 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 16:05:30,125 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 16:05:30,127 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 16:05:30,128 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 16:05:30,128 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 16:05:30,129 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_5-2.c [2024-11-09 16:05:31,407 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 16:05:31,563 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 16:05:31,563 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-2.c [2024-11-09 16:05:31,570 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/08cd910d1/5be7dcd46aa04127bf341f49a1ffabda/FLAG8a7555a45 [2024-11-09 16:05:31,969 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/08cd910d1/5be7dcd46aa04127bf341f49a1ffabda [2024-11-09 16:05:31,971 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 16:05:31,973 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 16:05:31,975 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 16:05:31,976 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 16:05:31,981 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 16:05:31,982 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,983 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48226bd3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:31, skipping insertion in model container [2024-11-09 16:05:31,983 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:05:31" (1/1) ... [2024-11-09 16:05:31,997 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 16:05:32,145 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:05:32,156 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 16:05:32,167 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:05:32,182 INFO L204 MainTranslator]: Completed translation [2024-11-09 16:05:32,182 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32 WrapperNode [2024-11-09 16:05:32,183 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 16:05:32,183 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 16:05:32,183 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 16:05:32,184 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 16:05:32,189 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,195 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,209 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-09 16:05:32,209 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 16:05:32,210 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 16:05:32,210 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 16:05:32,210 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 16:05:32,218 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,218 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,219 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,227 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 16:05:32,227 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,228 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,229 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,231 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,233 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,234 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,235 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 16:05:32,236 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 16:05:32,236 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 16:05:32,236 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 16:05:32,237 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (1/1) ... [2024-11-09 16:05:32,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:32,276 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:32,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-09 16:05:32,325 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 16:05:32,326 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 16:05:32,326 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 16:05:32,326 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 16:05:32,326 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-09 16:05:32,326 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-09 16:05:32,379 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 16:05:32,381 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 16:05:32,510 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 16:05:32,510 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 16:05:32,524 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 16:05:32,524 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 16:05:32,525 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:32 BoogieIcfgContainer [2024-11-09 16:05:32,525 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 16:05:32,526 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 16:05:32,527 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 16:05:32,547 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 16:05:32,548 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:32,549 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 04:05:31" (1/3) ... [2024-11-09 16:05:32,550 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@31637290 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:05:32, skipping insertion in model container [2024-11-09 16:05:32,550 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:32,551 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:05:32" (2/3) ... [2024-11-09 16:05:32,551 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@31637290 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:05:32, skipping insertion in model container [2024-11-09 16:05:32,551 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:05:32,552 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:32" (3/3) ... [2024-11-09 16:05:32,553 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_5-2.c [2024-11-09 16:05:32,605 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 16:05:32,605 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 16:05:32,605 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 16:05:32,605 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 16:05:32,606 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 16:05:32,606 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 16:05:32,606 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 16:05:32,606 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 16:05:32,611 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 16:05:32,629 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:32,629 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:32,629 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:32,634 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:05:32,634 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:32,635 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 16:05:32,635 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 16:05:32,637 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:32,637 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:32,638 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:32,639 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:05:32,639 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 16:05:32,645 INFO L745 eck$LassoCheckResult]: Stem: 17#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 9#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 4#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 11#$Ultimate##0true [2024-11-09 16:05:32,645 INFO L747 eck$LassoCheckResult]: Loop: 11#$Ultimate##0true ~n := #in~n; 5#L8true assume !(~n < 1); 7#L10true assume !(1 == ~n); 13#L13true call #t~ret4 := fibo(~n - 1);< 11#$Ultimate##0true [2024-11-09 16:05:32,651 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:32,651 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-11-09 16:05:32,661 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:32,662 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [703261209] [2024-11-09 16:05:32,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:32,663 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:32,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,754 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:32,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,780 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:32,782 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:32,782 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-11-09 16:05:32,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:32,783 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1085497412] [2024-11-09 16:05:32,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:32,783 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:32,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,791 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:32,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,798 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:32,803 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:32,803 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-11-09 16:05:32,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:32,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [347949543] [2024-11-09 16:05:32,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:32,804 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:32,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,821 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:32,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:32,831 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:32,937 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:32,938 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:32,939 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:32,939 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:32,939 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:32,939 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:32,939 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:32,939 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:32,940 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2024-11-09 16:05:32,940 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:32,940 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:32,953 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,975 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,983 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,987 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:32,999 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:33,049 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:33,050 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:33,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,052 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,054 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,054 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-09 16:05:33,055 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:33,056 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:33,071 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:33,071 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:33,084 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-09 16:05:33,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,090 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,092 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-09 16:05:33,093 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:33,093 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:33,105 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:33,105 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:33,116 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-09 16:05:33,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,118 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,119 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-09 16:05:33,121 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:33,121 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:33,132 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:33,132 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:33,143 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-09 16:05:33,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,146 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,147 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-09 16:05:33,148 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:33,148 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:33,169 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-09 16:05:33,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,170 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,171 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-09 16:05:33,172 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:33,172 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:33,225 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:33,230 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-09 16:05:33,230 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:33,230 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:33,230 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:33,230 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:33,230 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:33,230 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,230 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:33,231 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:33,231 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2024-11-09 16:05:33,231 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:33,231 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:33,232 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:33,236 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:33,238 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:33,243 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:33,253 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:33,297 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:33,301 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:33,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,304 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,305 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-09 16:05:33,306 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:33,316 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:33,317 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:33,317 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:33,317 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:33,317 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:33,319 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:33,319 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:33,325 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:33,336 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-09 16:05:33,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,338 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,339 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-09 16:05:33,339 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:33,349 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:33,349 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:33,350 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:33,350 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:33,350 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:33,350 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:33,350 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:33,352 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:33,363 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:33,363 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,363 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,364 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,365 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-09 16:05:33,366 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:33,376 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:33,376 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:33,376 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:33,376 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:33,376 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:33,376 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:33,377 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:33,378 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:33,391 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-09 16:05:33,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,394 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-09 16:05:33,395 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:33,405 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:33,405 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:33,405 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:33,405 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:33,405 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:33,406 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:33,406 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:33,409 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:33,412 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:33,412 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:33,414 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:33,414 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:33,435 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:33,436 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-09 16:05:33,437 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:33,437 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:33,438 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:33,438 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-09 16:05:33,448 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:33,451 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:33,476 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,504 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 16:05:33,505 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:33,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,534 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:33,535 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:33,585 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:33,610 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-09 16:05:33,612 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:05:33,643 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-09 16:05:33,756 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 41 states and 54 transitions. Complement of second has 16 states. [2024-11-09 16:05:33,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:33,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:05:33,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-09 16:05:33,768 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-09 16:05:33,769 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:33,769 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-09 16:05:33,769 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:33,769 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-09 16:05:33,770 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:33,770 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-09 16:05:33,773 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:33,780 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-09 16:05:33,782 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-09 16:05:33,782 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-09 16:05:33,783 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-09 16:05:33,784 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:33,784 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-09 16:05:33,797 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-09 16:05:33,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-09 16:05:33,805 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:33,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-09 16:05:33,807 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:05:33,807 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-09 16:05:33,807 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 16:05:33,808 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-09 16:05:33,808 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:33,808 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:33,808 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:33,809 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:33,809 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:33,809 INFO L745 eck$LassoCheckResult]: Stem: 135#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 136#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 121#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 120#$Ultimate##0 ~n := #in~n; 122#L8 assume !(~n < 1); 134#L10 assume !(1 == ~n); 124#L13 call #t~ret4 := fibo(~n - 1);< 123#$Ultimate##0 ~n := #in~n; 125#L8 assume ~n < 1;#res := 0; 131#fiboFINAL assume true; 132#fiboEXIT >#35#return; 127#L13-1 [2024-11-09 16:05:33,809 INFO L747 eck$LassoCheckResult]: Loop: 127#L13-1 call #t~ret5 := fibo(~n - 2);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume !(~n < 1); 139#L10 assume !(1 == ~n); 126#L13 call #t~ret4 := fibo(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume ~n < 1;#res := 0; 130#fiboFINAL assume true; 137#fiboEXIT >#35#return; 127#L13-1 [2024-11-09 16:05:33,810 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,810 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-11-09 16:05:33,810 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:33,810 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [929599450] [2024-11-09 16:05:33,810 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,810 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:33,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,902 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:05:33,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:33,948 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 16:05:33,948 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:33,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [929599450] [2024-11-09 16:05:33,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [929599450] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:33,950 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:33,950 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:05:33,950 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [782284302] [2024-11-09 16:05:33,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:33,955 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:33,956 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:33,956 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-11-09 16:05:33,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:33,957 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [711483243] [2024-11-09 16:05:33,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:33,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:33,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,008 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:34,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,032 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 16:05:34,033 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:34,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [711483243] [2024-11-09 16:05:34,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [711483243] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:34,033 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:34,033 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 16:05:34,033 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [640937280] [2024-11-09 16:05:34,033 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:34,033 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:34,034 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:34,040 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 16:05:34,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-09 16:05:34,041 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:34,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:34,094 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-09 16:05:34,094 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-09 16:05:34,095 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:34,096 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-09 16:05:34,096 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-09 16:05:34,096 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-09 16:05:34,096 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-09 16:05:34,096 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:34,097 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:34,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-09 16:05:34,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 16:05:34,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-09 16:05:34,099 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-09 16:05:34,099 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:34,099 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 16:05:34,100 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-09 16:05:34,100 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 16:05:34,100 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-09 16:05:34,101 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:34,101 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:34,101 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:34,101 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:34,101 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:34,102 INFO L745 eck$LassoCheckResult]: Stem: 205#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 206#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 199#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 202#$Ultimate##0 ~n := #in~n; 197#L8 assume !(~n < 1); 208#L10 assume !(1 == ~n); 196#L13 call #t~ret4 := fibo(~n - 1);< 195#$Ultimate##0 ~n := #in~n; 198#L8 assume !(~n < 1); 214#L10 assume 1 == ~n;#res := 1; 213#fiboFINAL assume true; 211#fiboEXIT >#35#return; 192#L13-1 [2024-11-09 16:05:34,102 INFO L747 eck$LassoCheckResult]: Loop: 192#L13-1 call #t~ret5 := fibo(~n - 2);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume !(1 == ~n); 193#L13 call #t~ret4 := fibo(~n - 1);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume 1 == ~n;#res := 1; 209#fiboFINAL assume true; 210#fiboEXIT >#35#return; 192#L13-1 [2024-11-09 16:05:34,102 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:34,102 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-11-09 16:05:34,102 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:34,102 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1858607185] [2024-11-09 16:05:34,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:34,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:34,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,141 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 16:05:34,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,172 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:34,172 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:34,172 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1858607185] [2024-11-09 16:05:34,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1858607185] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:34,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [61515243] [2024-11-09 16:05:34,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:34,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:34,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,175 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,176 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 16:05:34,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,210 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:34,210 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:34,246 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:34,247 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:34,351 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:34,351 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [61515243] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:34,352 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:34,352 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-09 16:05:34,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1033025023] [2024-11-09 16:05:34,352 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:34,352 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:34,353 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:34,353 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-11-09 16:05:34,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:34,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [859336479] [2024-11-09 16:05:34,353 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:34,353 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:34,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:34,360 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:34,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:34,365 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:34,469 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:34,469 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:34,469 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:34,469 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:34,469 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:34,469 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,470 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:34,470 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:34,470 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2024-11-09 16:05:34,470 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:34,470 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:34,471 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,475 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,476 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,483 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,488 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,519 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:34,519 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:34,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,521 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-09 16:05:34,523 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,524 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,535 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:34,536 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#in~n=2} Honda state: {fibo_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:34,546 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-09 16:05:34,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,547 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,549 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-09 16:05:34,550 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,551 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,564 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:34,566 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:34,581 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-09 16:05:34,581 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,581 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,583 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,585 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-09 16:05:34,586 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,587 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,599 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:34,600 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:34,614 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-09 16:05:34,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,614 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,618 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,619 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-09 16:05:34,624 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:34,624 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,647 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,648 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,652 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-09 16:05:34,653 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:34,653 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:34,669 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:34,680 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-09 16:05:34,681 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:34,681 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:34,681 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:34,681 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:34,682 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:34,682 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,682 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:34,682 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:34,682 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2024-11-09 16:05:34,682 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:34,682 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:34,685 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,688 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,691 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,693 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,695 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:34,738 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:34,738 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:34,738 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,738 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,740 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,741 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-11-09 16:05:34,742 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,752 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,752 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,752 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,752 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,752 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,753 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,754 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,755 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,766 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-09 16:05:34,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,768 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,769 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-09 16:05:34,770 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,780 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,781 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,781 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,781 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,781 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,782 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,782 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,783 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,794 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-09 16:05:34,794 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,794 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,795 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,796 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-09 16:05:34,797 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,807 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,808 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,808 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,808 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,808 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,808 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,808 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,810 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,820 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,821 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,821 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,822 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,824 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-11-09 16:05:34,824 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,834 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,834 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,834 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,834 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,834 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,835 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,835 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,836 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:34,847 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-11-09 16:05:34,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,848 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,849 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,851 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-09 16:05:34,852 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:34,866 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:34,866 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:34,866 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:34,866 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:34,866 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:34,867 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:34,867 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:34,869 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:34,872 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:34,872 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:34,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:34,872 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:34,874 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:34,876 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-09 16:05:34,876 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:34,876 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:34,876 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:34,876 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-09 16:05:34,889 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:34,890 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:34,905 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:34,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:34,926 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:34,927 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:35,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,017 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 16:05:35,018 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:35,090 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:35,091 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-09 16:05:35,091 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:35,283 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 128 states and 178 transitions. Complement of second has 40 states. [2024-11-09 16:05:35,284 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:35,284 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:35,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-11-09 16:05:35,285 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-11-09 16:05:35,285 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:35,285 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-11-09 16:05:35,286 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:35,286 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-11-09 16:05:35,286 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:35,286 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-11-09 16:05:35,291 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:35,297 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-11-09 16:05:35,299 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-11-09 16:05:35,300 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-11-09 16:05:35,300 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-11-09 16:05:35,300 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:35,300 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-11-09 16:05:35,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-11-09 16:05:35,313 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-11-09 16:05:35,314 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (35), 18 states have call predecessors, (35), 19 states have call successors, (35) [2024-11-09 16:05:35,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-11-09 16:05:35,317 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-11-09 16:05:35,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:35,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 16:05:35,317 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-09 16:05:35,318 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:35,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:35,432 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-11-09 16:05:35,432 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-11-09 16:05:35,435 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:35,437 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-11-09 16:05:35,437 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-09 16:05:35,438 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-09 16:05:35,438 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-11-09 16:05:35,438 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:35,438 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-11-09 16:05:35,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-11-09 16:05:35,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-11-09 16:05:35,444 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (39), 20 states have call predecessors, (39), 22 states have call successors, (39) [2024-11-09 16:05:35,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-11-09 16:05:35,446 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-09 16:05:35,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:05:35,451 INFO L425 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-11-09 16:05:35,451 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 16:05:35,451 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-11-09 16:05:35,453 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 16:05:35,455 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:35,455 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:35,456 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:35,456 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-09 16:05:35,457 INFO L745 eck$LassoCheckResult]: Stem: 806#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 807#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 792#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 793#$Ultimate##0 ~n := #in~n; 809#L8 assume !(~n < 1); 810#L10 assume !(1 == ~n); 780#L13 call #t~ret4 := fibo(~n - 1);< 779#$Ultimate##0 ~n := #in~n; 781#L8 assume !(~n < 1); 816#L10 assume !(1 == ~n); 790#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 839#L8 assume !(~n < 1); 837#L10 assume 1 == ~n;#res := 1; 835#fiboFINAL assume true; 834#fiboEXIT >#35#return; 817#L13-1 call #t~ret5 := fibo(~n - 2);< 833#$Ultimate##0 ~n := #in~n; 879#L8 assume ~n < 1;#res := 0; 878#fiboFINAL assume true; 877#fiboEXIT >#37#return; 875#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 872#fiboFINAL assume true; 864#fiboEXIT >#35#return; 813#L13-1 [2024-11-09 16:05:35,457 INFO L747 eck$LassoCheckResult]: Loop: 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#35#return; 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#37#return; 862#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 871#fiboFINAL assume true; 865#fiboEXIT >#35#return; 813#L13-1 [2024-11-09 16:05:35,457 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,457 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-11-09 16:05:35,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,457 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [620796093] [2024-11-09 16:05:35,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,457 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,471 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:35,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,480 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:35,480 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,480 INFO L85 PathProgramCache]: Analyzing trace with hash -1138642743, now seen corresponding path program 1 times [2024-11-09 16:05:35,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,481 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1821588019] [2024-11-09 16:05:35,481 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,481 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,538 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 16:05:35,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,543 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2024-11-09 16:05:35,601 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:35,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,635 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:35,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,657 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-09 16:05:35,658 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:35,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1821588019] [2024-11-09 16:05:35,658 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1821588019] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:35,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1338210315] [2024-11-09 16:05:35,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:35,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:35,660 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:35,661 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2024-11-09 16:05:35,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,688 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:35,689 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:35,713 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-09 16:05:35,713 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:35,840 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-09 16:05:35,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1338210315] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:35,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:35,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-09 16:05:35,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1434527200] [2024-11-09 16:05:35,841 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:35,841 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 16:05:35,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:35,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-09 16:05:35,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-09 16:05:35,842 INFO L87 Difference]: Start difference. First operand 106 states and 143 transitions. cyclomatic complexity: 42 Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 2 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 16:05:35,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:35,924 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-09 16:05:35,924 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-09 16:05:35,925 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:35,926 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-09 16:05:35,926 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-09 16:05:35,926 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-09 16:05:35,926 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-09 16:05:35,926 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:35,926 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:35,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-09 16:05:35,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-09 16:05:35,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-09 16:05:35,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-09 16:05:35,931 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:35,933 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 16:05:35,934 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-09 16:05:35,934 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 16:05:35,934 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-09 16:05:35,935 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 16:05:35,935 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:35,935 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:35,935 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:35,935 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-09 16:05:35,936 INFO L745 eck$LassoCheckResult]: Stem: 1144#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 1145#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 1138#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1139#$Ultimate##0 ~n := #in~n; 1154#L8 assume !(~n < 1); 1153#L10 assume !(1 == ~n); 1126#L13 call #t~ret4 := fibo(~n - 1);< 1125#$Ultimate##0 ~n := #in~n; 1127#L8 assume !(~n < 1); 1147#L10 assume !(1 == ~n); 1131#L13 call #t~ret4 := fibo(~n - 1);< 1132#$Ultimate##0 ~n := #in~n; 1152#L8 assume !(~n < 1); 1169#L10 assume !(1 == ~n); 1142#L13 call #t~ret4 := fibo(~n - 1);< 1132#$Ultimate##0 ~n := #in~n; 1152#L8 assume !(~n < 1); 1169#L10 assume !(1 == ~n); 1142#L13 call #t~ret4 := fibo(~n - 1);< 1132#$Ultimate##0 ~n := #in~n; 1151#L8 assume !(~n < 1); 1148#L10 assume 1 == ~n;#res := 1; 1149#fiboFINAL assume true; 1141#fiboEXIT >#35#return; 1143#L13-1 call #t~ret5 := fibo(~n - 2);< 1168#$Ultimate##0 ~n := #in~n; 1175#L8 assume ~n < 1;#res := 0; 1173#fiboFINAL assume true; 1167#fiboEXIT >#37#return; 1165#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1164#fiboFINAL assume true; 1161#fiboEXIT >#35#return; 1134#L13-1 [2024-11-09 16:05:35,936 INFO L747 eck$LassoCheckResult]: Loop: 1134#L13-1 call #t~ret5 := fibo(~n - 2);< 1130#$Ultimate##0 ~n := #in~n; 1172#L8 assume !(~n < 1); 1170#L10 assume !(1 == ~n); 1136#L13 call #t~ret4 := fibo(~n - 1);< 1130#$Ultimate##0 ~n := #in~n; 1172#L8 assume !(~n < 1); 1170#L10 assume !(1 == ~n); 1136#L13 call #t~ret4 := fibo(~n - 1);< 1130#$Ultimate##0 ~n := #in~n; 1172#L8 assume !(~n < 1); 1170#L10 assume 1 == ~n;#res := 1; 1171#fiboFINAL assume true; 1166#fiboEXIT >#35#return; 1123#L13-1 call #t~ret5 := fibo(~n - 2);< 1122#$Ultimate##0 ~n := #in~n; 1124#L8 assume ~n < 1;#res := 0; 1146#fiboFINAL assume true; 1174#fiboEXIT >#37#return; 1133#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1137#fiboFINAL assume true; 1140#fiboEXIT >#35#return; 1134#L13-1 [2024-11-09 16:05:35,936 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,936 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 2 times [2024-11-09 16:05:35,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,936 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1538764322] [2024-11-09 16:05:35,936 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,936 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,949 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:35,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,961 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:35,961 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,961 INFO L85 PathProgramCache]: Analyzing trace with hash -2000232554, now seen corresponding path program 1 times [2024-11-09 16:05:35,962 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [41713826] [2024-11-09 16:05:35,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,962 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,972 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:35,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:35,980 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:35,980 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,980 INFO L85 PathProgramCache]: Analyzing trace with hash -443608101, now seen corresponding path program 3 times [2024-11-09 16:05:35,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:35,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [825788960] [2024-11-09 16:05:35,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:35,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:35,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,131 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-09 16:05:36,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,138 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:36,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,140 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:36,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,143 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-09 16:05:36,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,151 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 16:05:36,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,158 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 16:05:36,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,160 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 34 proven. 64 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-09 16:05:36,160 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:36,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [825788960] [2024-11-09 16:05:36,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [825788960] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:36,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1823094043] [2024-11-09 16:05:36,161 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 16:05:36,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:36,161 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:36,162 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:36,165 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-11-09 16:05:36,203 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-09 16:05:36,203 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:36,204 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:36,205 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:36,302 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 63 proven. 69 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-09 16:05:36,303 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:36,515 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 63 proven. 70 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2024-11-09 16:05:36,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1823094043] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:36,515 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:36,516 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 14] total 22 [2024-11-09 16:05:36,516 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248427341] [2024-11-09 16:05:36,516 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:36,707 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:36,708 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:36,708 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:36,708 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:36,708 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:36,708 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:36,708 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:36,708 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:36,708 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration5_Loop [2024-11-09 16:05:36,708 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:36,708 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:36,709 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,715 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,717 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,718 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:36,749 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:36,749 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:36,749 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:36,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:36,751 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:36,752 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-09 16:05:36,752 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:36,752 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:36,780 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:36,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:36,781 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:36,782 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:36,790 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-09 16:05:36,790 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:36,791 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:37,253 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:37,258 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-09 16:05:37,258 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:37,258 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:37,258 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:37,258 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:37,259 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:37,259 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,259 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:37,259 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:37,259 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration5_Loop [2024-11-09 16:05:37,259 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:37,259 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:37,260 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,264 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,265 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,271 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:37,308 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:37,308 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:37,308 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,310 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-09 16:05:37,311 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:37,321 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:37,321 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:37,321 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:37,321 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:37,321 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:37,322 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:37,322 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:37,323 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:37,334 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:37,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,335 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,336 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-11-09 16:05:37,336 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:37,346 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:37,346 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:37,346 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:37,346 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:37,346 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:37,348 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:37,348 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:37,349 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:37,359 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:37,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,359 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,360 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,361 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-09 16:05:37,363 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:37,373 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:37,373 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:37,373 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:37,373 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:37,373 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:37,376 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:37,380 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:37,382 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:37,386 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:37,386 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 16:05:37,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:37,387 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:37,388 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:37,389 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-09 16:05:37,389 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:37,389 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:37,389 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:37,389 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-09 16:05:37,399 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-09 16:05:37,400 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:37,407 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:37,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:37,443 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:37,444 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:37,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:37,677 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:37,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:37,771 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:37,771 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:37,772 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:37,846 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-11-09 16:05:37,846 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:37,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:37,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-09 16:05:37,847 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-09 16:05:37,847 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:37,847 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:37,855 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:37,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:37,889 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:37,890 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,039 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,040 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,135 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:38,136 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:38,136 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:38,215 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-11-09 16:05:38,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:38,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:38,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-09 16:05:38,217 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-09 16:05:38,217 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:38,217 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:38,226 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:38,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,255 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,256 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,365 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-11-09 16:05:38,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:38,425 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 16:05:38,426 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:38,528 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:38,528 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:38,528 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:38,750 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 408 states and 526 transitions. Complement of second has 132 states. [2024-11-09 16:05:38,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:38,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:38,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-09 16:05:38,753 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-09 16:05:38,753 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:38,753 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-09 16:05:38,754 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:38,754 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-09 16:05:38,755 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:38,755 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-09 16:05:38,760 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-09 16:05:38,764 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-09 16:05:38,764 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-09 16:05:38,764 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-09 16:05:38,765 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-09 16:05:38,765 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:38,765 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-09 16:05:38,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-09 16:05:38,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-09 16:05:38,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 115 states have (on average 1.1391304347826088) internal successors, (131), 122 states have internal predecessors, (131), 43 states have call successors, (48), 25 states have call predecessors, (48), 29 states have return successors, (67), 39 states have call predecessors, (67), 39 states have call successors, (67) [2024-11-09 16:05:38,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-09 16:05:38,782 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-09 16:05:38,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:38,783 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-09 16:05:38,783 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=376, Unknown=0, NotChecked=0, Total=462 [2024-11-09 16:05:38,783 INFO L87 Difference]: Start difference. First operand 187 states and 246 transitions. Second operand has 22 states, 19 states have (on average 2.263157894736842) internal successors, (43), 16 states have internal predecessors, (43), 13 states have call successors, (17), 7 states have call predecessors, (17), 3 states have return successors, (10), 5 states have call predecessors, (10), 9 states have call successors, (10) [2024-11-09 16:05:39,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:39,068 INFO L93 Difference]: Finished difference Result 136 states and 141 transitions. [2024-11-09 16:05:39,068 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 136 states and 141 transitions. [2024-11-09 16:05:39,069 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:39,069 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 136 states to 0 states and 0 transitions. [2024-11-09 16:05:39,069 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:05:39,069 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:05:39,069 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:05:39,069 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:05:39,070 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:39,070 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:39,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-09 16:05:39,070 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:39,070 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 16:05:39,071 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 16:05:39,071 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:39,071 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 16:05:39,076 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 04:05:39 BoogieIcfgContainer [2024-11-09 16:05:39,077 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 16:05:39,077 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 16:05:39,077 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 16:05:39,077 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 16:05:39,078 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:05:32" (3/4) ... [2024-11-09 16:05:39,079 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 16:05:39,080 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 16:05:39,081 INFO L158 Benchmark]: Toolchain (without parser) took 7108.51ms. Allocated memory was 157.3MB in the beginning and 222.3MB in the end (delta: 65.0MB). Free memory was 83.4MB in the beginning and 117.9MB in the end (delta: -34.5MB). Peak memory consumption was 30.7MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,081 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 157.3MB. Free memory is still 108.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:39,081 INFO L158 Benchmark]: CACSL2BoogieTranslator took 207.62ms. Allocated memory is still 157.3MB. Free memory was 83.2MB in the beginning and 71.5MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,081 INFO L158 Benchmark]: Boogie Procedure Inliner took 25.72ms. Allocated memory is still 157.3MB. Free memory was 71.3MB in the beginning and 70.1MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,081 INFO L158 Benchmark]: Boogie Preprocessor took 25.49ms. Allocated memory is still 157.3MB. Free memory was 70.1MB in the beginning and 68.5MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,081 INFO L158 Benchmark]: RCFGBuilder took 288.96ms. Allocated memory is still 157.3MB. Free memory was 68.5MB in the beginning and 125.3MB in the end (delta: -56.8MB). Peak memory consumption was 13.2MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,082 INFO L158 Benchmark]: BuchiAutomizer took 6550.98ms. Allocated memory was 157.3MB in the beginning and 222.3MB in the end (delta: 65.0MB). Free memory was 125.2MB in the beginning and 117.9MB in the end (delta: 7.3MB). Peak memory consumption was 72.0MB. Max. memory is 16.1GB. [2024-11-09 16:05:39,082 INFO L158 Benchmark]: Witness Printer took 3.12ms. Allocated memory is still 222.3MB. Free memory is still 117.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:39,083 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.11ms. Allocated memory is still 157.3MB. Free memory is still 108.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 207.62ms. Allocated memory is still 157.3MB. Free memory was 83.2MB in the beginning and 71.5MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 25.72ms. Allocated memory is still 157.3MB. Free memory was 71.3MB in the beginning and 70.1MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 25.49ms. Allocated memory is still 157.3MB. Free memory was 70.1MB in the beginning and 68.5MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 288.96ms. Allocated memory is still 157.3MB. Free memory was 68.5MB in the beginning and 125.3MB in the end (delta: -56.8MB). Peak memory consumption was 13.2MB. Max. memory is 16.1GB. * BuchiAutomizer took 6550.98ms. Allocated memory was 157.3MB in the beginning and 222.3MB in the end (delta: 65.0MB). Free memory was 125.2MB in the beginning and 117.9MB in the end (delta: 7.3MB). Peak memory consumption was 72.0MB. Max. memory is 16.1GB. * Witness Printer took 3.12ms. Allocated memory is still 222.3MB. Free memory is still 117.9MB. 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 7 terminating modules (4 trivial, 2 deterministic, 1 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function n and consists of 11 locations. 4 modules have a trivial ranking function, the largest among these consists of 22 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 6.4s and 6 iterations. TraceHistogramMax:6. Analysis of lassos took 3.6s. Construction of modules took 0.4s. Büchi inclusion checks took 2.1s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 94 StatesRemovedByMinimization, 4 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 1, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 243 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 228 mSDsluCounter, 381 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 253 mSDsCounter, 151 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 766 IncrementalHoareTripleChecker+Invalid, 917 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 151 mSolverCounterUnsat, 128 mSDtfsCounter, 766 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI1 SFLT1 conc0 concLT1 SILN0 SILU0 SILI1 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital17 mio100 ax100 hnf100 lsp81 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq180 hnf92 smp80 dnf100 smp100 tf111 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 23ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 6 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 3 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.7s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-09 16:05:39,108 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:39,312 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:39,512 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:39,713 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