./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version fca748b1 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-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 64bit --witnessprinter.graph.data.programhash 9c9c032ca120503dfa93615a57a0bb47775014248f579f3a3fd38a4985b2298b --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dd.update-z3-fca748b-m [2024-11-20 22:08:57,445 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-20 22:08:57,508 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-20 22:08:57,513 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-20 22:08:57,514 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-20 22:08:57,554 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-20 22:08:57,554 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-20 22:08:57,554 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-20 22:08:57,555 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-20 22:08:57,555 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-20 22:08:57,555 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-20 22:08:57,555 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-20 22:08:57,556 INFO L153 SettingsManager]: * Use SBE=true [2024-11-20 22:08:57,556 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-20 22:08:57,558 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-20 22:08:57,558 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-20 22:08:57,558 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-20 22:08:57,559 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-20 22:08:57,559 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-20 22:08:57,560 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-20 22:08:57,563 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-20 22:08:57,563 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-20 22:08:57,564 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-20 22:08:57,564 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-20 22:08:57,564 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-20 22:08:57,564 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-20 22:08:57,564 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-20 22:08:57,564 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-20 22:08:57,565 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-20 22:08:57,565 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-20 22:08:57,565 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-20 22:08:57,565 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-20 22:08:57,565 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-20 22:08:57,565 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-20 22:08:57,566 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-20 22:08:57,566 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-20 22:08:57,566 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 9c9c032ca120503dfa93615a57a0bb47775014248f579f3a3fd38a4985b2298b [2024-11-20 22:08:57,758 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-20 22:08:57,783 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-20 22:08:57,786 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-20 22:08:57,787 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-20 22:08:57,787 INFO L274 PluginConnector]: CDTParser initialized [2024-11-20 22:08:57,788 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-11-20 22:08:59,049 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-20 22:08:59,214 INFO L384 CDTParser]: Found 1 translation units. [2024-11-20 22:08:59,214 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-11-20 22:08:59,220 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ead8053be/500f7ed5d64d4ddab81f8ab7693a5618/FLAG7c16b50fe [2024-11-20 22:08:59,230 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ead8053be/500f7ed5d64d4ddab81f8ab7693a5618 [2024-11-20 22:08:59,233 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-20 22:08:59,234 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-20 22:08:59,234 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-20 22:08:59,235 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-20 22:08:59,239 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-20 22:08:59,240 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,240 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@288c46b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59, skipping insertion in model container [2024-11-20 22:08:59,241 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,259 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-20 22:08:59,372 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-20 22:08:59,382 INFO L200 MainTranslator]: Completed pre-run [2024-11-20 22:08:59,392 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-20 22:08:59,408 INFO L204 MainTranslator]: Completed translation [2024-11-20 22:08:59,408 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59 WrapperNode [2024-11-20 22:08:59,409 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-20 22:08:59,410 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-20 22:08:59,410 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-20 22:08:59,410 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-20 22:08:59,416 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,419 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,431 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-11-20 22:08:59,431 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-20 22:08:59,432 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-20 22:08:59,432 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-20 22:08:59,432 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-20 22:08:59,440 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,440 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,441 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,446 INFO L175 MemorySlicer]: No memory access in input program. [2024-11-20 22:08:59,446 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,446 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,447 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,449 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,449 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,450 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,454 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-20 22:08:59,455 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-20 22:08:59,456 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-20 22:08:59,456 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-20 22:08:59,456 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (1/1) ... [2024-11-20 22:08:59,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:08:59,477 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:08:59,492 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-20 22:08:59,494 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-20 22:08:59,545 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2024-11-20 22:08:59,545 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2024-11-20 22:08:59,546 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2024-11-20 22:08:59,546 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2024-11-20 22:08:59,546 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-20 22:08:59,546 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-20 22:08:59,588 INFO L238 CfgBuilder]: Building ICFG [2024-11-20 22:08:59,590 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-20 22:08:59,667 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-20 22:08:59,667 INFO L287 CfgBuilder]: Performing block encoding [2024-11-20 22:08:59,676 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-20 22:08:59,677 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-20 22:08:59,677 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:08:59 BoogieIcfgContainer [2024-11-20 22:08:59,677 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-20 22:08:59,678 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-20 22:08:59,678 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-20 22:08:59,682 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-20 22:08:59,683 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:08:59,683 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 20.11 10:08:59" (1/3) ... [2024-11-20 22:08:59,683 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@23b58686 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 20.11 10:08:59, skipping insertion in model container [2024-11-20 22:08:59,684 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:08:59,684 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.11 10:08:59" (2/3) ... [2024-11-20 22:08:59,684 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@23b58686 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 20.11 10:08:59, skipping insertion in model container [2024-11-20 22:08:59,684 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-20 22:08:59,684 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:08:59" (3/3) ... [2024-11-20 22:08:59,685 INFO L332 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2024-11-20 22:08:59,729 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-20 22:08:59,729 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-20 22:08:59,729 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-20 22:08:59,729 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-20 22:08:59,729 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-20 22:08:59,730 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-20 22:08:59,730 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-20 22:08:59,730 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-20 22:08:59,733 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 22 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 13 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-20 22:08:59,748 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:08:59,748 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:08:59,749 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:08:59,753 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:08:59,753 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:08:59,754 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-20 22:08:59,754 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 22 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 13 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-20 22:08:59,756 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:08:59,756 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:08:59,756 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:08:59,756 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:08:59,756 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:08:59,762 INFO L745 eck$LassoCheckResult]: Stem: 21#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true; 14#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 10#L25true call main_#t~ret6#1 := rec2(main_~x~0#1);< 7#$Ultimate##0true [2024-11-20 22:08:59,763 INFO L747 eck$LassoCheckResult]: Loop: 7#$Ultimate##0true ~j := #in~j; 17#L18true assume !(~j <= 0); 20#L20true call #t~ret3 := rec1(~j);< 4#$Ultimate##0true ~i := #in~i; 18#L12true assume ~i <= 0;#res := 0; 15#rec1FINALtrue assume true; 16#rec1EXITtrue >#34#return; 3#L20-1true call #t~ret4 := rec2(#t~ret3 - 1);< 7#$Ultimate##0true [2024-11-20 22:08:59,767 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:08:59,767 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 1 times [2024-11-20 22:08:59,774 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:08:59,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1259974366] [2024-11-20 22:08:59,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:08:59,775 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:08:59,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:08:59,831 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:08:59,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:08:59,846 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:08:59,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:08:59,849 INFO L85 PathProgramCache]: Analyzing trace with hash -1074209557, now seen corresponding path program 1 times [2024-11-20 22:08:59,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:08:59,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [312951147] [2024-11-20 22:08:59,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:08:59,850 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:08:59,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:08:59,916 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-20 22:08:59,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:08:59,958 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-20 22:08:59,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:08:59,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [312951147] [2024-11-20 22:08:59,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [312951147] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:08:59,960 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-20 22:08:59,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-20 22:08:59,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1491180137] [2024-11-20 22:08:59,961 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:08:59,964 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-20 22:08:59,964 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:08:59,987 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-20 22:08:59,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-20 22:08:59,989 INFO L87 Difference]: Start difference. First operand has 22 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 13 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 5 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 4 states have internal predecessors, (5), 2 states have call successors, (2), 2 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-20 22:09:00,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:09:00,067 INFO L93 Difference]: Finished difference Result 26 states and 34 transitions. [2024-11-20 22:09:00,068 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 34 transitions. [2024-11-20 22:09:00,070 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:00,075 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 17 states and 23 transitions. [2024-11-20 22:09:00,077 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2024-11-20 22:09:00,077 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2024-11-20 22:09:00,078 INFO L73 IsDeterministic]: Start isDeterministic. Operand 17 states and 23 transitions. [2024-11-20 22:09:00,079 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-20 22:09:00,079 INFO L218 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-20 22:09:00,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states and 23 transitions. [2024-11-20 22:09:00,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-20 22:09:00,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 10 states have internal predecessors, (10), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-20 22:09:00,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2024-11-20 22:09:00,101 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-20 22:09:00,103 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-20 22:09:00,105 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-20 22:09:00,106 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-20 22:09:00,106 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 23 transitions. [2024-11-20 22:09:00,106 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:00,107 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:09:00,107 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:09:00,107 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-20 22:09:00,108 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:00,108 INFO L745 eck$LassoCheckResult]: Stem: 78#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 75#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 64#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 65#$Ultimate##0 [2024-11-20 22:09:00,108 INFO L747 eck$LassoCheckResult]: Loop: 65#$Ultimate##0 ~j := #in~j; 72#L18 assume !(~j <= 0); 70#L20 call #t~ret3 := rec1(~j);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume !(~i <= 0); 67#L14 call #t~ret0 := rec1(~i - 2);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume ~i <= 0;#res := 0; 76#rec1FINAL assume true; 77#rec1EXIT >#28#return; 68#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume ~i <= 0;#res := 0; 76#rec1FINAL assume true; 77#rec1EXIT >#30#return; 69#L14-2 call #t~ret2 := rec1(#t~ret1);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume ~i <= 0;#res := 0; 76#rec1FINAL assume true; 77#rec1EXIT >#32#return; 73#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 74#rec1FINAL assume true; 79#rec1EXIT >#34#return; 63#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 65#$Ultimate##0 [2024-11-20 22:09:00,109 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:00,109 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 2 times [2024-11-20 22:09:00,109 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:00,109 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1789682670] [2024-11-20 22:09:00,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:00,109 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:00,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:00,112 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:00,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:00,115 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:00,115 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:00,115 INFO L85 PathProgramCache]: Analyzing trace with hash -204878921, now seen corresponding path program 1 times [2024-11-20 22:09:00,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:00,116 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1079003232] [2024-11-20 22:09:00,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:00,116 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:00,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:00,129 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:00,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:00,141 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:00,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:00,142 INFO L85 PathProgramCache]: Analyzing trace with hash -482494696, now seen corresponding path program 1 times [2024-11-20 22:09:00,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:00,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [176632680] [2024-11-20 22:09:00,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:00,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:00,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:00,157 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:00,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:00,167 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:00,528 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:00,529 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:00,529 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:00,529 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:00,529 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:09:00,529 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,529 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:00,529 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:00,529 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-11-20 22:09:00,529 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:00,529 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:00,545 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,552 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,555 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,558 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,567 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,596 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:00,598 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:09:00,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,602 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,606 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-20 22:09:00,607 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-20 22:09:00,611 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:00,611 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:00,631 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:00,631 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:00,649 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:00,650 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,650 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,651 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-20 22:09:00,652 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-20 22:09:00,655 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:00,655 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:00,667 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:00,667 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:00,673 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:00,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,678 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-20 22:09:00,680 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-20 22:09:00,680 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:00,680 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:00,706 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:00,706 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#t~ret4=0} Honda state: {rec2_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:00,716 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-20 22:09:00,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,717 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-20 22:09:00,719 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-20 22:09:00,721 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:00,721 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:00,749 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:00,749 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,751 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-20 22:09:00,752 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-20 22:09:00,752 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:09:00,752 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:00,773 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:09:00,783 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-20 22:09:00,786 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:00,787 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:00,787 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:00,787 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:00,787 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:09:00,787 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,787 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:00,787 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:00,792 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-11-20 22:09:00,792 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:00,792 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:00,793 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,795 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,801 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,804 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,815 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:00,847 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:00,855 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:09:00,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,858 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-20 22:09:00,859 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-20 22:09:00,860 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-20 22:09:00,871 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:00,871 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:00,872 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:00,872 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:00,872 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:00,873 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:00,873 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:00,875 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:00,882 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-20 22:09:00,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,884 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-20 22:09:00,886 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-20 22:09:00,887 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-20 22:09:00,897 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:00,898 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:00,898 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:00,898 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:00,898 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:00,898 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:00,899 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:00,900 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:00,906 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-20 22:09:00,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,909 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-20 22:09:00,910 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-20 22:09:00,910 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-20 22:09:00,920 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:00,921 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:00,921 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:00,921 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:00,921 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:00,921 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:00,921 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:00,922 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:00,929 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-20 22:09:00,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,932 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-20 22:09:00,933 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-20 22:09:00,933 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-20 22:09:00,943 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:00,944 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:00,944 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:00,944 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:00,944 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:00,945 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:00,945 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:00,947 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:09:00,950 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-20 22:09:00,950 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-20 22:09:00,952 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:00,952 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:00,954 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-20 22:09:00,955 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-20 22:09:00,956 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:09:00,956 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:09:00,956 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:09:00,957 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2024-11-20 22:09:00,965 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-20 22:09:00,968 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:09:01,004 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:01,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:01,031 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-20 22:09:01,032 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:01,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:01,081 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-20 22:09:01,083 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:01,236 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-20 22:09:01,239 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 8 loop predicates [2024-11-20 22:09:01,241 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 17 states and 23 transitions. cyclomatic complexity: 8 Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:01,494 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 17 states and 23 transitions. cyclomatic complexity: 8. Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Result 102 states and 148 transitions. Complement of second has 42 states. [2024-11-20 22:09:01,497 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 1 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-20 22:09:01,497 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:01,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 37 transitions. [2024-11-20 22:09:01,500 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 24 letters. [2024-11-20 22:09:01,501 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:01,501 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 27 letters. Loop has 24 letters. [2024-11-20 22:09:01,501 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:01,501 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 48 letters. [2024-11-20 22:09:01,502 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:01,502 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 102 states and 148 transitions. [2024-11-20 22:09:01,506 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:01,509 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 102 states to 90 states and 136 transitions. [2024-11-20 22:09:01,509 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 39 [2024-11-20 22:09:01,509 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-11-20 22:09:01,509 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 136 transitions. [2024-11-20 22:09:01,510 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:01,510 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 136 transitions. [2024-11-20 22:09:01,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 136 transitions. [2024-11-20 22:09:01,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 63. [2024-11-20 22:09:01,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 34 states have (on average 1.1176470588235294) internal successors, (38), 36 states have internal predecessors, (38), 20 states have call successors, (20), 8 states have call predecessors, (20), 9 states have return successors, (41), 18 states have call predecessors, (41), 16 states have call successors, (41) [2024-11-20 22:09:01,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 99 transitions. [2024-11-20 22:09:01,535 INFO L240 hiAutomatonCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-11-20 22:09:01,535 INFO L425 stractBuchiCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-11-20 22:09:01,535 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-20 22:09:01,535 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 63 states and 99 transitions. [2024-11-20 22:09:01,544 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:01,544 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:09:01,544 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:09:01,545 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:01,545 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-20 22:09:01,545 INFO L745 eck$LassoCheckResult]: Stem: 384#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 376#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 344#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 353#$Ultimate##0 ~j := #in~j; 355#L18 assume !(~j <= 0); 348#L20 call #t~ret3 := rec1(~j);< 347#$Ultimate##0 ~i := #in~i; 349#L12 assume !(~i <= 0); 360#L14 call #t~ret0 := rec1(~i - 2);< 374#$Ultimate##0 [2024-11-20 22:09:01,545 INFO L747 eck$LassoCheckResult]: Loop: 374#$Ultimate##0 ~i := #in~i; 393#L12 assume !(~i <= 0); 357#L14 call #t~ret0 := rec1(~i - 2);< 374#$Ultimate##0 [2024-11-20 22:09:01,545 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:01,545 INFO L85 PathProgramCache]: Analyzing trace with hash 838970620, now seen corresponding path program 1 times [2024-11-20 22:09:01,545 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:01,545 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [687826835] [2024-11-20 22:09:01,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:01,548 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-20 22:09:01,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:01,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:01,555 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:01,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:01,561 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:01,561 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:01,561 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2024-11-20 22:09:01,561 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:01,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2064844113] [2024-11-20 22:09:01,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:01,561 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:01,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:01,563 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:01,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:01,568 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:01,568 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:01,568 INFO L85 PathProgramCache]: Analyzing trace with hash 1359045147, now seen corresponding path program 2 times [2024-11-20 22:09:01,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:01,568 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2092141699] [2024-11-20 22:09:01,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:01,569 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:01,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:01,575 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:01,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:01,580 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:01,612 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:01,612 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:01,612 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:01,612 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:01,612 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:09:01,612 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,612 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:01,612 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:01,612 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-11-20 22:09:01,612 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:01,612 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:01,613 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,619 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,620 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,621 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,623 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,627 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,659 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:01,659 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:09:01,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,661 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:01,667 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-11-20 22:09:01,667 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:01,667 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:01,679 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:01,679 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:01,685 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-20 22:09:01,685 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,685 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,686 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-20 22:09:01,687 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-20 22:09:01,689 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:01,689 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:01,700 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:01,700 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:01,706 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-20 22:09:01,706 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,708 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-20 22:09:01,709 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-20 22:09:01,710 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:01,710 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:01,721 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:01,721 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:01,727 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-20 22:09:01,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,729 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-20 22:09:01,730 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-20 22:09:01,731 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:01,731 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:01,741 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:01,742 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:01,748 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-20 22:09:01,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,750 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-20 22:09:01,751 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-20 22:09:01,752 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:01,752 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:01,770 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-20 22:09:01,770 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,772 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-20 22:09:01,775 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-20 22:09:01,776 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:09:01,776 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:01,816 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:09:01,821 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-20 22:09:01,821 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:01,821 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:01,821 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:01,821 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:01,821 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:09:01,821 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,821 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:01,821 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:01,821 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-11-20 22:09:01,821 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:01,821 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:01,822 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,827 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,829 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,831 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,833 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,838 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:01,870 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:01,871 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:09:01,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,873 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-20 22:09:01,874 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-20 22:09:01,875 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-20 22:09:01,885 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:01,885 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:01,885 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:01,885 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:01,885 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:01,885 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:01,885 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:01,886 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:01,892 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-20 22:09:01,893 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,894 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-20 22:09:01,895 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-20 22:09:01,897 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-20 22:09:01,906 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:01,906 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:01,906 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:01,907 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:01,907 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:01,907 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:01,907 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:01,908 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:01,914 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:01,915 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,915 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,916 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-20 22:09:01,917 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-20 22:09:01,918 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-20 22:09:01,928 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:01,928 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:01,928 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:01,928 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:01,928 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:01,929 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:01,929 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:01,931 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:01,937 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-20 22:09:01,937 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,937 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,939 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-20 22:09:01,940 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-20 22:09:01,940 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-20 22:09:01,950 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:01,950 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:01,950 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:01,950 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:01,950 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:01,951 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:01,951 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:01,952 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:01,958 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-20 22:09:01,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,960 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-20 22:09:01,961 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-20 22:09:01,962 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-20 22:09:01,975 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:01,976 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:01,976 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:01,976 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:01,976 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:01,978 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:01,978 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:01,982 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:09:01,984 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:09:01,984 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:09:01,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:01,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:01,989 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-20 22:09:01,990 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-20 22:09:01,991 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:09:01,991 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:09:01,991 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:09:01,991 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-20 22:09:01,997 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-20 22:09:01,998 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:09:02,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:02,045 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-20 22:09:02,046 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:02,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:02,089 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:02,089 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:02,123 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-20 22:09:02,124 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-20 22:09:02,124 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 63 states and 99 transitions. cyclomatic complexity: 40 Second operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-20 22:09:02,187 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 63 states and 99 transitions. cyclomatic complexity: 40. Second operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 109 states and 166 transitions. Complement of second has 17 states. [2024-11-20 22:09:02,192 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-20 22:09:02,193 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-20 22:09:02,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2024-11-20 22:09:02,198 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 3 letters. [2024-11-20 22:09:02,198 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:02,198 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 12 letters. Loop has 3 letters. [2024-11-20 22:09:02,198 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:02,198 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 6 letters. [2024-11-20 22:09:02,198 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:02,198 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 109 states and 166 transitions. [2024-11-20 22:09:02,203 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:02,205 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 109 states to 97 states and 154 transitions. [2024-11-20 22:09:02,211 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2024-11-20 22:09:02,212 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-20 22:09:02,212 INFO L73 IsDeterministic]: Start isDeterministic. Operand 97 states and 154 transitions. [2024-11-20 22:09:02,212 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:02,212 INFO L218 hiAutomatonCegarLoop]: Abstraction has 97 states and 154 transitions. [2024-11-20 22:09:02,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states and 154 transitions. [2024-11-20 22:09:02,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 93. [2024-11-20 22:09:02,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 54 states have (on average 1.1481481481481481) internal successors, (62), 60 states have internal predecessors, (62), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (56), 18 states have call predecessors, (56), 22 states have call successors, (56) [2024-11-20 22:09:02,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 144 transitions. [2024-11-20 22:09:02,236 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-11-20 22:09:02,236 INFO L425 stractBuchiCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-11-20 22:09:02,236 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-20 22:09:02,236 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 93 states and 144 transitions. [2024-11-20 22:09:02,238 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:02,238 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:09:02,238 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:09:02,241 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:02,242 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-20 22:09:02,242 INFO L745 eck$LassoCheckResult]: Stem: 636#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 626#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 587#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 605#$Ultimate##0 ~j := #in~j; 607#L18 assume !(~j <= 0); 631#L20 call #t~ret3 := rec1(~j);< 635#$Ultimate##0 ~i := #in~i; 653#L12 assume !(~i <= 0); 610#L14 call #t~ret0 := rec1(~i - 2);< 651#$Ultimate##0 ~i := #in~i; 656#L12 assume ~i <= 0;#res := 0; 655#rec1FINAL assume true; 650#rec1EXIT >#28#return; 593#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 592#$Ultimate##0 [2024-11-20 22:09:02,242 INFO L747 eck$LassoCheckResult]: Loop: 592#$Ultimate##0 ~i := #in~i; 600#L12 assume !(~i <= 0); 596#L14 call #t~ret0 := rec1(~i - 2);< 592#$Ultimate##0 [2024-11-20 22:09:02,242 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,243 INFO L85 PathProgramCache]: Analyzing trace with hash 372282091, now seen corresponding path program 1 times [2024-11-20 22:09:02,243 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:02,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2051826616] [2024-11-20 22:09:02,246 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:02,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:02,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:02,254 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:02,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:02,266 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:02,272 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,273 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2024-11-20 22:09:02,273 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:02,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [885394398] [2024-11-20 22:09:02,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:02,273 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:02,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:02,277 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:02,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:02,284 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:02,286 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,286 INFO L85 PathProgramCache]: Analyzing trace with hash 1050214860, now seen corresponding path program 2 times [2024-11-20 22:09:02,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:02,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1924148816] [2024-11-20 22:09:02,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:02,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:02,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:02,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-20 22:09:02,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:02,414 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-20 22:09:02,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:09:02,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1924148816] [2024-11-20 22:09:02,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1924148816] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:09:02,415 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-20 22:09:02,415 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-20 22:09:02,415 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [282737787] [2024-11-20 22:09:02,415 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:09:02,462 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:02,462 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:02,462 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:02,462 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:02,462 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:09:02,462 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,462 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:02,462 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:02,462 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-11-20 22:09:02,462 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:02,462 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:02,463 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,470 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,474 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,480 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,482 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,484 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,516 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:02,521 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:09:02,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:02,523 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:02,524 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-20 22:09:02,526 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:02,526 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:02,539 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:02,540 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:02,546 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:02,547 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,547 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:02,549 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:02,549 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-11-20 22:09:02,550 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:02,550 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:02,567 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:02,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:02,571 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-20 22:09:02,574 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-20 22:09:02,575 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:09:02,575 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:02,616 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:09:02,622 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-20 22:09:02,623 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:02,623 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:02,623 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:02,623 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:02,623 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:09:02,623 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,623 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:02,623 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:02,624 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-11-20 22:09:02,624 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:02,624 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:02,624 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,627 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,631 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,633 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,635 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,637 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:02,660 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:02,660 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:09:02,660 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,660 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:02,663 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-20 22:09:02,665 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-20 22:09:02,666 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-20 22:09:02,675 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:02,675 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:02,676 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:02,676 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:02,676 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:02,677 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:02,677 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:02,680 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:02,689 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-20 22:09:02,689 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:02,692 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-20 22:09:02,693 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-20 22:09:02,694 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-20 22:09:02,707 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:02,707 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:02,707 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:02,707 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:02,707 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:02,708 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:02,708 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:02,710 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:09:02,712 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:09:02,712 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:09:02,712 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:02,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:02,717 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-20 22:09:02,718 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-20 22:09:02,719 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:09:02,719 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:09:02,719 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:09:02,719 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-20 22:09:02,727 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-20 22:09:02,727 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:09:02,741 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:02,766 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-20 22:09:02,767 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:02,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:02,819 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:02,819 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:02,835 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-20 22:09:02,836 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:02,836 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 93 states and 144 transitions. cyclomatic complexity: 57 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-20 22:09:02,906 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 93 states and 144 transitions. cyclomatic complexity: 57. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 133 states and 208 transitions. Complement of second has 18 states. [2024-11-20 22:09:02,907 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-20 22:09:02,908 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-20 22:09:02,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-11-20 22:09:02,909 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 3 letters. [2024-11-20 22:09:02,909 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:02,909 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 17 letters. Loop has 3 letters. [2024-11-20 22:09:02,909 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:02,909 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 6 letters. [2024-11-20 22:09:02,909 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:02,909 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 133 states and 208 transitions. [2024-11-20 22:09:02,915 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:02,919 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 133 states to 121 states and 196 transitions. [2024-11-20 22:09:02,922 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2024-11-20 22:09:02,923 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 52 [2024-11-20 22:09:02,923 INFO L73 IsDeterministic]: Start isDeterministic. Operand 121 states and 196 transitions. [2024-11-20 22:09:02,923 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:02,923 INFO L218 hiAutomatonCegarLoop]: Abstraction has 121 states and 196 transitions. [2024-11-20 22:09:02,923 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states and 196 transitions. [2024-11-20 22:09:02,926 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2024-11-20 22:09:02,932 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2024-11-20 22:09:02,932 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 68 states have (on average 1.1764705882352942) internal successors, (80), 76 states have internal predecessors, (80), 32 states have call successors, (32), 18 states have call predecessors, (32), 17 states have return successors, (74), 22 states have call predecessors, (74), 28 states have call successors, (74) [2024-11-20 22:09:02,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 186 transitions. [2024-11-20 22:09:02,934 INFO L240 hiAutomatonCegarLoop]: Abstraction has 117 states and 186 transitions. [2024-11-20 22:09:02,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:09:02,934 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-20 22:09:02,934 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-20 22:09:02,935 INFO L87 Difference]: Start difference. First operand 117 states and 186 transitions. Second operand has 6 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-20 22:09:02,943 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-20 22:09:02,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:09:02,964 INFO L93 Difference]: Finished difference Result 130 states and 196 transitions. [2024-11-20 22:09:02,964 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 196 transitions. [2024-11-20 22:09:02,966 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-20 22:09:02,968 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 128 states and 194 transitions. [2024-11-20 22:09:02,969 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2024-11-20 22:09:02,969 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2024-11-20 22:09:02,969 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 194 transitions. [2024-11-20 22:09:02,969 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:02,969 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 194 transitions. [2024-11-20 22:09:02,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 194 transitions. [2024-11-20 22:09:02,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 105. [2024-11-20 22:09:02,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 60 states have (on average 1.1333333333333333) internal successors, (68), 66 states have internal predecessors, (68), 30 states have call successors, (30), 16 states have call predecessors, (30), 15 states have return successors, (60), 22 states have call predecessors, (60), 26 states have call successors, (60) [2024-11-20 22:09:02,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2024-11-20 22:09:02,978 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-11-20 22:09:02,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-20 22:09:02,979 INFO L425 stractBuchiCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-11-20 22:09:02,979 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-20 22:09:02,979 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 158 transitions. [2024-11-20 22:09:02,980 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-20 22:09:02,980 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:09:02,980 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:09:02,981 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:02,981 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:02,981 INFO L745 eck$LassoCheckResult]: Stem: 1218#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1207#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 1165#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1200#$Ultimate##0 ~j := #in~j; 1231#L18 assume !(~j <= 0); 1201#L20 call #t~ret3 := rec1(~j);< 1230#$Ultimate##0 ~i := #in~i; 1229#L12 assume !(~i <= 0); 1183#L14 call #t~ret0 := rec1(~i - 2);< 1227#$Ultimate##0 ~i := #in~i; 1226#L12 assume !(~i <= 0); 1187#L14 call #t~ret0 := rec1(~i - 2);< 1225#$Ultimate##0 ~i := #in~i; 1228#L12 assume ~i <= 0;#res := 0; 1208#rec1FINAL assume true; 1209#rec1EXIT >#28#return; 1171#L14-1 [2024-11-20 22:09:02,981 INFO L747 eck$LassoCheckResult]: Loop: 1171#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1169#$Ultimate##0 ~i := #in~i; 1172#L12 assume ~i <= 0;#res := 0; 1266#rec1FINAL assume true; 1254#rec1EXIT >#30#return; 1179#L14-2 call #t~ret2 := rec1(#t~ret1);< 1203#$Ultimate##0 ~i := #in~i; 1245#L12 assume !(~i <= 0); 1181#L14 call #t~ret0 := rec1(~i - 2);< 1203#$Ultimate##0 ~i := #in~i; 1245#L12 assume ~i <= 0;#res := 0; 1244#rec1FINAL assume true; 1243#rec1EXIT >#28#return; 1171#L14-1 [2024-11-20 22:09:02,981 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,982 INFO L85 PathProgramCache]: Analyzing trace with hash 1325197585, now seen corresponding path program 1 times [2024-11-20 22:09:02,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:02,982 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1342689929] [2024-11-20 22:09:02,982 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:02,982 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:02,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:02,987 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:02,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:02,991 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:02,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:02,991 INFO L85 PathProgramCache]: Analyzing trace with hash 949089090, now seen corresponding path program 1 times [2024-11-20 22:09:02,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:02,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1130862952] [2024-11-20 22:09:02,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:02,992 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:02,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,016 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-20 22:09:03,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,028 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-20 22:09:03,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,031 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-20 22:09:03,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:09:03,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1130862952] [2024-11-20 22:09:03,032 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1130862952] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:09:03,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1919624104] [2024-11-20 22:09:03,032 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:03,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:09:03,032 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,036 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,038 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Waiting until timeout for monitored process [2024-11-20 22:09:03,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,059 INFO L255 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-20 22:09:03,060 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:03,069 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-20 22:09:03,069 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-20 22:09:03,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1919624104] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-20 22:09:03,069 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-20 22:09:03,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-20 22:09:03,070 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [655714662] [2024-11-20 22:09:03,070 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-20 22:09:03,070 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-20 22:09:03,070 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:09:03,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-20 22:09:03,071 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-20 22:09:03,071 INFO L87 Difference]: Start difference. First operand 105 states and 158 transitions. cyclomatic complexity: 59 Second operand has 6 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-20 22:09:03,096 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:09:03,096 INFO L93 Difference]: Finished difference Result 120 states and 174 transitions. [2024-11-20 22:09:03,097 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 120 states and 174 transitions. [2024-11-20 22:09:03,098 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:03,100 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 120 states to 115 states and 165 transitions. [2024-11-20 22:09:03,100 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2024-11-20 22:09:03,100 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2024-11-20 22:09:03,101 INFO L73 IsDeterministic]: Start isDeterministic. Operand 115 states and 165 transitions. [2024-11-20 22:09:03,101 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:03,101 INFO L218 hiAutomatonCegarLoop]: Abstraction has 115 states and 165 transitions. [2024-11-20 22:09:03,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states and 165 transitions. [2024-11-20 22:09:03,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 112. [2024-11-20 22:09:03,107 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 64 states have (on average 1.109375) internal successors, (71), 69 states have internal predecessors, (71), 32 states have call successors, (32), 18 states have call predecessors, (32), 16 states have return successors, (59), 24 states have call predecessors, (59), 28 states have call successors, (59) [2024-11-20 22:09:03,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 162 transitions. [2024-11-20 22:09:03,108 INFO L240 hiAutomatonCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-11-20 22:09:03,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-20 22:09:03,109 INFO L425 stractBuchiCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-11-20 22:09:03,109 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-20 22:09:03,109 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 112 states and 162 transitions. [2024-11-20 22:09:03,110 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-20 22:09:03,110 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:09:03,110 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:09:03,111 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:03,111 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-20 22:09:03,111 INFO L745 eck$LassoCheckResult]: Stem: 1505#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1491#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 1447#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1475#$Ultimate##0 ~j := #in~j; 1516#L18 assume !(~j <= 0); 1461#L20 call #t~ret3 := rec1(~j);< 1515#$Ultimate##0 ~i := #in~i; 1514#L12 assume !(~i <= 0); 1478#L14 call #t~ret0 := rec1(~i - 2);< 1513#$Ultimate##0 ~i := #in~i; 1511#L12 assume !(~i <= 0); 1484#L14 call #t~ret0 := rec1(~i - 2);< 1510#$Ultimate##0 ~i := #in~i; 1512#L12 assume ~i <= 0;#res := 0; 1492#rec1FINAL assume true; 1493#rec1EXIT >#28#return; 1487#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1488#$Ultimate##0 ~i := #in~i; 1524#L12 assume ~i <= 0;#res := 0; 1523#rec1FINAL assume true; 1521#rec1EXIT >#30#return; 1452#L14-2 call #t~ret2 := rec1(#t~ret1);< 1451#$Ultimate##0 ~i := #in~i; 1453#L12 assume ~i <= 0;#res := 0; 1500#rec1FINAL assume true; 1496#rec1EXIT >#32#return; 1497#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 1526#rec1FINAL assume true; 1525#rec1EXIT >#28#return; 1480#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1502#$Ultimate##0 [2024-11-20 22:09:03,111 INFO L747 eck$LassoCheckResult]: Loop: 1502#$Ultimate##0 ~i := #in~i; 1528#L12 assume !(~i <= 0); 1481#L14 call #t~ret0 := rec1(~i - 2);< 1502#$Ultimate##0 [2024-11-20 22:09:03,111 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:03,111 INFO L85 PathProgramCache]: Analyzing trace with hash 1060897207, now seen corresponding path program 1 times [2024-11-20 22:09:03,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:03,112 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1241908179] [2024-11-20 22:09:03,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:03,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:03,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:03,118 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:03,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:03,126 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:03,126 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:03,126 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 3 times [2024-11-20 22:09:03,127 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:03,127 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [859915900] [2024-11-20 22:09:03,127 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:03,127 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:03,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:03,132 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:03,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:03,133 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:03,134 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:03,134 INFO L85 PathProgramCache]: Analyzing trace with hash -1475637376, now seen corresponding path program 2 times [2024-11-20 22:09:03,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:03,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1096839960] [2024-11-20 22:09:03,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:03,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:03,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,173 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-20 22:09:03,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,199 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-20 22:09:03,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,201 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-20 22:09:03,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,203 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-20 22:09:03,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,214 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-20 22:09:03,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:09:03,215 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1096839960] [2024-11-20 22:09:03,215 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1096839960] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:09:03,215 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1560001723] [2024-11-20 22:09:03,215 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-20 22:09:03,215 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:09:03,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,217 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,218 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Waiting until timeout for monitored process [2024-11-20 22:09:03,243 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-20 22:09:03,243 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-20 22:09:03,244 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:03,245 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:03,258 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-20 22:09:03,258 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:09:03,329 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-20 22:09:03,329 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1560001723] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:09:03,329 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:09:03,329 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-11-20 22:09:03,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1776149709] [2024-11-20 22:09:03,330 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:09:03,348 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:03,349 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:03,349 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:03,349 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:03,349 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:09:03,349 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,349 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:03,349 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:03,349 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-11-20 22:09:03,349 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:03,349 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:03,350 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,351 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,353 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,354 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,356 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,358 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,378 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:03,378 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:09:03,378 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,382 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,386 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-20 22:09:03,387 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:03,387 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,400 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:03,400 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:03,408 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-11-20 22:09:03,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,411 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-20 22:09:03,413 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:03,413 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,425 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:03,425 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:03,434 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,434 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,434 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,435 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,436 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-20 22:09:03,437 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:03,437 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,448 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:03,449 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret2=0} Honda state: {rec1_#t~ret2=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:03,456 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,456 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,456 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,460 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,461 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-20 22:09:03,463 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:03,463 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,474 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:03,474 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:03,480 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,482 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-20 22:09:03,484 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:03,484 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,494 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:03,494 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:03,500 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,502 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,503 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-20 22:09:03,503 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:03,503 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,520 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,523 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,525 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-20 22:09:03,525 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:09:03,525 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:03,565 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:09:03,570 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,570 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:03,570 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:03,570 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:03,570 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:03,570 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:09:03,570 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,570 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:03,570 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:03,570 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-11-20 22:09:03,570 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:03,570 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:03,571 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,574 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,575 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,576 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,578 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,579 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:03,600 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:03,600 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:09:03,601 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,602 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,609 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-20 22:09:03,609 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-20 22:09:03,619 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:03,619 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:03,619 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:03,619 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:03,619 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:03,620 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:03,620 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:03,621 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:03,630 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Ended with exit code 0 [2024-11-20 22:09:03,631 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,631 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,633 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,635 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-11-20 22:09:03,636 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-20 22:09:03,646 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:03,646 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:03,646 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:03,646 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:03,646 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:03,647 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:03,647 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:03,649 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:03,654 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,657 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,657 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-20 22:09:03,658 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-20 22:09:03,668 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:03,668 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:03,668 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:03,668 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:03,668 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:03,669 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:03,669 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:03,670 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:03,679 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-11-20 22:09:03,683 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,687 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,692 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-20 22:09:03,693 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-20 22:09:03,702 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:03,703 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:03,703 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:03,703 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:03,703 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:03,703 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:03,703 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:03,704 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:03,711 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,712 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,714 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,716 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2024-11-20 22:09:03,717 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-20 22:09:03,729 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:03,729 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:03,729 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:03,729 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:03,729 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:03,729 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:03,730 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:03,731 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-20 22:09:03,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,737 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,739 INFO L229 MonitoredProcess]: Starting monitored process 44 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,742 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2024-11-20 22:09:03,744 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-20 22:09:03,757 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:03,757 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:03,757 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:03,758 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:03,758 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:03,759 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:03,759 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:03,760 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:09:03,762 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:09:03,762 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:09:03,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:03,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:03,764 INFO L229 MonitoredProcess]: Starting monitored process 45 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:03,765 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2024-11-20 22:09:03,766 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:09:03,766 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:09:03,766 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:09:03,766 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-20 22:09:03,772 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:03,773 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:09:03,788 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:03,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:03,826 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-20 22:09:03,828 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,038 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:04,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,040 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:04,041 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,058 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-20 22:09:04,059 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:04,059 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:04,108 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 129 states and 180 transitions. Complement of second has 9 states. [2024-11-20 22:09:04,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2024-11-20 22:09:04,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:04,109 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-20 22:09:04,109 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-20 22:09:04,109 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:04,110 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:09:04,125 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:04,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,161 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-20 22:09:04,162 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,329 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:04,330 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,346 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-20 22:09:04,347 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:04,347 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:04,389 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 129 states and 180 transitions. Complement of second has 9 states. [2024-11-20 22:09:04,389 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2024-11-20 22:09:04,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:04,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-20 22:09:04,390 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-20 22:09:04,390 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:04,390 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:09:04,397 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:04,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,432 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-20 22:09:04,433 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,598 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:04,599 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,616 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-20 22:09:04,617 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:04,617 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:04,685 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 157 states and 219 transitions. Complement of second has 17 states. [2024-11-20 22:09:04,686 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-20 22:09:04,686 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:04,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-11-20 22:09:04,686 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-20 22:09:04,687 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:04,687 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-11-20 22:09:04,687 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:04,687 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-11-20 22:09:04,687 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:04,687 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 157 states and 219 transitions. [2024-11-20 22:09:04,689 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-20 22:09:04,690 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 157 states to 139 states and 201 transitions. [2024-11-20 22:09:04,691 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 55 [2024-11-20 22:09:04,691 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 58 [2024-11-20 22:09:04,691 INFO L73 IsDeterministic]: Start isDeterministic. Operand 139 states and 201 transitions. [2024-11-20 22:09:04,691 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:04,691 INFO L218 hiAutomatonCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-11-20 22:09:04,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states and 201 transitions. [2024-11-20 22:09:04,697 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 120. [2024-11-20 22:09:04,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 70 states have (on average 1.1285714285714286) internal successors, (79), 75 states have internal predecessors, (79), 32 states have call successors, (32), 20 states have call predecessors, (32), 18 states have return successors, (59), 24 states have call predecessors, (59), 28 states have call successors, (59) [2024-11-20 22:09:04,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 170 transitions. [2024-11-20 22:09:04,698 INFO L240 hiAutomatonCegarLoop]: Abstraction has 120 states and 170 transitions. [2024-11-20 22:09:04,698 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:09:04,698 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-20 22:09:04,699 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-20 22:09:04,699 INFO L87 Difference]: Start difference. First operand 120 states and 170 transitions. Second operand has 8 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-20 22:09:04,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:09:04,743 INFO L93 Difference]: Finished difference Result 98 states and 116 transitions. [2024-11-20 22:09:04,743 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 98 states and 116 transitions. [2024-11-20 22:09:04,744 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-20 22:09:04,745 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 98 states to 63 states and 75 transitions. [2024-11-20 22:09:04,745 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2024-11-20 22:09:04,745 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 12 [2024-11-20 22:09:04,745 INFO L73 IsDeterministic]: Start isDeterministic. Operand 63 states and 75 transitions. [2024-11-20 22:09:04,745 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-20 22:09:04,745 INFO L218 hiAutomatonCegarLoop]: Abstraction has 63 states and 75 transitions. [2024-11-20 22:09:04,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states and 75 transitions. [2024-11-20 22:09:04,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-11-20 22:09:04,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 33 states have (on average 1.121212121212121) internal successors, (37), 36 states have internal predecessors, (37), 14 states have call successors, (14), 10 states have call predecessors, (14), 7 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2024-11-20 22:09:04,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2024-11-20 22:09:04,748 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-20 22:09:04,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-20 22:09:04,755 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-20 22:09:04,755 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-20 22:09:04,755 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 65 transitions. [2024-11-20 22:09:04,755 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-20 22:09:04,755 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-20 22:09:04,755 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-20 22:09:04,756 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-20 22:09:04,756 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-20 22:09:04,756 INFO L745 eck$LassoCheckResult]: Stem: 2824#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 2818#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 2794#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 2803#$Ultimate##0 ~j := #in~j; 2804#L18 assume !(~j <= 0); 2816#L20 call #t~ret3 := rec1(~j);< 2842#$Ultimate##0 ~i := #in~i; 2839#L12 assume !(~i <= 0); 2811#L14 call #t~ret0 := rec1(~i - 2);< 2841#$Ultimate##0 ~i := #in~i; 2846#L12 assume ~i <= 0;#res := 0; 2845#rec1FINAL assume true; 2820#rec1EXIT >#28#return; 2815#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 2817#$Ultimate##0 ~i := #in~i; 2838#L12 assume ~i <= 0;#res := 0; 2837#rec1FINAL assume true; 2831#rec1EXIT >#30#return; 2829#L14-2 call #t~ret2 := rec1(#t~ret1);< 2814#$Ultimate##0 ~i := #in~i; 2833#L12 assume ~i <= 0;#res := 0; 2830#rec1FINAL assume true; 2828#rec1EXIT >#32#return; 2827#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 2826#rec1FINAL assume true; 2825#rec1EXIT >#34#return; 2793#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 2795#$Ultimate##0 ~j := #in~j; 2805#L18 assume !(~j <= 0); 2799#L20 call #t~ret3 := rec1(~j);< 2796#$Ultimate##0 [2024-11-20 22:09:04,756 INFO L747 eck$LassoCheckResult]: Loop: 2796#$Ultimate##0 ~i := #in~i; 2798#L12 assume !(~i <= 0); 2797#L14 call #t~ret0 := rec1(~i - 2);< 2796#$Ultimate##0 [2024-11-20 22:09:04,757 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:04,757 INFO L85 PathProgramCache]: Analyzing trace with hash 1256061253, now seen corresponding path program 2 times [2024-11-20 22:09:04,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:04,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051169215] [2024-11-20 22:09:04,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:04,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:04,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,790 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-20 22:09:04,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,809 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-20 22:09:04,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,812 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-20 22:09:04,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,813 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-20 22:09:04,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:04,825 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-20 22:09:04,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-20 22:09:04,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051169215] [2024-11-20 22:09:04,825 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1051169215] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-20 22:09:04,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [496406405] [2024-11-20 22:09:04,825 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-20 22:09:04,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-20 22:09:04,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:04,827 INFO L229 MonitoredProcess]: Starting monitored process 46 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-20 22:09:04,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Waiting until timeout for monitored process [2024-11-20 22:09:04,853 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-20 22:09:04,853 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-20 22:09:04,854 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:04,855 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:04,865 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-20 22:09:04,865 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-20 22:09:04,940 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-20 22:09:04,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [496406405] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-20 22:09:04,940 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-20 22:09:04,940 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-11-20 22:09:04,940 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [339037339] [2024-11-20 22:09:04,940 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-20 22:09:04,941 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-20 22:09:04,941 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:04,941 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 4 times [2024-11-20 22:09:04,941 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-20 22:09:04,941 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1306898918] [2024-11-20 22:09:04,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-20 22:09:04,941 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-20 22:09:04,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:04,943 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-20 22:09:04,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-20 22:09:04,945 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-20 22:09:04,985 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:04,985 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:04,986 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:04,986 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:04,986 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-20 22:09:04,986 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:04,986 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:04,986 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:04,986 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-11-20 22:09:04,986 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:04,986 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:04,987 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:04,989 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:04,992 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:04,994 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:04,995 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:04,998 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,019 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:05,020 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-20 22:09:05,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:05,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:05,022 INFO L229 MonitoredProcess]: Starting monitored process 47 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:05,023 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2024-11-20 22:09:05,024 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:05,024 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:05,036 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-20 22:09:05,036 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-20 22:09:05,045 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:05,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:05,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:05,047 INFO L229 MonitoredProcess]: Starting monitored process 48 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:05,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Waiting until timeout for monitored process [2024-11-20 22:09:05,050 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-20 22:09:05,051 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:05,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:05,067 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:05,067 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:05,068 INFO L229 MonitoredProcess]: Starting monitored process 49 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:05,073 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Waiting until timeout for monitored process [2024-11-20 22:09:05,073 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-20 22:09:05,074 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-20 22:09:05,115 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-20 22:09:05,119 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:05,119 INFO L204 LassoAnalysis]: Preferences: [2024-11-20 22:09:05,120 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-20 22:09:05,120 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-20 22:09:05,120 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-20 22:09:05,120 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-20 22:09:05,121 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:05,121 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-20 22:09:05,121 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-20 22:09:05,121 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-11-20 22:09:05,121 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-20 22:09:05,121 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-20 22:09:05,122 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,133 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,135 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,139 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,141 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-20 22:09:05,162 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-20 22:09:05,162 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-20 22:09:05,162 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:05,162 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:05,164 INFO L229 MonitoredProcess]: Starting monitored process 50 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:05,165 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Waiting until timeout for monitored process [2024-11-20 22:09:05,167 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-20 22:09:05,176 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-20 22:09:05,176 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-20 22:09:05,176 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-20 22:09:05,176 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-20 22:09:05,176 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-20 22:09:05,177 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-20 22:09:05,177 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-20 22:09:05,179 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-20 22:09:05,180 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-20 22:09:05,180 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-20 22:09:05,181 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-20 22:09:05,181 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-20 22:09:05,183 INFO L229 MonitoredProcess]: Starting monitored process 51 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-20 22:09:05,183 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Waiting until timeout for monitored process [2024-11-20 22:09:05,184 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-20 22:09:05,185 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-20 22:09:05,185 INFO L474 LassoAnalysis]: Proved termination. [2024-11-20 22:09:05,185 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-20 22:09:05,191 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:05,192 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-20 22:09:05,200 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:05,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:05,231 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-20 22:09:05,232 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:05,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:05,378 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:05,379 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:05,395 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-20 22:09:05,396 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:05,396 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:05,461 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 64 states and 76 transitions. Complement of second has 15 states. [2024-11-20 22:09:05,462 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-20 22:09:05,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:05,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-20 22:09:05,463 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-20 22:09:05,463 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:05,463 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:09:05,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:05,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:05,516 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-20 22:09:05,517 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:05,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:05,675 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:05,675 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:05,692 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-20 22:09:05,692 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:05,692 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:05,737 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 64 states and 76 transitions. Complement of second has 15 states. [2024-11-20 22:09:05,737 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-20 22:09:05,738 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:05,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-20 22:09:05,738 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-20 22:09:05,738 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:05,738 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-20 22:09:05,747 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-20 22:09:05,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:05,777 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-20 22:09:05,778 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:05,950 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Ended with exit code 0 [2024-11-20 22:09:05,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-20 22:09:05,953 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-20 22:09:05,955 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-20 22:09:05,970 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-20 22:09:05,970 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-20 22:09:05,971 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:06,029 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 78 states and 90 transitions. Complement of second has 15 states. [2024-11-20 22:09:06,029 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-20 22:09:06,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-20 22:09:06,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-11-20 22:09:06,030 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-20 22:09:06,030 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:06,030 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-11-20 22:09:06,030 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:06,030 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-11-20 22:09:06,031 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-20 22:09:06,031 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 78 states and 90 transitions. [2024-11-20 22:09:06,031 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:09:06,031 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 78 states to 0 states and 0 transitions. [2024-11-20 22:09:06,031 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-20 22:09:06,031 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-20 22:09:06,031 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-20 22:09:06,032 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-20 22:09:06,032 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-20 22:09:06,032 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-20 22:09:06,032 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 8 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-20 22:09:06,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-20 22:09:06,032 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:09:06,032 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-20 22:09:06,032 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-20 22:09:06,032 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-20 22:09:06,032 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:09:06,032 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:09:06,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-20 22:09:06,033 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-20 22:09:06,033 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-20 22:09:06,033 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-20 22:09:06,033 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-20 22:09:06,033 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-20 22:09:06,039 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 20.11 10:09:06 BoogieIcfgContainer [2024-11-20 22:09:06,039 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-20 22:09:06,040 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-20 22:09:06,040 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-20 22:09:06,040 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-20 22:09:06,040 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.11 10:08:59" (3/4) ... [2024-11-20 22:09:06,042 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-20 22:09:06,043 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-20 22:09:06,043 INFO L158 Benchmark]: Toolchain (without parser) took 6809.79ms. Allocated memory was 174.1MB in the beginning and 222.3MB in the end (delta: 48.2MB). Free memory was 143.5MB in the beginning and 178.7MB in the end (delta: -35.2MB). Peak memory consumption was 12.2MB. Max. memory is 16.1GB. [2024-11-20 22:09:06,044 INFO L158 Benchmark]: CDTParser took 0.49ms. Allocated memory is still 125.8MB. Free memory is still 90.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:09:06,044 INFO L158 Benchmark]: CACSL2BoogieTranslator took 174.42ms. Allocated memory is still 174.1MB. Free memory was 143.3MB in the beginning and 135.5MB in the end (delta: 7.8MB). Peak memory consumption was 10.7MB. Max. memory is 16.1GB. [2024-11-20 22:09:06,044 INFO L158 Benchmark]: Boogie Procedure Inliner took 21.63ms. Allocated memory is still 174.1MB. Free memory was 135.5MB in the beginning and 134.7MB in the end (delta: 736.3kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:09:06,044 INFO L158 Benchmark]: Boogie Preprocessor took 22.58ms. Allocated memory is still 174.1MB. Free memory was 134.7MB in the beginning and 133.4MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-20 22:09:06,044 INFO L158 Benchmark]: RCFGBuilder took 221.95ms. Allocated memory is still 174.1MB. Free memory was 132.7MB in the beginning and 122.2MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-20 22:09:06,045 INFO L158 Benchmark]: BuchiAutomizer took 6361.42ms. Allocated memory was 174.1MB in the beginning and 222.3MB in the end (delta: 48.2MB). Free memory was 122.2MB in the beginning and 178.7MB in the end (delta: -56.5MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:09:06,045 INFO L158 Benchmark]: Witness Printer took 3.17ms. Allocated memory is still 222.3MB. Free memory is still 178.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-20 22:09:06,046 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.49ms. Allocated memory is still 125.8MB. Free memory is still 90.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 174.42ms. Allocated memory is still 174.1MB. Free memory was 143.3MB in the beginning and 135.5MB in the end (delta: 7.8MB). Peak memory consumption was 10.7MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 21.63ms. Allocated memory is still 174.1MB. Free memory was 135.5MB in the beginning and 134.7MB in the end (delta: 736.3kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 22.58ms. Allocated memory is still 174.1MB. Free memory was 134.7MB in the beginning and 133.4MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 221.95ms. Allocated memory is still 174.1MB. Free memory was 132.7MB in the beginning and 122.2MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 6361.42ms. Allocated memory was 174.1MB in the beginning and 222.3MB in the end (delta: 48.2MB). Free memory was 122.2MB in the beginning and 178.7MB in the end (delta: -56.5MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.17ms. Allocated memory is still 222.3MB. Free memory is still 178.7MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(j) and consists of 10 locations. One deterministic module has affine ranking function \old(i) and consists of 5 locations. One deterministic module has affine ranking function \old(i) and consists of 6 locations. One nondeterministic module has affine ranking function \old(i) and consists of 6 locations. One nondeterministic module has affine ranking function \old(i) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 8 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 6.3s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 3.2s. Construction of modules took 0.3s. Büchi inclusion checks took 2.6s. Highest rank in rank-based complementation 3. Minimization of det autom 3. Minimization of nondet autom 7. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 89 StatesRemovedByMinimization, 7 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 [3, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 22/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 200 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 177 mSDsluCounter, 532 SdHoareTripleChecker+Invalid, 0.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 333 mSDsCounter, 131 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 323 IncrementalHoareTripleChecker+Invalid, 454 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 131 mSolverCounterUnsat, 199 mSDtfsCounter, 323 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI2 SFLT2 conc0 concLT2 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital11 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq147 hnf94 smp100 dnf100 smp100 tf112 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 19ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 14 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.5s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-20 22:09:06,058 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:06,258 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Forceful destruction successful, exit code 0 [2024-11-20 22:09:06,463 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Ended with exit code 0 [2024-11-20 22:09:06,663 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