./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/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.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/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.3.0-?-8fc3dc6-m [2025-03-17 19:50:27,211 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 19:50:27,263 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2025-03-17 19:50:27,267 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 19:50:27,267 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 19:50:27,269 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-17 19:50:27,289 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 19:50:27,290 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 19:50:27,290 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 19:50:27,290 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 19:50:27,291 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 19:50:27,291 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 19:50:27,291 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 19:50:27,291 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 19:50:27,291 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-17 19:50:27,292 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 19:50:27,292 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-17 19:50:27,293 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 19:50:27,293 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 19:50:27,293 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 19:50:27,293 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 19:50:27,293 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 19:50:27,293 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 19:50:27,293 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-17 19:50:27,293 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR 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 [2025-03-17 19:50:27,509 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 19:50:27,518 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 19:50:27,519 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 19:50:27,520 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 19:50:27,520 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 19:50:27,521 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2025-03-17 19:50:28,708 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ed9dcdbc/cb6ae0f07f7e4844810ac4c93da81a87/FLAGa8b851512 [2025-03-17 19:50:28,913 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 19:50:28,914 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2025-03-17 19:50:28,918 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ed9dcdbc/cb6ae0f07f7e4844810ac4c93da81a87/FLAGa8b851512 [2025-03-17 19:50:29,275 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ed9dcdbc/cb6ae0f07f7e4844810ac4c93da81a87 [2025-03-17 19:50:29,276 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 19:50:29,277 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 19:50:29,278 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 19:50:29,278 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 19:50:29,284 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 19:50:29,285 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,285 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@575fa61a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29, skipping insertion in model container [2025-03-17 19:50:29,285 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,294 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 19:50:29,386 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 19:50:29,389 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 19:50:29,395 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 19:50:29,406 INFO L204 MainTranslator]: Completed translation [2025-03-17 19:50:29,406 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29 WrapperNode [2025-03-17 19:50:29,407 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 19:50:29,407 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 19:50:29,407 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 19:50:29,408 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 19:50:29,412 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,414 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,423 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2025-03-17 19:50:29,424 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 19:50:29,424 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 19:50:29,424 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 19:50:29,424 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 19:50:29,429 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,429 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,430 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,433 INFO L175 MemorySlicer]: No memory access in input program. [2025-03-17 19:50:29,434 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,434 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,435 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,436 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,437 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,437 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,438 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 19:50:29,441 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 19:50:29,441 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 19:50:29,441 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 19:50:29,442 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (1/1) ... [2025-03-17 19:50:29,448 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:29,459 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:29,473 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) [2025-03-17 19:50:29,475 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 [2025-03-17 19:50:29,494 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2025-03-17 19:50:29,495 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2025-03-17 19:50:29,495 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2025-03-17 19:50:29,495 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2025-03-17 19:50:29,495 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 19:50:29,495 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 19:50:29,531 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 19:50:29,532 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 19:50:29,590 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L14: havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; [2025-03-17 19:50:29,608 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L20: havoc #t~ret3;havoc #t~ret4; [2025-03-17 19:50:29,643 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-03-17 19:50:29,643 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 19:50:29,652 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 19:50:29,652 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 19:50:29,653 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:50:29 BoogieIcfgContainer [2025-03-17 19:50:29,653 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 19:50:29,654 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-17 19:50:29,654 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-17 19:50:29,659 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-17 19:50:29,659 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 19:50:29,660 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.03 07:50:29" (1/3) ... [2025-03-17 19:50:29,661 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6fcbe6a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 07:50:29, skipping insertion in model container [2025-03-17 19:50:29,661 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 19:50:29,661 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:29" (2/3) ... [2025-03-17 19:50:29,661 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6fcbe6a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 07:50:29, skipping insertion in model container [2025-03-17 19:50:29,661 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 19:50:29,662 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:50:29" (3/3) ... [2025-03-17 19:50:29,663 INFO L363 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2025-03-17 19:50:29,696 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-17 19:50:29,696 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-17 19:50:29,696 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-17 19:50:29,696 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-17 19:50:29,696 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-17 19:50:29,697 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-17 19:50:29,697 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-17 19:50:29,697 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-17 19:50:29,700 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 20 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 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) [2025-03-17 19:50:29,711 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:29,712 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:29,712 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:29,716 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 19:50:29,716 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:29,716 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-17 19:50:29,716 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 20 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 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) [2025-03-17 19:50:29,718 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:29,718 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:29,718 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:29,718 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 19:50:29,718 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:29,722 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< [2025-03-17 19:50:29,723 INFO L754 eck$LassoCheckResult]: Loop: "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#30#return;" "call #t~ret4 := rec2(#t~ret3 - 1);"< [2025-03-17 19:50:29,726 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:29,726 INFO L85 PathProgramCache]: Analyzing trace with hash 1581, now seen corresponding path program 1 times [2025-03-17 19:50:29,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:29,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556857195] [2025-03-17 19:50:29,732 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:29,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:29,771 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:29,773 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:29,773 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:29,773 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:29,774 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:29,775 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:29,776 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:29,776 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:29,776 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:29,785 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:29,787 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:29,787 INFO L85 PathProgramCache]: Analyzing trace with hash -1058085942, now seen corresponding path program 1 times [2025-03-17 19:50:29,787 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:29,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [991795304] [2025-03-17 19:50:29,787 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:29,788 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:29,791 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:29,800 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:29,800 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:29,800 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:29,910 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:29,911 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:29,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [991795304] [2025-03-17 19:50:29,912 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [991795304] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 19:50:29,912 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 19:50:29,912 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-17 19:50:29,912 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644726067] [2025-03-17 19:50:29,913 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 19:50:29,914 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-17 19:50:29,915 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:29,929 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-17 19:50:29,930 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-17 19:50:29,931 INFO L87 Difference]: Start difference. First operand has 20 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 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) [2025-03-17 19:50:29,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:29,999 INFO L93 Difference]: Finished difference Result 24 states and 32 transitions. [2025-03-17 19:50:30,000 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 24 states and 32 transitions. [2025-03-17 19:50:30,001 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:30,006 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 24 states to 16 states and 22 transitions. [2025-03-17 19:50:30,007 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 16 [2025-03-17 19:50:30,008 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2025-03-17 19:50:30,008 INFO L73 IsDeterministic]: Start isDeterministic. Operand 16 states and 22 transitions. [2025-03-17 19:50:30,009 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 19:50:30,009 INFO L218 hiAutomatonCegarLoop]: Abstraction has 16 states and 22 transitions. [2025-03-17 19:50:30,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states and 22 transitions. [2025-03-17 19:50:30,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2025-03-17 19:50:30,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 8 states have (on average 1.125) internal successors, (9), 9 states have internal predecessors, (9), 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) [2025-03-17 19:50:30,028 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 22 transitions. [2025-03-17 19:50:30,029 INFO L240 hiAutomatonCegarLoop]: Abstraction has 16 states and 22 transitions. [2025-03-17 19:50:30,030 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-17 19:50:30,033 INFO L432 stractBuchiCegarLoop]: Abstraction has 16 states and 22 transitions. [2025-03-17 19:50:30,033 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-17 19:50:30,033 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 16 states and 22 transitions. [2025-03-17 19:50:30,033 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:30,033 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:30,033 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:30,037 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 19:50:30,038 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:30,038 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< [2025-03-17 19:50:30,038 INFO L754 eck$LassoCheckResult]: Loop: "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#26#return;" "call #t~ret1 := rec1(#t~ret0 - 1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#24#return;" "call #t~ret2 := rec1(#t~ret1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#22#return;" "#res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2;" "assume true;" >"#30#return;" "call #t~ret4 := rec2(#t~ret3 - 1);"< [2025-03-17 19:50:30,039 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:30,039 INFO L85 PathProgramCache]: Analyzing trace with hash 1581, now seen corresponding path program 2 times [2025-03-17 19:50:30,039 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:30,039 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1265573906] [2025-03-17 19:50:30,039 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:30,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:30,042 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:30,043 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:30,043 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-17 19:50:30,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:30,043 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:30,044 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:30,044 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:30,044 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,044 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:30,045 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:30,045 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:30,045 INFO L85 PathProgramCache]: Analyzing trace with hash 755780845, now seen corresponding path program 1 times [2025-03-17 19:50:30,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:30,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [572672249] [2025-03-17 19:50:30,045 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:30,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:30,050 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-17 19:50:30,059 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-17 19:50:30,059 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,059 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:30,059 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:30,061 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-17 19:50:30,066 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-17 19:50:30,066 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,066 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:30,069 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:30,070 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:30,070 INFO L85 PathProgramCache]: Analyzing trace with hash 120033049, now seen corresponding path program 1 times [2025-03-17 19:50:30,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:30,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1878474377] [2025-03-17 19:50:30,070 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:30,070 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:30,077 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-17 19:50:30,082 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-17 19:50:30,082 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,082 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:30,082 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:30,085 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-17 19:50:30,095 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-17 19:50:30,095 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,095 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:30,101 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:30,412 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:30,412 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:30,412 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:30,412 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:30,413 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:30,413 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,413 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:30,413 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:30,413 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2025-03-17 19:50:30,413 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:30,413 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:30,422 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,428 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,430 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,432 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,442 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,479 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:30,479 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:30,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,481 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,483 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) [2025-03-17 19:50:30,485 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 [2025-03-17 19:50:30,486 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:30,486 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:30,502 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:30,502 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#t~ret3=0} Honda state: {rec2_#t~ret3=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:30,509 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 [2025-03-17 19:50:30,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,511 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) [2025-03-17 19:50:30,515 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 [2025-03-17 19:50:30,516 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:30,516 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:30,532 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:30,533 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:30,539 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 [2025-03-17 19:50:30,540 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,540 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,542 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) [2025-03-17 19:50:30,542 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 [2025-03-17 19:50:30,544 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:30,544 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:30,555 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:30,555 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:30,560 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 [2025-03-17 19:50:30,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,562 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) [2025-03-17 19:50:30,563 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 [2025-03-17 19:50:30,564 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:30,564 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:30,581 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2025-03-17 19:50:30,581 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,582 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,583 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) [2025-03-17 19:50:30,584 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 [2025-03-17 19:50:30,585 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:30,585 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:30,597 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:30,604 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:30,604 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:30,604 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:30,604 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:30,604 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:30,604 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:30,604 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,604 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:30,604 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:30,604 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2025-03-17 19:50:30,604 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:30,604 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:30,605 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,608 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,610 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,612 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,621 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:30,647 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:30,650 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:30,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,651 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,653 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) [2025-03-17 19:50:30,654 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 [2025-03-17 19:50:30,656 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 [2025-03-17 19:50:30,669 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:30,669 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:30,670 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:30,670 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:30,670 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:30,675 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:30,676 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:30,679 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:30,685 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:30,685 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,685 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,687 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) [2025-03-17 19:50:30,688 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 [2025-03-17 19:50:30,690 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:30,699 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:30,699 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:30,700 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:30,700 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:30,700 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:30,700 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:30,700 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:30,701 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:30,706 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2025-03-17 19:50:30,707 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,709 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) [2025-03-17 19:50:30,709 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 [2025-03-17 19:50:30,711 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 [2025-03-17 19:50:30,721 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:30,721 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:30,721 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:30,721 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:30,721 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:30,721 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:30,721 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:30,733 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:30,739 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:30,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,741 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) [2025-03-17 19:50:30,741 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 [2025-03-17 19:50:30,742 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:30,752 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:30,752 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:30,752 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:30,752 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:30,752 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:30,753 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:30,753 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:30,755 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:30,759 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 19:50:30,764 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2025-03-17 19:50:30,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:30,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:30,771 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) [2025-03-17 19:50:30,772 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 [2025-03-17 19:50:30,773 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:30,773 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:30,773 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:30,773 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2025-03-17 19:50:30,782 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2025-03-17 19:50:30,784 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:30,806 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:30,814 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:30,820 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:30,820 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,820 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:30,821 INFO L256 TraceCheckSpWp]: Trace formula consists of 35 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-17 19:50:30,822 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:30,836 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-17 19:50:30,863 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-17 19:50:30,863 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:30,863 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:30,867 INFO L256 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-17 19:50:30,870 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:31,014 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-17 19:50:31,017 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 [2025-03-17 19:50:31,018 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 16 states and 22 transitions. cyclomatic complexity: 8 Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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) [2025-03-17 19:50:31,352 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 16 states and 22 transitions. cyclomatic complexity: 8. Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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 101 states and 147 transitions. Complement of second has 42 states. [2025-03-17 19:50:31,355 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 [2025-03-17 19:50:31,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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) [2025-03-17 19:50:31,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 36 transitions. [2025-03-17 19:50:31,359 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 36 transitions. Stem has 2 letters. Loop has 24 letters. [2025-03-17 19:50:31,361 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:31,361 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 36 transitions. Stem has 26 letters. Loop has 24 letters. [2025-03-17 19:50:31,361 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:31,361 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 36 transitions. Stem has 2 letters. Loop has 48 letters. [2025-03-17 19:50:31,362 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:31,362 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 101 states and 147 transitions. [2025-03-17 19:50:31,369 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:31,375 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 101 states to 89 states and 135 transitions. [2025-03-17 19:50:31,375 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 38 [2025-03-17 19:50:31,375 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 41 [2025-03-17 19:50:31,376 INFO L73 IsDeterministic]: Start isDeterministic. Operand 89 states and 135 transitions. [2025-03-17 19:50:31,377 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:31,377 INFO L218 hiAutomatonCegarLoop]: Abstraction has 89 states and 135 transitions. [2025-03-17 19:50:31,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states and 135 transitions. [2025-03-17 19:50:31,387 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 62. [2025-03-17 19:50:31,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 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) [2025-03-17 19:50:31,389 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 98 transitions. [2025-03-17 19:50:31,389 INFO L240 hiAutomatonCegarLoop]: Abstraction has 62 states and 98 transitions. [2025-03-17 19:50:31,389 INFO L432 stractBuchiCegarLoop]: Abstraction has 62 states and 98 transitions. [2025-03-17 19:50:31,389 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-17 19:50:31,389 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 62 states and 98 transitions. [2025-03-17 19:50:31,390 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:31,390 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:31,390 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:31,391 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:31,391 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:31,391 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< [2025-03-17 19:50:31,391 INFO L754 eck$LassoCheckResult]: Loop: "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< [2025-03-17 19:50:31,391 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,391 INFO L85 PathProgramCache]: Analyzing trace with hash -867748695, now seen corresponding path program 1 times [2025-03-17 19:50:31,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:31,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2037346674] [2025-03-17 19:50:31,391 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:31,391 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:31,394 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:31,395 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:31,395 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,395 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,395 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:31,396 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:31,397 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:31,397 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,397 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,398 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:31,398 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,398 INFO L85 PathProgramCache]: Analyzing trace with hash 36729, now seen corresponding path program 1 times [2025-03-17 19:50:31,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:31,398 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1850071291] [2025-03-17 19:50:31,399 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:31,399 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:31,400 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:31,401 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:31,401 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,401 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,401 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:31,401 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:31,402 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:31,402 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,402 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,402 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:31,403 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,403 INFO L85 PathProgramCache]: Analyzing trace with hash 306788817, now seen corresponding path program 2 times [2025-03-17 19:50:31,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:31,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [723806778] [2025-03-17 19:50:31,403 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:31,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:31,406 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 11 statements into 2 equivalence classes. [2025-03-17 19:50:31,411 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 11 of 11 statements. [2025-03-17 19:50:31,412 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:31,412 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,412 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:31,413 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-17 19:50:31,414 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-17 19:50:31,415 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,415 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,415 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:31,453 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:31,454 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:31,454 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:31,454 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:31,454 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:31,454 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,454 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:31,454 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:31,454 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2025-03-17 19:50:31,454 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:31,454 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:31,454 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,459 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,460 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,463 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,465 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,467 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,500 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:31,500 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:31,500 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,500 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,502 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) [2025-03-17 19:50:31,503 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 [2025-03-17 19:50:31,505 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:31,505 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,515 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:31,516 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:31,520 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:31,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,522 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) [2025-03-17 19:50:31,523 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 [2025-03-17 19:50:31,524 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:31,524 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,534 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:31,534 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:31,539 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:31,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,539 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,541 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) [2025-03-17 19:50:31,542 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 [2025-03-17 19:50:31,543 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:31,543 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,553 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:31,553 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:31,558 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 [2025-03-17 19:50:31,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,558 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,560 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) [2025-03-17 19:50:31,561 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 [2025-03-17 19:50:31,562 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:31,562 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,572 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:31,572 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:31,577 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:31,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,579 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) [2025-03-17 19:50:31,580 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 [2025-03-17 19:50:31,581 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:31,581 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,591 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:31,591 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret2=0} Honda state: {rec1_#t~ret2=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:31,596 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:31,596 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,598 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) [2025-03-17 19:50:31,599 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 [2025-03-17 19:50:31,599 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:31,599 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,615 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 [2025-03-17 19:50:31,616 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,617 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) [2025-03-17 19:50:31,618 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 [2025-03-17 19:50:31,619 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:31,619 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:31,658 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:31,662 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 [2025-03-17 19:50:31,662 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:31,662 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:31,662 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:31,662 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:31,662 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:31,662 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,662 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:31,662 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:31,662 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2025-03-17 19:50:31,662 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:31,662 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:31,663 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,669 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,672 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,676 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,679 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,683 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:31,707 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:31,708 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:31,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,710 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) [2025-03-17 19:50:31,711 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 [2025-03-17 19:50:31,712 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 [2025-03-17 19:50:31,722 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:31,722 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:31,722 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:31,722 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:31,722 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:31,723 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:31,723 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:31,724 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:31,730 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2025-03-17 19:50:31,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,732 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) [2025-03-17 19:50:31,733 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 [2025-03-17 19:50:31,734 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 [2025-03-17 19:50:31,743 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:31,744 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:31,744 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:31,744 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:31,744 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:31,744 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:31,744 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:31,745 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:31,751 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 [2025-03-17 19:50:31,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,755 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) [2025-03-17 19:50:31,756 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 [2025-03-17 19:50:31,757 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 [2025-03-17 19:50:31,767 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:31,767 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:31,767 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:31,767 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:31,767 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:31,767 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:31,767 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:31,769 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:31,774 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 [2025-03-17 19:50:31,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,774 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,776 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) [2025-03-17 19:50:31,776 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 [2025-03-17 19:50:31,780 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 [2025-03-17 19:50:31,790 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:31,790 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:31,790 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:31,790 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:31,790 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:31,790 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:31,790 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:31,791 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:31,796 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2025-03-17 19:50:31,797 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,798 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) [2025-03-17 19:50:31,799 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 [2025-03-17 19:50:31,800 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 [2025-03-17 19:50:31,809 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:31,809 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:31,809 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:31,809 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:31,809 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:31,810 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:31,810 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:31,812 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:31,814 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-17 19:50:31,814 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:31,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:31,814 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:31,816 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) [2025-03-17 19:50:31,817 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 [2025-03-17 19:50:31,817 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:31,817 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:31,817 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:31,817 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2025-03-17 19:50:31,822 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 [2025-03-17 19:50:31,823 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:31,836 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,845 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:31,856 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:31,856 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,856 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:31,857 INFO L256 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 19:50:31,857 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:31,873 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:31,876 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:31,876 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,876 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:31,876 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:31,876 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:31,903 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:31,903 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 [2025-03-17 19:50:31,903 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 62 states and 98 transitions. cyclomatic complexity: 40 Second operand has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 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) [2025-03-17 19:50:31,937 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 62 states and 98 transitions. cyclomatic complexity: 40. Second operand has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 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 108 states and 165 transitions. Complement of second has 17 states. [2025-03-17 19:50:31,937 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 [2025-03-17 19:50:31,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 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) [2025-03-17 19:50:31,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 13 transitions. [2025-03-17 19:50:31,938 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 13 transitions. Stem has 8 letters. Loop has 3 letters. [2025-03-17 19:50:31,938 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:31,938 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 13 transitions. Stem has 11 letters. Loop has 3 letters. [2025-03-17 19:50:31,938 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:31,938 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 13 transitions. Stem has 8 letters. Loop has 6 letters. [2025-03-17 19:50:31,938 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:31,938 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 108 states and 165 transitions. [2025-03-17 19:50:31,941 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:31,943 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 108 states to 96 states and 153 transitions. [2025-03-17 19:50:31,943 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 40 [2025-03-17 19:50:31,943 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2025-03-17 19:50:31,943 INFO L73 IsDeterministic]: Start isDeterministic. Operand 96 states and 153 transitions. [2025-03-17 19:50:31,944 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:31,944 INFO L218 hiAutomatonCegarLoop]: Abstraction has 96 states and 153 transitions. [2025-03-17 19:50:31,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states and 153 transitions. [2025-03-17 19:50:31,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 92. [2025-03-17 19:50:31,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 53 states have (on average 1.150943396226415) internal successors, (61), 59 states have internal predecessors, (61), 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) [2025-03-17 19:50:31,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 143 transitions. [2025-03-17 19:50:31,950 INFO L240 hiAutomatonCegarLoop]: Abstraction has 92 states and 143 transitions. [2025-03-17 19:50:31,950 INFO L432 stractBuchiCegarLoop]: Abstraction has 92 states and 143 transitions. [2025-03-17 19:50:31,950 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-17 19:50:31,950 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 92 states and 143 transitions. [2025-03-17 19:50:31,951 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:31,951 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:31,951 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:31,951 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:31,951 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:31,952 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#26#return;" "call #t~ret1 := rec1(#t~ret0 - 1);"< [2025-03-17 19:50:31,952 INFO L754 eck$LassoCheckResult]: Loop: "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< [2025-03-17 19:50:31,952 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,952 INFO L85 PathProgramCache]: Analyzing trace with hash -1528735586, now seen corresponding path program 1 times [2025-03-17 19:50:31,952 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:31,952 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1948949782] [2025-03-17 19:50:31,952 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:31,952 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:31,954 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-17 19:50:31,957 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-17 19:50:31,958 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,958 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,958 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:31,958 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-17 19:50:31,960 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-17 19:50:31,960 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,960 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,961 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:31,961 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,961 INFO L85 PathProgramCache]: Analyzing trace with hash 36729, now seen corresponding path program 2 times [2025-03-17 19:50:31,961 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:31,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [137737587] [2025-03-17 19:50:31,962 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:31,962 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:31,963 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:31,963 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:31,963 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-17 19:50:31,964 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,964 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:31,976 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:31,978 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:31,978 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:31,978 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:31,978 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:31,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:31,979 INFO L85 PathProgramCache]: Analyzing trace with hash 1271371196, now seen corresponding path program 2 times [2025-03-17 19:50:31,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:31,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120032283] [2025-03-17 19:50:31,979 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:31,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:31,984 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 16 statements into 2 equivalence classes. [2025-03-17 19:50:31,986 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 16 of 16 statements. [2025-03-17 19:50:31,986 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:31,987 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2025-03-17 19:50:31,987 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:31,999 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 [2025-03-17 19:50:32,044 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-17 19:50:32,044 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:32,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1120032283] [2025-03-17 19:50:32,044 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1120032283] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 19:50:32,044 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 19:50:32,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-17 19:50:32,044 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [586403705] [2025-03-17 19:50:32,044 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 19:50:32,069 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:32,070 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:32,070 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:32,070 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:32,070 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:32,070 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,070 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:32,070 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:32,070 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2025-03-17 19:50:32,070 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:32,070 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:32,071 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,073 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,074 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,077 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,079 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,080 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,095 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:32,095 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:32,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,097 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) [2025-03-17 19:50:32,098 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 [2025-03-17 19:50:32,099 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:32,099 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:32,109 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:32,109 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:32,115 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 [2025-03-17 19:50:32,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,116 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) [2025-03-17 19:50:32,117 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 [2025-03-17 19:50:32,119 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:32,119 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:32,129 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:32,129 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret2=0} Honda state: {rec1_#t~ret2=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:32,134 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 [2025-03-17 19:50:32,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,134 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,136 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) [2025-03-17 19:50:32,136 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 [2025-03-17 19:50:32,137 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:32,137 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:32,152 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:32,152 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,153 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,188 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) [2025-03-17 19:50:32,189 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 [2025-03-17 19:50:32,190 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:32,190 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:32,229 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:32,233 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2025-03-17 19:50:32,233 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:32,233 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:32,233 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:32,233 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:32,233 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:32,233 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,233 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:32,233 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:32,233 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2025-03-17 19:50:32,233 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:32,233 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:32,234 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,236 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,239 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,244 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,245 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,246 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,265 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:32,265 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:32,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,267 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) [2025-03-17 19:50:32,268 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 [2025-03-17 19:50:32,269 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 [2025-03-17 19:50:32,278 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:32,279 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:32,279 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:32,279 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:32,279 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:32,279 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:32,279 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:32,280 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:32,286 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 [2025-03-17 19:50:32,287 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,287 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,288 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:32,289 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2025-03-17 19:50:32,290 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 [2025-03-17 19:50:32,300 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:32,300 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:32,300 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:32,300 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:32,300 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:32,301 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:32,301 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:32,303 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:32,305 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-17 19:50:32,305 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:32,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,307 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:32,308 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2025-03-17 19:50:32,309 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:32,309 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:32,309 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:32,309 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2025-03-17 19:50:32,315 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2025-03-17 19:50:32,315 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:32,322 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:32,331 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-17 19:50:32,342 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-17 19:50:32,342 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,342 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:32,343 INFO L256 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 19:50:32,344 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:32,395 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:32,399 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:32,399 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,399 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:32,400 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:32,400 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:32,420 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:32,420 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 [2025-03-17 19:50:32,420 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 92 states and 143 transitions. cyclomatic complexity: 57 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:32,484 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 92 states and 143 transitions. cyclomatic complexity: 57. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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 132 states and 207 transitions. Complement of second has 18 states. [2025-03-17 19:50:32,485 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 [2025-03-17 19:50:32,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:32,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2025-03-17 19:50:32,486 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-17 19:50:32,486 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:32,486 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 16 letters. Loop has 3 letters. [2025-03-17 19:50:32,486 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:32,486 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 13 letters. Loop has 6 letters. [2025-03-17 19:50:32,486 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:32,486 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 132 states and 207 transitions. [2025-03-17 19:50:32,488 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:32,491 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 132 states to 120 states and 195 transitions. [2025-03-17 19:50:32,491 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 49 [2025-03-17 19:50:32,491 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2025-03-17 19:50:32,493 INFO L73 IsDeterministic]: Start isDeterministic. Operand 120 states and 195 transitions. [2025-03-17 19:50:32,493 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:32,493 INFO L218 hiAutomatonCegarLoop]: Abstraction has 120 states and 195 transitions. [2025-03-17 19:50:32,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states and 195 transitions. [2025-03-17 19:50:32,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 116. [2025-03-17 19:50:32,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 67 states have (on average 1.1791044776119404) internal successors, (79), 75 states have internal predecessors, (79), 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) [2025-03-17 19:50:32,500 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 185 transitions. [2025-03-17 19:50:32,500 INFO L240 hiAutomatonCegarLoop]: Abstraction has 116 states and 185 transitions. [2025-03-17 19:50:32,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:32,501 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-17 19:50:32,501 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-17 19:50:32,501 INFO L87 Difference]: Start difference. First operand 116 states and 185 transitions. Second operand has 6 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 19:50:32,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:32,532 INFO L93 Difference]: Finished difference Result 129 states and 195 transitions. [2025-03-17 19:50:32,532 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 129 states and 195 transitions. [2025-03-17 19:50:32,534 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 19:50:32,538 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 129 states to 127 states and 193 transitions. [2025-03-17 19:50:32,540 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 59 [2025-03-17 19:50:32,540 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 59 [2025-03-17 19:50:32,540 INFO L73 IsDeterministic]: Start isDeterministic. Operand 127 states and 193 transitions. [2025-03-17 19:50:32,540 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:32,540 INFO L218 hiAutomatonCegarLoop]: Abstraction has 127 states and 193 transitions. [2025-03-17 19:50:32,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states and 193 transitions. [2025-03-17 19:50:32,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 104. [2025-03-17 19:50:32,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 59 states have (on average 1.1355932203389831) internal successors, (67), 65 states have internal predecessors, (67), 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) [2025-03-17 19:50:32,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 157 transitions. [2025-03-17 19:50:32,548 INFO L240 hiAutomatonCegarLoop]: Abstraction has 104 states and 157 transitions. [2025-03-17 19:50:32,549 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-17 19:50:32,550 INFO L432 stractBuchiCegarLoop]: Abstraction has 104 states and 157 transitions. [2025-03-17 19:50:32,550 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-17 19:50:32,551 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 104 states and 157 transitions. [2025-03-17 19:50:32,551 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2025-03-17 19:50:32,552 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:32,552 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:32,553 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:32,553 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:32,553 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#26#return;" [2025-03-17 19:50:32,553 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret1 := rec1(#t~ret0 - 1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#24#return;" "call #t~ret2 := rec1(#t~ret1);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#26#return;" [2025-03-17 19:50:32,553 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:32,553 INFO L85 PathProgramCache]: Analyzing trace with hash -192336959, now seen corresponding path program 1 times [2025-03-17 19:50:32,553 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:32,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752709449] [2025-03-17 19:50:32,553 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:32,553 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:32,558 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 15 statements into 1 equivalence classes. [2025-03-17 19:50:32,561 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 15 of 15 statements. [2025-03-17 19:50:32,561 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,561 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:32,561 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:32,562 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 15 statements into 1 equivalence classes. [2025-03-17 19:50:32,567 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 15 of 15 statements. [2025-03-17 19:50:32,568 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,568 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:32,569 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:32,569 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:32,569 INFO L85 PathProgramCache]: Analyzing trace with hash -99532167, now seen corresponding path program 1 times [2025-03-17 19:50:32,569 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:32,569 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971707233] [2025-03-17 19:50:32,569 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:32,569 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:32,571 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-17 19:50:32,572 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-17 19:50:32,572 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,572 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:32,607 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-17 19:50:32,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:32,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971707233] [2025-03-17 19:50:32,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1971707233] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 19:50:32,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [588211842] [2025-03-17 19:50:32,607 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:32,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 19:50:32,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,609 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 19:50:32,611 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (32)] Waiting until timeout for monitored process [2025-03-17 19:50:32,628 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-17 19:50:32,633 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-17 19:50:32,633 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,633 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:32,634 INFO L256 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-03-17 19:50:32,634 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:32,651 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:32,651 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 19:50:32,651 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [588211842] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 19:50:32,652 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 19:50:32,652 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2025-03-17 19:50:32,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1789331946] [2025-03-17 19:50:32,653 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 19:50:32,653 INFO L769 eck$LassoCheckResult]: loop already infeasible [2025-03-17 19:50:32,653 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:32,653 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-17 19:50:32,653 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-17 19:50:32,653 INFO L87 Difference]: Start difference. First operand 104 states and 157 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) [2025-03-17 19:50:32,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:32,679 INFO L93 Difference]: Finished difference Result 119 states and 173 transitions. [2025-03-17 19:50:32,679 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 173 transitions. [2025-03-17 19:50:32,680 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:32,681 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 164 transitions. [2025-03-17 19:50:32,682 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2025-03-17 19:50:32,682 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 50 [2025-03-17 19:50:32,682 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 164 transitions. [2025-03-17 19:50:32,682 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:32,682 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 164 transitions. [2025-03-17 19:50:32,683 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 164 transitions. [2025-03-17 19:50:32,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 111. [2025-03-17 19:50:32,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 63 states have (on average 1.1111111111111112) internal successors, (70), 68 states have internal predecessors, (70), 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) [2025-03-17 19:50:32,691 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 161 transitions. [2025-03-17 19:50:32,691 INFO L240 hiAutomatonCegarLoop]: Abstraction has 111 states and 161 transitions. [2025-03-17 19:50:32,692 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-17 19:50:32,693 INFO L432 stractBuchiCegarLoop]: Abstraction has 111 states and 161 transitions. [2025-03-17 19:50:32,693 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-17 19:50:32,693 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 111 states and 161 transitions. [2025-03-17 19:50:32,694 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2025-03-17 19:50:32,694 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:32,694 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:32,694 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:32,695 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:32,695 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#26#return;" "call #t~ret1 := rec1(#t~ret0 - 1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#24#return;" "call #t~ret2 := rec1(#t~ret1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#22#return;" "#res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2;" "assume true;" >"#26#return;" "call #t~ret1 := rec1(#t~ret0 - 1);"< [2025-03-17 19:50:32,696 INFO L754 eck$LassoCheckResult]: Loop: "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< [2025-03-17 19:50:32,696 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:32,696 INFO L85 PathProgramCache]: Analyzing trace with hash 120691137, now seen corresponding path program 1 times [2025-03-17 19:50:32,696 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:32,696 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2146524335] [2025-03-17 19:50:32,696 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:32,696 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:32,700 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:32,706 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:32,706 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,706 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:32,707 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:32,709 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:32,713 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:32,713 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,713 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:32,714 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:32,715 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:32,715 INFO L85 PathProgramCache]: Analyzing trace with hash 36729, now seen corresponding path program 3 times [2025-03-17 19:50:32,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:32,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1827258666] [2025-03-17 19:50:32,715 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 19:50:32,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:32,721 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:32,722 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:32,722 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2025-03-17 19:50:32,722 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:32,722 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:32,722 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:32,727 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:32,727 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:32,727 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:32,727 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:32,728 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:32,728 INFO L85 PathProgramCache]: Analyzing trace with hash 622042553, now seen corresponding path program 2 times [2025-03-17 19:50:32,728 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:32,728 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1647540997] [2025-03-17 19:50:32,728 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:32,728 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:32,731 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-17 19:50:32,736 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-17 19:50:32,736 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:32,736 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:32,823 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2025-03-17 19:50:32,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:32,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1647540997] [2025-03-17 19:50:32,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1647540997] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 19:50:32,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2077041539] [2025-03-17 19:50:32,823 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:32,823 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 19:50:32,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:32,825 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 19:50:32,827 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Waiting until timeout for monitored process [2025-03-17 19:50:32,844 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-17 19:50:32,850 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-17 19:50:32,850 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:32,850 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:32,851 INFO L256 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:32,851 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:32,873 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2025-03-17 19:50:32,873 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 19:50:32,958 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2025-03-17 19:50:32,958 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2077041539] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 19:50:32,958 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 19:50:32,958 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2025-03-17 19:50:32,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [812101886] [2025-03-17 19:50:32,958 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 19:50:32,983 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:32,984 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:32,984 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:32,984 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:32,984 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:32,984 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:32,984 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:32,984 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:32,984 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2025-03-17 19:50:32,984 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:32,984 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:32,984 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,986 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,987 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,988 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,989 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:32,995 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,011 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:33,011 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:33,011 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,011 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,013 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) [2025-03-17 19:50:33,014 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 [2025-03-17 19:50:33,015 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:33,015 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:33,026 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:33,026 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:33,031 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2025-03-17 19:50:33,031 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,033 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) [2025-03-17 19:50:33,033 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 [2025-03-17 19:50:33,035 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:33,035 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:33,045 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:33,045 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret2=0} Honda state: {rec1_#t~ret2=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:33,050 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2025-03-17 19:50:33,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,052 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) [2025-03-17 19:50:33,053 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 [2025-03-17 19:50:33,054 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:33,054 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:33,064 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:33,064 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:33,069 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 [2025-03-17 19:50:33,069 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,071 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) [2025-03-17 19:50:33,072 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 [2025-03-17 19:50:33,073 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:33,073 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:33,083 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:33,083 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:33,088 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2025-03-17 19:50:33,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,090 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) [2025-03-17 19:50:33,092 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 [2025-03-17 19:50:33,092 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:33,092 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:33,109 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2025-03-17 19:50:33,109 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,111 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) [2025-03-17 19:50:33,112 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 [2025-03-17 19:50:33,113 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:33,113 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:33,152 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:33,156 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 [2025-03-17 19:50:33,156 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:33,156 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:33,156 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:33,156 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:33,156 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:33,156 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,156 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:33,156 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:33,156 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2025-03-17 19:50:33,156 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:33,156 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:33,157 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,159 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,162 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,164 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,171 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:33,189 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2025-03-17 19:50:33,205 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:33,205 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:33,205 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,207 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) [2025-03-17 19:50:33,208 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 [2025-03-17 19:50:33,209 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 [2025-03-17 19:50:33,218 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:33,218 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:33,218 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:33,218 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:33,218 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:33,219 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:33,219 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:33,220 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:33,224 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 [2025-03-17 19:50:33,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,226 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) [2025-03-17 19:50:33,227 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 [2025-03-17 19:50:33,228 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 [2025-03-17 19:50:33,238 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:33,238 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:33,239 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:33,239 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:33,239 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:33,239 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:33,239 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:33,240 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:33,246 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 [2025-03-17 19:50:33,247 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,247 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,248 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) [2025-03-17 19:50:33,250 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 [2025-03-17 19:50:33,251 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 [2025-03-17 19:50:33,261 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:33,262 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:33,262 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:33,262 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:33,262 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:33,263 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:33,263 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:33,264 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:33,272 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 [2025-03-17 19:50:33,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,274 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) [2025-03-17 19:50:33,276 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 [2025-03-17 19:50:33,277 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 [2025-03-17 19:50:33,287 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:33,287 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:33,287 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:33,287 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:33,287 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:33,287 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:33,288 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:33,290 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:33,296 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 [2025-03-17 19:50:33,296 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,296 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,300 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) [2025-03-17 19:50:33,302 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 [2025-03-17 19:50:33,303 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 [2025-03-17 19:50:33,314 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:33,314 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:33,314 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:33,314 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:33,314 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:33,315 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:33,315 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:33,320 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:33,321 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-17 19:50:33,322 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:33,322 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:33,322 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:33,324 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) [2025-03-17 19:50:33,325 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 [2025-03-17 19:50:33,327 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:33,327 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:33,327 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:33,327 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2025-03-17 19:50:33,332 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Ended with exit code 0 [2025-03-17 19:50:33,333 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:33,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:33,353 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:33,373 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:33,373 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:33,373 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:33,374 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 19:50:33,375 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:33,563 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:33,566 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:33,566 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:33,566 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:33,568 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:33,568 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:33,586 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:33,587 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 [2025-03-17 19:50:33,587 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 111 states and 161 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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) [2025-03-17 19:50:33,628 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 111 states and 161 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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 128 states and 179 transitions. Complement of second has 9 states. [2025-03-17 19:50:33,629 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 [2025-03-17 19:50:33,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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) [2025-03-17 19:50:33,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 15 transitions. [2025-03-17 19:50:33,630 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 15 transitions. Stem has 29 letters. Loop has 3 letters. [2025-03-17 19:50:33,630 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:33,630 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:33,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:33,648 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:33,667 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:33,668 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:33,668 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:33,669 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 19:50:33,670 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:33,818 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:33,822 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:33,822 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:33,822 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:33,822 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:33,823 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:33,840 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:33,841 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 [2025-03-17 19:50:33,841 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 111 states and 161 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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) [2025-03-17 19:50:33,882 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 111 states and 161 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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 128 states and 179 transitions. Complement of second has 9 states. [2025-03-17 19:50:33,882 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 [2025-03-17 19:50:33,883 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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) [2025-03-17 19:50:33,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 15 transitions. [2025-03-17 19:50:33,883 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 15 transitions. Stem has 29 letters. Loop has 3 letters. [2025-03-17 19:50:33,883 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:33,883 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:33,893 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:33,908 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:33,929 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:33,929 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:33,929 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:33,930 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 19:50:33,931 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:34,014 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Ended with exit code 0 [2025-03-17 19:50:34,103 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:34,106 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:34,106 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:34,106 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:34,107 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:34,107 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:34,124 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:34,125 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 [2025-03-17 19:50:34,125 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 111 states and 161 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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) [2025-03-17 19:50:34,194 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 111 states and 161 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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 156 states and 218 transitions. Complement of second has 17 states. [2025-03-17 19:50:34,195 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 [2025-03-17 19:50:34,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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) [2025-03-17 19:50:34,195 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 24 transitions. [2025-03-17 19:50:34,195 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 24 transitions. Stem has 29 letters. Loop has 3 letters. [2025-03-17 19:50:34,196 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:34,196 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 24 transitions. Stem has 32 letters. Loop has 3 letters. [2025-03-17 19:50:34,196 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:34,196 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 24 transitions. Stem has 29 letters. Loop has 6 letters. [2025-03-17 19:50:34,196 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:34,196 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 156 states and 218 transitions. [2025-03-17 19:50:34,197 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2025-03-17 19:50:34,201 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 156 states to 138 states and 200 transitions. [2025-03-17 19:50:34,201 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 54 [2025-03-17 19:50:34,202 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 57 [2025-03-17 19:50:34,202 INFO L73 IsDeterministic]: Start isDeterministic. Operand 138 states and 200 transitions. [2025-03-17 19:50:34,202 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:34,202 INFO L218 hiAutomatonCegarLoop]: Abstraction has 138 states and 200 transitions. [2025-03-17 19:50:34,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states and 200 transitions. [2025-03-17 19:50:34,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 119. [2025-03-17 19:50:34,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 69 states have (on average 1.1304347826086956) internal successors, (78), 74 states have internal predecessors, (78), 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) [2025-03-17 19:50:34,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 169 transitions. [2025-03-17 19:50:34,210 INFO L240 hiAutomatonCegarLoop]: Abstraction has 119 states and 169 transitions. [2025-03-17 19:50:34,210 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:34,210 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-17 19:50:34,210 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-17 19:50:34,210 INFO L87 Difference]: Start difference. First operand 119 states and 169 transitions. Second operand has 8 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 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) [2025-03-17 19:50:34,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:34,252 INFO L93 Difference]: Finished difference Result 97 states and 115 transitions. [2025-03-17 19:50:34,252 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 97 states and 115 transitions. [2025-03-17 19:50:34,253 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2025-03-17 19:50:34,253 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 97 states to 62 states and 74 transitions. [2025-03-17 19:50:34,253 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 11 [2025-03-17 19:50:34,253 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 11 [2025-03-17 19:50:34,253 INFO L73 IsDeterministic]: Start isDeterministic. Operand 62 states and 74 transitions. [2025-03-17 19:50:34,254 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:34,254 INFO L218 hiAutomatonCegarLoop]: Abstraction has 62 states and 74 transitions. [2025-03-17 19:50:34,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states and 74 transitions. [2025-03-17 19:50:34,256 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 53. [2025-03-17 19:50:34,257 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 32 states have (on average 1.125) internal successors, (36), 35 states have internal predecessors, (36), 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) [2025-03-17 19:50:34,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 64 transitions. [2025-03-17 19:50:34,257 INFO L240 hiAutomatonCegarLoop]: Abstraction has 53 states and 64 transitions. [2025-03-17 19:50:34,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-17 19:50:34,261 INFO L432 stractBuchiCegarLoop]: Abstraction has 53 states and 64 transitions. [2025-03-17 19:50:34,261 INFO L338 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2025-03-17 19:50:34,261 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 53 states and 64 transitions. [2025-03-17 19:50:34,261 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2025-03-17 19:50:34,261 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:34,261 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:34,261 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:34,261 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:34,262 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;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;" "call main_#t~ret6#1 := rec2(main_~x~0#1);"< "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#26#return;" "call #t~ret1 := rec1(#t~ret0 - 1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#24#return;" "call #t~ret2 := rec1(#t~ret1);"< "~i := #in~i;" "assume ~i <= 0;#res := 0;" "assume true;" >"#22#return;" "#res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2;" "assume true;" >"#30#return;" "call #t~ret4 := rec2(#t~ret3 - 1);"< "~j := #in~j;" "assume !(~j <= 0);" "call #t~ret3 := rec1(~j);"< [2025-03-17 19:50:34,262 INFO L754 eck$LassoCheckResult]: Loop: "~i := #in~i;" "assume !(~i <= 0);" "call #t~ret0 := rec1(~i - 2);"< [2025-03-17 19:50:34,262 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:34,262 INFO L85 PathProgramCache]: Analyzing trace with hash -1803179931, now seen corresponding path program 2 times [2025-03-17 19:50:34,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:34,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1209337553] [2025-03-17 19:50:34,262 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:34,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:34,264 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 29 statements into 2 equivalence classes. [2025-03-17 19:50:34,266 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:34,267 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:34,267 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:34,322 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-17 19:50:34,322 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:34,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1209337553] [2025-03-17 19:50:34,322 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1209337553] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 19:50:34,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2109995683] [2025-03-17 19:50:34,322 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:34,322 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 19:50:34,322 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:34,324 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) [2025-03-17 19:50:34,326 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Waiting until timeout for monitored process [2025-03-17 19:50:34,343 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 29 statements into 2 equivalence classes. [2025-03-17 19:50:34,348 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:34,348 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:34,348 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:34,348 INFO L256 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:34,349 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:34,360 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-17 19:50:34,360 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 19:50:34,430 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-17 19:50:34,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2109995683] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 19:50:34,430 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 19:50:34,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2025-03-17 19:50:34,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1939501467] [2025-03-17 19:50:34,431 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 19:50:34,431 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 19:50:34,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:34,431 INFO L85 PathProgramCache]: Analyzing trace with hash 36729, now seen corresponding path program 4 times [2025-03-17 19:50:34,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:34,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1141713258] [2025-03-17 19:50:34,431 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-17 19:50:34,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:34,433 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 3 statements into 2 equivalence classes. [2025-03-17 19:50:34,434 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:34,434 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-17 19:50:34,434 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:34,434 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:34,435 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:34,436 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:34,436 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:34,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:34,436 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:34,456 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:34,457 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:34,457 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:34,457 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:34,457 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:34,457 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,457 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:34,457 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:34,457 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2025-03-17 19:50:34,457 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:34,457 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:34,457 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,461 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,463 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,464 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,466 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,467 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,486 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:34,486 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:34,486 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,486 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:34,490 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) [2025-03-17 19:50:34,491 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 [2025-03-17 19:50:34,492 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:34,492 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:34,507 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2025-03-17 19:50:34,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:34,509 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) [2025-03-17 19:50:34,509 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 [2025-03-17 19:50:34,510 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:34,510 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:34,548 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:34,552 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Ended with exit code 0 [2025-03-17 19:50:34,552 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:34,552 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:34,552 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:34,552 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:34,552 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:34,552 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,552 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:34,552 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:34,552 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2025-03-17 19:50:34,552 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:34,552 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:34,553 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,555 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,559 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,560 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,561 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,563 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:34,582 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:34,582 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:34,582 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,582 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:34,584 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) [2025-03-17 19:50:34,586 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 [2025-03-17 19:50:34,587 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 [2025-03-17 19:50:34,597 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:34,597 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:34,597 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:34,597 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:34,597 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:34,597 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:34,597 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:34,599 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:34,605 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 [2025-03-17 19:50:34,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:34,607 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) [2025-03-17 19:50:34,608 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 [2025-03-17 19:50:34,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 [2025-03-17 19:50:34,619 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:34,619 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:34,619 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:34,619 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:34,619 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:34,620 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:34,620 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:34,621 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:34,623 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2025-03-17 19:50:34,623 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:34,623 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:34,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:34,625 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) [2025-03-17 19:50:34,626 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 [2025-03-17 19:50:34,627 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:34,627 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:34,627 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:34,627 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2025-03-17 19:50:34,632 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Ended with exit code 0 [2025-03-17 19:50:34,633 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:34,642 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:34,651 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:34,671 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:34,671 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:34,671 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:34,672 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 19:50:34,673 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:34,805 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 [2025-03-17 19:50:34,819 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:34,825 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:34,825 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:34,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:34,826 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:34,826 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:34,842 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:34,843 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 [2025-03-17 19:50:34,843 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 53 states and 64 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:34,892 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 53 states and 64 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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 63 states and 75 transitions. Complement of second has 15 states. [2025-03-17 19:50:34,893 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 [2025-03-17 19:50:34,894 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:34,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 19:50:34,895 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 29 letters. Loop has 3 letters. [2025-03-17 19:50:34,895 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:34,895 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:34,903 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:34,910 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:34,927 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:34,928 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:34,928 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:34,929 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 19:50:34,929 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:35,056 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:35,059 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:35,059 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:35,059 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:35,059 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:35,060 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:35,075 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:35,075 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 [2025-03-17 19:50:35,075 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 53 states and 64 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:35,121 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 53 states and 64 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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 63 states and 75 transitions. Complement of second has 15 states. [2025-03-17 19:50:35,122 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 [2025-03-17 19:50:35,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:35,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 19:50:35,123 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 29 letters. Loop has 3 letters. [2025-03-17 19:50:35,123 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:35,123 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:35,132 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:35,141 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-17 19:50:35,159 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-17 19:50:35,159 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:35,159 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:35,160 INFO L256 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 19:50:35,161 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:35,303 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:35,306 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:35,306 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:35,306 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:35,307 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:35,307 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:35,325 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:35,325 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 [2025-03-17 19:50:35,326 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 53 states and 64 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:35,388 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 53 states and 64 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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 77 states and 89 transitions. Complement of second has 15 states. [2025-03-17 19:50:35,388 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 [2025-03-17 19:50:35,389 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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) [2025-03-17 19:50:35,389 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 24 transitions. [2025-03-17 19:50:35,389 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 24 transitions. Stem has 29 letters. Loop has 3 letters. [2025-03-17 19:50:35,389 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:35,389 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 24 transitions. Stem has 32 letters. Loop has 3 letters. [2025-03-17 19:50:35,390 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:35,390 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 24 transitions. Stem has 29 letters. Loop has 6 letters. [2025-03-17 19:50:35,390 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:35,390 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 77 states and 89 transitions. [2025-03-17 19:50:35,390 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 19:50:35,390 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 77 states to 0 states and 0 transitions. [2025-03-17 19:50:35,391 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 19:50:35,391 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 19:50:35,391 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 19:50:35,391 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 19:50:35,391 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:35,391 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:35,391 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:35,391 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-17 19:50:35,391 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-17 19:50:35,391 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 8 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 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) [2025-03-17 19:50:35,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:35,391 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2025-03-17 19:50:35,391 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2025-03-17 19:50:35,391 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 19:50:35,392 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2025-03-17 19:50:35,392 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 19:50:35,392 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 19:50:35,392 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 19:50:35,392 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 19:50:35,392 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:35,392 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:35,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-17 19:50:35,392 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:35,392 INFO L338 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2025-03-17 19:50:35,392 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-17 19:50:35,392 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 19:50:35,392 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-17 19:50:35,398 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.03 07:50:35 BoogieIcfgContainer [2025-03-17 19:50:35,399 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-17 19:50:35,399 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-17 19:50:35,399 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-17 19:50:35,399 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-17 19:50:35,400 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:50:29" (3/4) ... [2025-03-17 19:50:35,401 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-17 19:50:35,402 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-17 19:50:35,402 INFO L158 Benchmark]: Toolchain (without parser) took 6125.03ms. Allocated memory is still 167.8MB. Free memory was 121.9MB in the beginning and 50.2MB in the end (delta: 71.8MB). Peak memory consumption was 67.2MB. Max. memory is 16.1GB. [2025-03-17 19:50:35,402 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 201.3MB. Free memory is still 118.7MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:35,402 INFO L158 Benchmark]: CACSL2BoogieTranslator took 128.85ms. Allocated memory is still 167.8MB. Free memory was 121.5MB in the beginning and 111.8MB in the end (delta: 9.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 19:50:35,403 INFO L158 Benchmark]: Boogie Procedure Inliner took 16.51ms. Allocated memory is still 167.8MB. Free memory was 111.8MB in the beginning and 110.9MB in the end (delta: 905.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:35,403 INFO L158 Benchmark]: Boogie Preprocessor took 15.86ms. Allocated memory is still 167.8MB. Free memory was 110.9MB in the beginning and 110.0MB in the end (delta: 903.7kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:35,403 INFO L158 Benchmark]: IcfgBuilder took 212.51ms. Allocated memory is still 167.8MB. Free memory was 110.0MB in the beginning and 98.8MB in the end (delta: 11.2MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-17 19:50:35,403 INFO L158 Benchmark]: BuchiAutomizer took 5744.75ms. Allocated memory is still 167.8MB. Free memory was 98.8MB in the beginning and 50.2MB in the end (delta: 48.6MB). Peak memory consumption was 42.1MB. Max. memory is 16.1GB. [2025-03-17 19:50:35,403 INFO L158 Benchmark]: Witness Printer took 2.65ms. Allocated memory is still 167.8MB. Free memory was 50.2MB in the beginning and 50.2MB in the end (delta: 50.8kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:35,404 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.21ms. Allocated memory is still 201.3MB. Free memory is still 118.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 128.85ms. Allocated memory is still 167.8MB. Free memory was 121.5MB in the beginning and 111.8MB in the end (delta: 9.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 16.51ms. Allocated memory is still 167.8MB. Free memory was 111.8MB in the beginning and 110.9MB in the end (delta: 905.1kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 15.86ms. Allocated memory is still 167.8MB. Free memory was 110.9MB in the beginning and 110.0MB in the end (delta: 903.7kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 212.51ms. Allocated memory is still 167.8MB. Free memory was 110.0MB in the beginning and 98.8MB in the end (delta: 11.2MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * BuchiAutomizer took 5744.75ms. Allocated memory is still 167.8MB. Free memory was 98.8MB in the beginning and 50.2MB in the end (delta: 48.6MB). Peak memory consumption was 42.1MB. Max. memory is 16.1GB. * Witness Printer took 2.65ms. Allocated memory is still 167.8MB. Free memory was 50.2MB in the beginning and 50.2MB in the end (delta: 50.8kB). 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 5.7s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 2.8s. Construction of modules took 0.3s. Büchi inclusion checks took 2.3s. 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, 191 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 168 mSDsluCounter, 495 SdHoareTripleChecker+Invalid, 0.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 310 mSDsCounter, 129 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 337 IncrementalHoareTripleChecker+Invalid, 466 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 129 mSolverCounterUnsat, 185 mSDtfsCounter, 337 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: 28ms 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! [2025-03-17 19:50:35,416 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:35,616 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:35,816 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (32)] Ended with exit code 0 [2025-03-17 19:50:36,018 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE