./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 48c9605d Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/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 b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 --- Real Ultimate output --- This is Ultimate 0.3.0-?-48c9605-m [2025-02-08 14:18:01,760 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-08 14:18:01,812 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2025-02-08 14:18:01,818 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-08 14:18:01,819 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-08 14:18:01,819 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-02-08 14:18:01,833 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-08 14:18:01,833 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-08 14:18:01,834 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-08 14:18:01,834 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-08 14:18:01,834 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-08 14:18:01,834 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-08 14:18:01,834 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-08 14:18:01,834 INFO L153 SettingsManager]: * Use SBE=true [2025-02-08 14:18:01,834 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Use old map elimination=false [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-02-08 14:18:01,835 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-02-08 14:18:01,835 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-08 14:18:01,836 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-08 14:18:01,836 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-08 14:18:01,836 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-08 14:18:01,836 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-02-08 14:18:01,836 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-jdk21/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 -> b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 [2025-02-08 14:18:02,046 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-08 14:18:02,069 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-08 14:18:02,070 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-08 14:18:02,071 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-08 14:18:02,075 INFO L274 PluginConnector]: CDTParser initialized [2025-02-08 14:18:02,077 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-02-08 14:18:03,329 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/965c9524c/7b839f746b9b4cc689a4ee6e41b5a5f2/FLAG3435adf63 [2025-02-08 14:18:03,538 INFO L384 CDTParser]: Found 1 translation units. [2025-02-08 14:18:03,538 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-02-08 14:18:03,547 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/965c9524c/7b839f746b9b4cc689a4ee6e41b5a5f2/FLAG3435adf63 [2025-02-08 14:18:03,891 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/965c9524c/7b839f746b9b4cc689a4ee6e41b5a5f2 [2025-02-08 14:18:03,896 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-08 14:18:03,898 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-08 14:18:03,901 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-08 14:18:03,901 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-08 14:18:03,904 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-08 14:18:03,904 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.02 02:18:03" (1/1) ... [2025-02-08 14:18:03,906 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@a87a9a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:03, skipping insertion in model container [2025-02-08 14:18:03,906 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.02 02:18:03" (1/1) ... [2025-02-08 14:18:03,914 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-08 14:18:03,998 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-08 14:18:04,001 INFO L200 MainTranslator]: Completed pre-run [2025-02-08 14:18:04,009 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-08 14:18:04,017 INFO L204 MainTranslator]: Completed translation [2025-02-08 14:18:04,018 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04 WrapperNode [2025-02-08 14:18:04,018 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-08 14:18:04,019 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-08 14:18:04,019 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-08 14:18:04,019 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-08 14:18:04,024 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,025 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,034 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2025-02-08 14:18:04,034 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-08 14:18:04,034 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-08 14:18:04,034 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-08 14:18:04,035 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-08 14:18:04,039 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,039 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,040 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,043 INFO L175 MemorySlicer]: No memory access in input program. [2025-02-08 14:18:04,043 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,043 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,044 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,044 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,045 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,045 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,046 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-08 14:18:04,047 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-08 14:18:04,047 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-08 14:18:04,047 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-08 14:18:04,048 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (1/1) ... [2025-02-08 14:18:04,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:04,078 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:04,084 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2025-02-08 14:18:04,102 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-08 14:18:04,102 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-08 14:18:04,102 INFO L130 BoogieDeclarations]: Found specification of procedure mc91 [2025-02-08 14:18:04,102 INFO L138 BoogieDeclarations]: Found implementation of procedure mc91 [2025-02-08 14:18:04,136 INFO L257 CfgBuilder]: Building ICFG [2025-02-08 14:18:04,137 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-08 14:18:04,210 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2025-02-08 14:18:04,210 INFO L308 CfgBuilder]: Performing block encoding [2025-02-08 14:18:04,217 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-08 14:18:04,217 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-08 14:18:04,218 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 02:18:04 BoogieIcfgContainer [2025-02-08 14:18:04,218 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-08 14:18:04,219 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-02-08 14:18:04,219 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-02-08 14:18:04,223 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-02-08 14:18:04,223 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-02-08 14:18:04,223 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 08.02 02:18:03" (1/3) ... [2025-02-08 14:18:04,224 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@326310c9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 08.02 02:18:04, skipping insertion in model container [2025-02-08 14:18:04,224 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-02-08 14:18:04,224 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.02 02:18:04" (2/3) ... [2025-02-08 14:18:04,224 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@326310c9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 08.02 02:18:04, skipping insertion in model container [2025-02-08 14:18:04,224 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-02-08 14:18:04,224 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 02:18:04" (3/3) ... [2025-02-08 14:18:04,225 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91_Recursion.c [2025-02-08 14:18:04,260 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-02-08 14:18:04,263 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-02-08 14:18:04,263 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-02-08 14:18:04,263 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-02-08 14:18:04,264 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-02-08 14:18:04,264 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-02-08 14:18:04,264 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-02-08 14:18:04,264 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-02-08 14:18:04,267 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 12 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 7 states have internal predecessors, (8), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-08 14:18:04,284 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-02-08 14:18:04,287 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-08 14:18:04,288 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-08 14:18:04,291 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-02-08 14:18:04,294 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-02-08 14:18:04,294 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-02-08 14:18:04,294 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 12 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 7 states have internal predecessors, (8), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-08 14:18:04,295 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-02-08 14:18:04,295 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-08 14:18:04,295 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-08 14:18:04,295 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-02-08 14:18:04,295 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-02-08 14:18:04,302 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~nondet2#1, main_#t~ret3#1, main_~x~0#1;havoc main_#t~nondet2#1;main_~x~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;" "call main_#t~ret3#1 := mc91(main_~x~0#1);"< [2025-02-08 14:18:04,305 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< [2025-02-08 14:18:04,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,308 INFO L85 PathProgramCache]: Analyzing trace with hash 1034, now seen corresponding path program 1 times [2025-02-08 14:18:04,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:04,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2070951376] [2025-02-08 14:18:04,318 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:04,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:04,375 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-02-08 14:18:04,377 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-02-08 14:18:04,377 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,377 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:04,378 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-02-08 14:18:04,379 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-02-08 14:18:04,379 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,379 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,387 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:04,389 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,389 INFO L85 PathProgramCache]: Analyzing trace with hash 38703, now seen corresponding path program 1 times [2025-02-08 14:18:04,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:04,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [184055256] [2025-02-08 14:18:04,389 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:04,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:04,391 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:04,400 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:04,401 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,401 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,401 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:04,402 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:04,403 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:04,403 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,403 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,404 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:04,404 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,405 INFO L85 PathProgramCache]: Analyzing trace with hash 30812806, now seen corresponding path program 1 times [2025-02-08 14:18:04,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:04,405 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [764172998] [2025-02-08 14:18:04,405 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:04,405 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:04,411 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-02-08 14:18:04,412 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-02-08 14:18:04,412 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,412 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,412 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:04,413 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-02-08 14:18:04,415 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-02-08 14:18:04,416 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,416 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,417 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:04,496 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:04,496 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:04,496 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:04,496 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:04,496 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-08 14:18:04,496 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,497 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:04,497 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:04,497 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-02-08 14:18:04,497 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:04,498 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:04,505 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,515 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,517 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,520 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,522 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,554 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:04,555 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-08 14:18:04,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:04,560 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:04,567 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2025-02-08 14:18:04,567 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:04,568 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:04,586 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:04,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,586 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:04,590 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:04,591 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2025-02-08 14:18:04,592 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-08 14:18:04,592 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:04,637 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-08 14:18:04,644 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2025-02-08 14:18:04,644 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:04,644 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:04,644 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:04,644 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:04,644 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-08 14:18:04,644 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,644 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:04,644 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:04,644 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-02-08 14:18:04,644 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:04,644 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:04,646 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,652 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,654 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,657 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,659 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:04,685 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:04,688 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-08 14:18:04,688 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:04,691 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:04,693 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2025-02-08 14:18:04,694 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-02-08 14:18:04,709 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:04,709 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:04,710 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:04,710 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:04,710 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:04,716 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:04,716 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:04,724 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-08 14:18:04,728 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-08 14:18:04,729 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-08 14:18:04,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:04,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:04,735 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:04,741 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-08 14:18:04,741 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-08 14:18:04,742 INFO L474 LassoAnalysis]: Proved termination. [2025-02-08 14:18:04,742 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 211 Supporting invariants [] [2025-02-08 14:18:04,743 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2025-02-08 14:18:04,751 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2025-02-08 14:18:04,753 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-08 14:18:04,775 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,783 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-02-08 14:18:04,788 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-02-08 14:18:04,788 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,788 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:04,789 INFO L256 TraceCheckSpWp]: Trace formula consists of 35 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-08 14:18:04,790 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:04,799 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:04,805 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:04,806 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,806 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:04,806 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-08 14:18:04,807 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:04,839 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:04,856 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-02-08 14:18:04,858 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 12 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 7 states have internal predecessors, (8), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-08 14:18:04,924 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 12 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 7 states have internal predecessors, (8), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 30 states and 37 transitions. Complement of second has 16 states. [2025-02-08 14:18:04,926 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-02-08 14:18:04,928 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-08 14:18:04,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 7 transitions. [2025-02-08 14:18:04,933 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 3 letters. [2025-02-08 14:18:04,933 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:04,933 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 5 letters. Loop has 3 letters. [2025-02-08 14:18:04,934 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:04,934 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 6 letters. [2025-02-08 14:18:04,934 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:04,934 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 30 states and 37 transitions. [2025-02-08 14:18:04,936 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-02-08 14:18:04,939 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 30 states to 18 states and 24 transitions. [2025-02-08 14:18:04,940 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2025-02-08 14:18:04,940 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 13 [2025-02-08 14:18:04,940 INFO L73 IsDeterministic]: Start isDeterministic. Operand 18 states and 24 transitions. [2025-02-08 14:18:04,940 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-08 14:18:04,940 INFO L218 hiAutomatonCegarLoop]: Abstraction has 18 states and 24 transitions. [2025-02-08 14:18:04,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states and 24 transitions. [2025-02-08 14:18:04,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 16. [2025-02-08 14:18:04,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:04,959 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 20 transitions. [2025-02-08 14:18:04,959 INFO L240 hiAutomatonCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-02-08 14:18:04,960 INFO L432 stractBuchiCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-02-08 14:18:04,960 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-02-08 14:18:04,960 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 16 states and 20 transitions. [2025-02-08 14:18:04,960 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-02-08 14:18:04,960 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-08 14:18:04,960 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-08 14:18:04,961 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 14:18:04,961 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-02-08 14:18:04,961 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~nondet2#1, main_#t~ret3#1, main_~x~0#1;havoc main_#t~nondet2#1;main_~x~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;" "call main_#t~ret3#1 := mc91(main_~x~0#1);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" [2025-02-08 14:18:04,962 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" [2025-02-08 14:18:04,962 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,962 INFO L85 PathProgramCache]: Analyzing trace with hash 2115346215, now seen corresponding path program 1 times [2025-02-08 14:18:04,962 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:04,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [325576827] [2025-02-08 14:18:04,962 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:04,963 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:04,965 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-08 14:18:04,968 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-08 14:18:04,968 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,969 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,969 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:04,970 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-08 14:18:04,972 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-08 14:18:04,972 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,973 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,974 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:04,974 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,974 INFO L85 PathProgramCache]: Analyzing trace with hash -984999739, now seen corresponding path program 1 times [2025-02-08 14:18:04,975 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:04,975 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1547369549] [2025-02-08 14:18:04,975 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:04,975 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:04,978 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:04,980 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:04,980 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,980 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:04,982 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:04,984 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:04,984 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,984 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,985 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:04,985 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:04,986 INFO L85 PathProgramCache]: Analyzing trace with hash -512151061, now seen corresponding path program 1 times [2025-02-08 14:18:04,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:04,986 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1679853826] [2025-02-08 14:18:04,986 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:04,986 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:04,989 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-02-08 14:18:04,993 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-02-08 14:18:04,994 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:04,994 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:04,994 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:04,995 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-02-08 14:18:05,000 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-02-08 14:18:05,000 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:05,000 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:05,002 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:05,110 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:05,124 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:05,124 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:05,124 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:05,125 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:05,125 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-08 14:18:05,125 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,125 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:05,125 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:05,125 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-02-08 14:18:05,125 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:05,125 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:05,126 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:05,127 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:05,129 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:05,165 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:05,165 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-08 14:18:05,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,167 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,170 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2025-02-08 14:18:05,171 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:05,171 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:05,182 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-08 14:18:05,182 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#t~ret1=0} Honda state: {mc91_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-08 14:18:05,188 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2025-02-08 14:18:05,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,191 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,192 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-02-08 14:18:05,193 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:05,193 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:05,207 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-08 14:18:05,207 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-08 14:18:05,213 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-02-08 14:18:05,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,216 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,217 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2025-02-08 14:18:05,220 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:05,220 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:05,268 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:05,268 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,268 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,270 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,271 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2025-02-08 14:18:05,273 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-08 14:18:05,273 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:05,790 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-08 14:18:05,804 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2025-02-08 14:18:05,805 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:05,805 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:05,805 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:05,805 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:05,805 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-08 14:18:05,805 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,805 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:05,805 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:05,805 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-02-08 14:18:05,805 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:05,805 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:05,806 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:05,808 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:05,817 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:05,848 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:05,848 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-08 14:18:05,848 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,848 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,851 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,852 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2025-02-08 14:18:05,853 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-02-08 14:18:05,862 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:05,863 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:05,863 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:05,863 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:05,863 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:05,863 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:05,863 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:05,865 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-08 14:18:05,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:05,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,872 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,873 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2025-02-08 14:18:05,874 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-02-08 14:18:05,884 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:05,884 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:05,884 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:05,885 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:05,885 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:05,888 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:05,888 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:05,891 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-08 14:18:05,897 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-08 14:18:05,897 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-08 14:18:05,897 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:05,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:05,902 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:05,903 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-02-08 14:18:05,904 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-08 14:18:05,904 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-08 14:18:05,904 INFO L474 LassoAnalysis]: Proved termination. [2025-02-08 14:18:05,904 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2025-02-08 14:18:05,910 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2025-02-08 14:18:05,914 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-08 14:18:05,916 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2025-02-08 14:18:05,926 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:05,930 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-02-08 14:18:05,938 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-02-08 14:18:05,938 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:05,938 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:05,939 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-02-08 14:18:05,940 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:05,989 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:05,998 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:05,998 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:05,998 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:05,998 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-02-08 14:18:05,999 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:06,078 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:06,079 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-02-08 14:18:06,079 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 16 states and 20 transitions. cyclomatic complexity: 6 Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-08 14:18:06,230 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 16 states and 20 transitions. cyclomatic complexity: 6. Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 50 states and 72 transitions. Complement of second has 32 states. [2025-02-08 14:18:06,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2025-02-08 14:18:06,232 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), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-08 14:18:06,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-02-08 14:18:06,233 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 8 letters. [2025-02-08 14:18:06,233 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:06,233 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 17 letters. Loop has 8 letters. [2025-02-08 14:18:06,234 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:06,234 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 16 letters. [2025-02-08 14:18:06,234 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:06,234 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 50 states and 72 transitions. [2025-02-08 14:18:06,236 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-02-08 14:18:06,238 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 50 states to 41 states and 61 transitions. [2025-02-08 14:18:06,238 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-02-08 14:18:06,238 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 26 [2025-02-08 14:18:06,238 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 61 transitions. [2025-02-08 14:18:06,238 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-08 14:18:06,239 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 61 transitions. [2025-02-08 14:18:06,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 61 transitions. [2025-02-08 14:18:06,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 35. [2025-02-08 14:18:06,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 10 states have call successors, (13), 7 states have call predecessors, (13), 4 states have return successors, (12), 5 states have call predecessors, (12), 7 states have call successors, (12) [2025-02-08 14:18:06,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 50 transitions. [2025-02-08 14:18:06,242 INFO L240 hiAutomatonCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-02-08 14:18:06,242 INFO L432 stractBuchiCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-02-08 14:18:06,242 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-02-08 14:18:06,242 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 35 states and 50 transitions. [2025-02-08 14:18:06,243 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-02-08 14:18:06,243 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-08 14:18:06,243 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-08 14:18:06,243 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-02-08 14:18:06,243 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-02-08 14:18:06,244 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~nondet2#1, main_#t~ret3#1, main_~x~0#1;havoc main_#t~nondet2#1;main_~x~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;" "call main_#t~ret3#1 := mc91(main_~x~0#1);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume !(~n > 100);" [2025-02-08 14:18:06,244 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" [2025-02-08 14:18:06,244 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:06,244 INFO L85 PathProgramCache]: Analyzing trace with hash -1776030363, now seen corresponding path program 2 times [2025-02-08 14:18:06,244 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:06,244 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [834749451] [2025-02-08 14:18:06,244 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 14:18:06,244 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:06,247 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 12 statements into 2 equivalence classes. [2025-02-08 14:18:06,252 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 12 of 12 statements. [2025-02-08 14:18:06,252 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 14:18:06,252 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:06,252 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:06,253 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-08 14:18:06,255 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-08 14:18:06,255 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:06,255 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:06,256 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:06,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:06,257 INFO L85 PathProgramCache]: Analyzing trace with hash 44493, now seen corresponding path program 2 times [2025-02-08 14:18:06,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:06,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2021527718] [2025-02-08 14:18:06,257 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 14:18:06,257 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:06,259 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:06,259 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:06,260 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-02-08 14:18:06,260 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:06,260 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:06,260 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:06,261 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:06,261 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:06,261 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:06,262 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:06,262 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:06,262 INFO L85 PathProgramCache]: Analyzing trace with hash -18410007, now seen corresponding path program 3 times [2025-02-08 14:18:06,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:06,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [755877878] [2025-02-08 14:18:06,262 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 14:18:06,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:06,265 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 15 statements into 4 equivalence classes. [2025-02-08 14:18:06,269 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 15 of 15 statements. [2025-02-08 14:18:06,269 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-02-08 14:18:06,269 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:06,401 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-02-08 14:18:06,402 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 14:18:06,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [755877878] [2025-02-08 14:18:06,402 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [755877878] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-08 14:18:06,402 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-08 14:18:06,402 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-02-08 14:18:06,403 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1677990593] [2025-02-08 14:18:06,403 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-08 14:18:06,473 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:06,474 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:06,474 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:06,474 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:06,474 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-08 14:18:06,474 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:06,474 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:06,474 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:06,474 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-02-08 14:18:06,474 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:06,474 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:06,475 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,480 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,481 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,483 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,509 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:06,509 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-08 14:18:06,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:06,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:06,514 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:06,516 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2025-02-08 14:18:06,517 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:06,517 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:06,542 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2025-02-08 14:18:06,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:06,543 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:06,544 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:06,546 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2025-02-08 14:18:06,547 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-08 14:18:06,547 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:06,840 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-08 14:18:06,849 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:06,850 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:06,850 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:06,850 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:06,850 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:06,850 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-08 14:18:06,850 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:06,850 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:06,850 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:06,850 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-02-08 14:18:06,850 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:06,850 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:06,851 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,860 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,862 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,864 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:06,884 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:06,884 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-08 14:18:06,884 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:06,884 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:06,887 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:06,888 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2025-02-08 14:18:06,889 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-02-08 14:18:06,899 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:06,899 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:06,899 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:06,899 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:06,899 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:06,900 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:06,900 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:06,902 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-08 14:18:06,904 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-08 14:18:06,904 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-08 14:18:06,904 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:06,905 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:06,906 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:06,907 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2025-02-08 14:18:06,909 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-08 14:18:06,909 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-08 14:18:06,909 INFO L474 LassoAnalysis]: Proved termination. [2025-02-08 14:18:06,909 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_~n) = -2*mc91_~n + 189 Supporting invariants [] [2025-02-08 14:18:06,915 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2025-02-08 14:18:06,916 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-08 14:18:06,939 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:06,944 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2025-02-08 14:18:06,945 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:06,950 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-08 14:18:06,959 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-08 14:18:06,959 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:06,959 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:06,960 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 14:18:06,961 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,014 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:07,017 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:07,017 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,017 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,018 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-08 14:18:07,018 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,039 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:07,039 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-02-08 14:18:07,040 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,101 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 42 states and 58 transitions. Complement of second has 13 states. [2025-02-08 14:18:07,103 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-02-08 14:18:07,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-02-08 14:18:07,103 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-02-08 14:18:07,103 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:07,103 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:07,114 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:07,120 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-08 14:18:07,133 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-08 14:18:07,134 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,134 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,134 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 14:18:07,135 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,181 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:07,185 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:07,185 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,185 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,185 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-08 14:18:07,186 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,204 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:07,204 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-02-08 14:18:07,204 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,251 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 42 states and 58 transitions. Complement of second has 13 states. [2025-02-08 14:18:07,252 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-02-08 14:18:07,252 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,252 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-02-08 14:18:07,252 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-02-08 14:18:07,253 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:07,253 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:07,263 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:07,269 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-08 14:18:07,278 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-08 14:18:07,278 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,278 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,279 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-08 14:18:07,279 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,323 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-02-08 14:18:07,327 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-02-08 14:18:07,327 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,327 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,328 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-02-08 14:18:07,328 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,352 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:07,353 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-02-08 14:18:07,353 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,415 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 70 states and 99 transitions. Complement of second has 16 states. [2025-02-08 14:18:07,415 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-02-08 14:18:07,416 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2025-02-08 14:18:07,416 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 3 letters. [2025-02-08 14:18:07,416 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:07,416 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 15 letters. Loop has 3 letters. [2025-02-08 14:18:07,416 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:07,416 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 6 letters. [2025-02-08 14:18:07,417 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:07,417 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 70 states and 99 transitions. [2025-02-08 14:18:07,418 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-02-08 14:18:07,420 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 70 states to 47 states and 73 transitions. [2025-02-08 14:18:07,420 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-02-08 14:18:07,420 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-02-08 14:18:07,420 INFO L73 IsDeterministic]: Start isDeterministic. Operand 47 states and 73 transitions. [2025-02-08 14:18:07,420 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-08 14:18:07,420 INFO L218 hiAutomatonCegarLoop]: Abstraction has 47 states and 73 transitions. [2025-02-08 14:18:07,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states and 73 transitions. [2025-02-08 14:18:07,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 41. [2025-02-08 14:18:07,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 25 states have (on average 1.04) internal successors, (26), 25 states have internal predecessors, (26), 11 states have call successors, (18), 9 states have call predecessors, (18), 5 states have return successors, (15), 6 states have call predecessors, (15), 8 states have call successors, (15) [2025-02-08 14:18:07,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 59 transitions. [2025-02-08 14:18:07,424 INFO L240 hiAutomatonCegarLoop]: Abstraction has 41 states and 59 transitions. [2025-02-08 14:18:07,424 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 14:18:07,426 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-02-08 14:18:07,426 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-02-08 14:18:07,427 INFO L87 Difference]: Start difference. First operand 41 states and 59 transitions. Second operand has 8 states, 6 states have (on average 1.5) internal successors, (9), 5 states have internal predecessors, (9), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-02-08 14:18:07,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 14:18:07,512 INFO L93 Difference]: Finished difference Result 62 states and 81 transitions. [2025-02-08 14:18:07,513 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 62 states and 81 transitions. [2025-02-08 14:18:07,516 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-02-08 14:18:07,518 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 62 states to 57 states and 74 transitions. [2025-02-08 14:18:07,518 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2025-02-08 14:18:07,519 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 41 [2025-02-08 14:18:07,519 INFO L73 IsDeterministic]: Start isDeterministic. Operand 57 states and 74 transitions. [2025-02-08 14:18:07,519 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-08 14:18:07,519 INFO L218 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-02-08 14:18:07,519 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states and 74 transitions. [2025-02-08 14:18:07,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2025-02-08 14:18:07,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 34 states have (on average 1.0588235294117647) internal successors, (36), 36 states have internal predecessors, (36), 13 states have call successors, (18), 11 states have call predecessors, (18), 9 states have return successors, (19), 8 states have call predecessors, (19), 11 states have call successors, (19) [2025-02-08 14:18:07,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2025-02-08 14:18:07,522 INFO L240 hiAutomatonCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-02-08 14:18:07,523 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-08 14:18:07,523 INFO L432 stractBuchiCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-02-08 14:18:07,523 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-02-08 14:18:07,523 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 56 states and 73 transitions. [2025-02-08 14:18:07,524 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-02-08 14:18:07,524 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-08 14:18:07,524 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-08 14:18:07,530 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2025-02-08 14:18:07,530 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-02-08 14:18:07,530 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~nondet2#1, main_#t~ret3#1, main_~x~0#1;havoc main_#t~nondet2#1;main_~x~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;" "call main_#t~ret3#1 := mc91(main_~x~0#1);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#14#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-02-08 14:18:07,530 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#14#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-02-08 14:18:07,530 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:07,530 INFO L85 PathProgramCache]: Analyzing trace with hash 1357151171, now seen corresponding path program 1 times [2025-02-08 14:18:07,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:07,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1445834701] [2025-02-08 14:18:07,531 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:07,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:07,533 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-02-08 14:18:07,541 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-02-08 14:18:07,544 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,544 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:07,545 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:07,546 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-02-08 14:18:07,553 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-02-08 14:18:07,554 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,554 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:07,555 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:07,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:07,559 INFO L85 PathProgramCache]: Analyzing trace with hash -1529186708, now seen corresponding path program 1 times [2025-02-08 14:18:07,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:07,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2122960943] [2025-02-08 14:18:07,559 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-08 14:18:07,559 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:07,561 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-02-08 14:18:07,570 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-02-08 14:18:07,572 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,572 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:07,572 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:07,574 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-02-08 14:18:07,577 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-02-08 14:18:07,580 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:07,581 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:07,582 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:07,584 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:07,584 INFO L85 PathProgramCache]: Analyzing trace with hash -1944416406, now seen corresponding path program 2 times [2025-02-08 14:18:07,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:07,584 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [496883541] [2025-02-08 14:18:07,584 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 14:18:07,584 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:07,589 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-02-08 14:18:07,601 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-02-08 14:18:07,601 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 14:18:07,601 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,722 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-02-08 14:18:07,722 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-08 14:18:07,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [496883541] [2025-02-08 14:18:07,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [496883541] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-08 14:18:07,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1218114452] [2025-02-08 14:18:07,722 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 14:18:07,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-08 14:18:07,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:07,725 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-08 14:18:07,726 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-02-08 14:18:07,751 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-02-08 14:18:07,763 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-02-08 14:18:07,763 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 14:18:07,763 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:07,767 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-02-08 14:18:07,773 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:07,816 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-02-08 14:18:07,817 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-08 14:18:07,998 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-02-08 14:18:07,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1218114452] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-08 14:18:07,999 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-08 14:18:07,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-02-08 14:18:07,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1734963336] [2025-02-08 14:18:07,999 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-08 14:18:08,124 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:08,124 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:08,124 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:08,124 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:08,124 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-08 14:18:08,124 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:08,124 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:08,124 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:08,124 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-02-08 14:18:08,124 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:08,124 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:08,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,128 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,130 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,131 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,132 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,148 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:08,148 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-08 14:18:08,148 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:08,148 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:08,150 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:08,151 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-02-08 14:18:08,156 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:08,156 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:08,201 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-02-08 14:18:08,201 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:08,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:08,203 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:08,215 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2025-02-08 14:18:08,216 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-08 14:18:08,216 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:08,229 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-08 14:18:08,235 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:08,236 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:08,236 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:08,236 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:08,236 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:08,236 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-08 14:18:08,236 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:08,236 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:08,236 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:08,236 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-02-08 14:18:08,237 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:08,237 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:08,238 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,247 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,252 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,253 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,254 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:08,289 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:08,290 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-08 14:18:08,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:08,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:08,294 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:08,295 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2025-02-08 14:18:08,299 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-02-08 14:18:08,309 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:08,309 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:08,309 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:08,309 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:08,309 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:08,312 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:08,312 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:08,317 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-08 14:18:08,320 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-08 14:18:08,320 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-08 14:18:08,320 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:08,321 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:08,322 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:08,324 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2025-02-08 14:18:08,325 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-08 14:18:08,325 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-08 14:18:08,325 INFO L474 LassoAnalysis]: Proved termination. [2025-02-08 14:18:08,325 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -1*mc91_#in~n + 90 Supporting invariants [] [2025-02-08 14:18:08,331 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2025-02-08 14:18:08,331 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-08 14:18:08,348 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:08,356 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-02-08 14:18:08,371 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-02-08 14:18:08,371 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:08,371 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:08,372 INFO L256 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-08 14:18:08,373 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:08,577 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-02-08 14:18:08,595 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-02-08 14:18:08,596 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:08,596 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:08,597 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-02-08 14:18:08,598 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:08,640 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:08,835 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-02-08 14:18:08,836 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 10 loop predicates [2025-02-08 14:18:08,836 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-02-08 14:18:09,129 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Result 124 states and 149 transitions. Complement of second has 49 states. [2025-02-08 14:18:09,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 15 states 2 stem states 12 non-accepting loop states 1 accepting loop states [2025-02-08 14:18:09,130 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-02-08 14:18:09,130 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-02-08 14:18:09,130 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-02-08 14:18:09,130 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:09,131 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:09,138 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:09,146 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-02-08 14:18:09,161 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-02-08 14:18:09,161 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:09,161 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:09,161 INFO L256 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-08 14:18:09,162 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:09,261 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-02-08 14:18:09,275 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-02-08 14:18:09,275 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:09,275 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:09,277 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-02-08 14:18:09,278 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:09,435 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-02-08 14:18:09,435 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 10 loop predicates [2025-02-08 14:18:09,436 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-02-08 14:18:09,669 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Result 124 states and 149 transitions. Complement of second has 49 states. [2025-02-08 14:18:09,670 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 15 states 2 stem states 12 non-accepting loop states 1 accepting loop states [2025-02-08 14:18:09,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-02-08 14:18:09,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-02-08 14:18:09,671 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-02-08 14:18:09,671 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:09,671 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:09,679 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:09,685 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-02-08 14:18:09,698 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-02-08 14:18:09,698 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:09,698 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:09,699 INFO L256 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-08 14:18:09,700 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:09,795 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-02-08 14:18:09,806 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-02-08 14:18:09,807 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:09,807 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:09,807 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 14:18:09,808 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:09,913 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-08 14:18:09,913 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 9 loop predicates [2025-02-08 14:18:09,913 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-02-08 14:18:10,446 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Result 324 states and 416 transitions. Complement of second has 131 states. [2025-02-08 14:18:10,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 19 states 2 stem states 16 non-accepting loop states 1 accepting loop states [2025-02-08 14:18:10,447 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-02-08 14:18:10,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 49 transitions. [2025-02-08 14:18:10,448 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 49 transitions. Stem has 21 letters. Loop has 19 letters. [2025-02-08 14:18:10,448 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:10,448 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 49 transitions. Stem has 40 letters. Loop has 19 letters. [2025-02-08 14:18:10,448 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:10,448 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 49 transitions. Stem has 21 letters. Loop has 38 letters. [2025-02-08 14:18:10,449 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:10,449 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 324 states and 416 transitions. [2025-02-08 14:18:10,454 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 25 [2025-02-08 14:18:10,456 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 324 states to 168 states and 229 transitions. [2025-02-08 14:18:10,456 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 80 [2025-02-08 14:18:10,456 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 89 [2025-02-08 14:18:10,457 INFO L73 IsDeterministic]: Start isDeterministic. Operand 168 states and 229 transitions. [2025-02-08 14:18:10,457 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-08 14:18:10,457 INFO L218 hiAutomatonCegarLoop]: Abstraction has 168 states and 229 transitions. [2025-02-08 14:18:10,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states and 229 transitions. [2025-02-08 14:18:10,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 139. [2025-02-08 14:18:10,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 85 states have (on average 1.0823529411764705) internal successors, (92), 87 states have internal predecessors, (92), 32 states have call successors, (42), 26 states have call predecessors, (42), 22 states have return successors, (43), 25 states have call predecessors, (43), 28 states have call successors, (43) [2025-02-08 14:18:10,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 177 transitions. [2025-02-08 14:18:10,472 INFO L240 hiAutomatonCegarLoop]: Abstraction has 139 states and 177 transitions. [2025-02-08 14:18:10,472 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-08 14:18:10,472 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-02-08 14:18:10,473 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-02-08 14:18:10,473 INFO L87 Difference]: Start difference. First operand 139 states and 177 transitions. Second operand has 15 states, 12 states have (on average 1.75) internal successors, (21), 8 states have internal predecessors, (21), 7 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 7 states have call predecessors, (9), 4 states have call successors, (9) [2025-02-08 14:18:10,607 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-08 14:18:10,607 INFO L93 Difference]: Finished difference Result 137 states and 162 transitions. [2025-02-08 14:18:10,607 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 137 states and 162 transitions. [2025-02-08 14:18:10,611 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-02-08 14:18:10,612 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 137 states to 100 states and 120 transitions. [2025-02-08 14:18:10,614 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2025-02-08 14:18:10,614 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 72 [2025-02-08 14:18:10,614 INFO L73 IsDeterministic]: Start isDeterministic. Operand 100 states and 120 transitions. [2025-02-08 14:18:10,614 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-02-08 14:18:10,614 INFO L218 hiAutomatonCegarLoop]: Abstraction has 100 states and 120 transitions. [2025-02-08 14:18:10,615 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states and 120 transitions. [2025-02-08 14:18:10,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 96. [2025-02-08 14:18:10,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 59 states have (on average 1.0508474576271187) internal successors, (62), 60 states have internal predecessors, (62), 22 states have call successors, (29), 19 states have call predecessors, (29), 15 states have return successors, (25), 16 states have call predecessors, (25), 18 states have call successors, (25) [2025-02-08 14:18:10,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 116 transitions. [2025-02-08 14:18:10,621 INFO L240 hiAutomatonCegarLoop]: Abstraction has 96 states and 116 transitions. [2025-02-08 14:18:10,623 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-02-08 14:18:10,623 INFO L432 stractBuchiCegarLoop]: Abstraction has 96 states and 116 transitions. [2025-02-08 14:18:10,623 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-02-08 14:18:10,624 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 116 transitions. [2025-02-08 14:18:10,624 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-02-08 14:18:10,624 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-02-08 14:18:10,624 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-02-08 14:18:10,625 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1] [2025-02-08 14:18:10,625 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-02-08 14:18:10,626 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~nondet2#1, main_#t~ret3#1, main_~x~0#1;havoc main_#t~nondet2#1;main_~x~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;" "call main_#t~ret3#1 := mc91(main_~x~0#1);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#14#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-02-08 14:18:10,626 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-02-08 14:18:10,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:10,626 INFO L85 PathProgramCache]: Analyzing trace with hash -1752895173, now seen corresponding path program 3 times [2025-02-08 14:18:10,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:10,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [229693026] [2025-02-08 14:18:10,626 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-08 14:18:10,627 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:10,632 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 37 statements into 7 equivalence classes. [2025-02-08 14:18:10,637 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 37 of 37 statements. [2025-02-08 14:18:10,640 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-02-08 14:18:10,640 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:10,640 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:10,641 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-08 14:18:10,645 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-08 14:18:10,648 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:10,648 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:10,654 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:10,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:10,654 INFO L85 PathProgramCache]: Analyzing trace with hash -59090243, now seen corresponding path program 2 times [2025-02-08 14:18:10,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:10,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [207716725] [2025-02-08 14:18:10,654 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-08 14:18:10,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:10,655 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-02-08 14:18:10,657 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:10,657 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-08 14:18:10,657 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:10,657 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:10,657 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:10,661 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:10,661 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:10,661 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:10,662 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:10,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:10,662 INFO L85 PathProgramCache]: Analyzing trace with hash -738233865, now seen corresponding path program 4 times [2025-02-08 14:18:10,662 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-08 14:18:10,662 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2147272947] [2025-02-08 14:18:10,662 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-02-08 14:18:10,662 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-08 14:18:10,668 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 45 statements into 2 equivalence classes. [2025-02-08 14:18:10,671 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 45 of 45 statements. [2025-02-08 14:18:10,671 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-02-08 14:18:10,671 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:10,671 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-08 14:18:10,672 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-08 14:18:10,679 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-08 14:18:10,682 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:10,682 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-08 14:18:10,684 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-08 14:18:10,741 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:10,741 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:10,741 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:10,741 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:10,741 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-02-08 14:18:10,741 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,741 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:10,741 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:10,741 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-02-08 14:18:10,741 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:10,742 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:10,742 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,743 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,745 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,749 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,751 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,769 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:10,769 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-02-08 14:18:10,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,770 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,775 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,775 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2025-02-08 14:18:10,776 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:10,776 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:10,789 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-08 14:18:10,789 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#t~ret0=0} Honda state: {mc91_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-08 14:18:10,797 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:10,797 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,799 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,800 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2025-02-08 14:18:10,801 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:10,801 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:10,811 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-02-08 14:18:10,812 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-02-08 14:18:10,817 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:10,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,819 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,820 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2025-02-08 14:18:10,822 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-02-08 14:18:10,822 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:10,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:10,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,839 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,841 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-02-08 14:18:10,842 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-02-08 14:18:10,842 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-02-08 14:18:10,853 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-02-08 14:18:10,858 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:10,859 INFO L204 LassoAnalysis]: Preferences: [2025-02-08 14:18:10,859 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-02-08 14:18:10,859 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-02-08 14:18:10,859 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-02-08 14:18:10,859 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-02-08 14:18:10,859 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,859 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-02-08 14:18:10,859 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-02-08 14:18:10,859 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-02-08 14:18:10,859 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-02-08 14:18:10,859 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-02-08 14:18:10,860 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,861 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,863 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,868 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,870 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-02-08 14:18:10,889 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-02-08 14:18:10,889 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-02-08 14:18:10,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,891 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,892 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,894 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-02-08 14:18:10,895 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-02-08 14:18:10,905 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:10,905 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:10,905 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:10,905 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:10,905 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:10,906 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:10,906 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:10,907 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-08 14:18:10,913 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:10,913 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,913 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,916 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,917 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2025-02-08 14:18:10,918 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-02-08 14:18:10,928 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:10,928 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:10,928 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:10,928 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:10,928 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:10,929 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:10,929 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:10,930 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-02-08 14:18:10,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2025-02-08 14:18:10,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,940 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,941 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2025-02-08 14:18:10,943 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-02-08 14:18:10,953 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-02-08 14:18:10,953 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-02-08 14:18:10,953 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-02-08 14:18:10,953 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-02-08 14:18:10,953 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-02-08 14:18:10,954 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-02-08 14:18:10,954 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-02-08 14:18:10,956 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-02-08 14:18:10,957 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-02-08 14:18:10,957 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-02-08 14:18:10,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-02-08 14:18:10,957 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-08 14:18:10,959 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-02-08 14:18:10,961 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2025-02-08 14:18:10,961 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-02-08 14:18:10,962 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-02-08 14:18:10,962 INFO L474 LassoAnalysis]: Proved termination. [2025-02-08 14:18:10,962 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 201 Supporting invariants [] [2025-02-08 14:18:10,968 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2025-02-08 14:18:10,969 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-02-08 14:18:10,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:11,012 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2025-02-08 14:18:11,025 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-08 14:18:11,071 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-08 14:18:11,071 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:11,071 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:11,072 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 14:18:11,073 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:11,308 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:11,318 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:11,318 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:11,318 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:11,319 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-02-08 14:18:11,319 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:11,410 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:11,410 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-02-08 14:18:11,411 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:11,496 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 106 states and 126 transitions. Complement of second has 16 states. [2025-02-08 14:18:11,498 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-02-08 14:18:11,498 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:11,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 14 transitions. [2025-02-08 14:18:11,499 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 14 transitions. Stem has 37 letters. Loop has 8 letters. [2025-02-08 14:18:11,499 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:11,499 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:11,507 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:11,518 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-08 14:18:11,542 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-08 14:18:11,542 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:11,542 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:11,544 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 14:18:11,545 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:11,692 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:11,698 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:11,698 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:11,698 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:11,698 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-02-08 14:18:11,699 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:11,757 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:11,758 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2025-02-08 14:18:11,758 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:11,908 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 124 states and 145 transitions. Complement of second has 28 states. [2025-02-08 14:18:11,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2025-02-08 14:18:11,909 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:11,910 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 19 transitions. [2025-02-08 14:18:11,910 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 19 transitions. Stem has 37 letters. Loop has 8 letters. [2025-02-08 14:18:11,910 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:11,910 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:11,918 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:11,934 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-08 14:18:11,957 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-08 14:18:11,957 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:11,957 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:11,958 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 14:18:11,959 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:12,088 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:12,094 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:12,094 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:12,094 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:12,094 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-02-08 14:18:12,095 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:12,151 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:12,151 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-02-08 14:18:12,151 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:12,220 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 146 states and 166 transitions. Complement of second has 17 states. [2025-02-08 14:18:12,224 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-02-08 14:18:12,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:12,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2025-02-08 14:18:12,224 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 37 letters. Loop has 8 letters. [2025-02-08 14:18:12,225 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:12,225 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-02-08 14:18:12,234 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-08 14:18:12,261 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-08 14:18:12,313 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-08 14:18:12,313 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:12,313 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:12,314 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-02-08 14:18:12,315 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:12,476 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-02-08 14:18:12,482 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-02-08 14:18:12,482 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-08 14:18:12,482 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-08 14:18:12,482 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-02-08 14:18:12,484 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-08 14:18:12,558 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-08 14:18:12,561 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2025-02-08 14:18:12,561 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:12,775 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 116 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 181 states and 208 transitions. Complement of second has 51 states. [2025-02-08 14:18:12,778 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 12 states 2 stem states 9 non-accepting loop states 1 accepting loop states [2025-02-08 14:18:12,779 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-02-08 14:18:12,779 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 26 transitions. [2025-02-08 14:18:12,779 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 26 transitions. Stem has 37 letters. Loop has 8 letters. [2025-02-08 14:18:12,779 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:12,779 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 26 transitions. Stem has 45 letters. Loop has 8 letters. [2025-02-08 14:18:12,779 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:12,779 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 26 transitions. Stem has 37 letters. Loop has 16 letters. [2025-02-08 14:18:12,780 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-02-08 14:18:12,780 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 181 states and 208 transitions. [2025-02-08 14:18:12,781 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-02-08 14:18:12,782 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 181 states to 0 states and 0 transitions. [2025-02-08 14:18:12,782 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-02-08 14:18:12,782 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-02-08 14:18:12,782 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-02-08 14:18:12,782 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-02-08 14:18:12,782 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-08 14:18:12,782 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-08 14:18:12,782 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-08 14:18:12,782 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-02-08 14:18:12,782 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-02-08 14:18:12,782 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-02-08 14:18:12,782 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-02-08 14:18:12,794 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 08.02 02:18:12 BoogieIcfgContainer [2025-02-08 14:18:12,795 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-02-08 14:18:12,795 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-02-08 14:18:12,795 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-02-08 14:18:12,795 INFO L274 PluginConnector]: Witness Printer initialized [2025-02-08 14:18:12,796 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.02 02:18:04" (3/4) ... [2025-02-08 14:18:12,797 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-02-08 14:18:12,801 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-02-08 14:18:12,801 INFO L158 Benchmark]: Toolchain (without parser) took 8903.12ms. Allocated memory is still 142.6MB. Free memory was 115.5MB in the beginning and 52.5MB in the end (delta: 63.0MB). Peak memory consumption was 64.3MB. Max. memory is 16.1GB. [2025-02-08 14:18:12,801 INFO L158 Benchmark]: CDTParser took 0.23ms. Allocated memory is still 201.3MB. Free memory is still 124.6MB. There was no memory consumed. Max. memory is 16.1GB. [2025-02-08 14:18:12,802 INFO L158 Benchmark]: CACSL2BoogieTranslator took 117.91ms. Allocated memory is still 142.6MB. Free memory was 115.5MB in the beginning and 106.3MB in the end (delta: 9.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-08 14:18:12,802 INFO L158 Benchmark]: Boogie Procedure Inliner took 15.21ms. Allocated memory is still 142.6MB. Free memory was 105.6MB in the beginning and 104.8MB in the end (delta: 734.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-08 14:18:12,802 INFO L158 Benchmark]: Boogie Preprocessor took 11.90ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 104.1MB in the end (delta: 720.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-08 14:18:12,802 INFO L158 Benchmark]: IcfgBuilder took 171.40ms. Allocated memory is still 142.6MB. Free memory was 104.1MB in the beginning and 93.8MB in the end (delta: 10.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-08 14:18:12,802 INFO L158 Benchmark]: BuchiAutomizer took 8575.81ms. Allocated memory is still 142.6MB. Free memory was 93.8MB in the beginning and 52.6MB in the end (delta: 41.2MB). Peak memory consumption was 47.5MB. Max. memory is 16.1GB. [2025-02-08 14:18:12,802 INFO L158 Benchmark]: Witness Printer took 5.74ms. Allocated memory is still 142.6MB. Free memory was 52.6MB in the beginning and 52.5MB in the end (delta: 41.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-08 14:18:12,803 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.23ms. Allocated memory is still 201.3MB. Free memory is still 124.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 117.91ms. Allocated memory is still 142.6MB. Free memory was 115.5MB in the beginning and 106.3MB in the end (delta: 9.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 15.21ms. Allocated memory is still 142.6MB. Free memory was 105.6MB in the beginning and 104.8MB in the end (delta: 734.6kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 11.90ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 104.1MB in the end (delta: 720.6kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 171.40ms. Allocated memory is still 142.6MB. Free memory was 104.1MB in the beginning and 93.8MB in the end (delta: 10.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 8575.81ms. Allocated memory is still 142.6MB. Free memory was 93.8MB in the beginning and 52.6MB in the end (delta: 41.2MB). Peak memory consumption was 47.5MB. Max. memory is 16.1GB. * Witness Printer took 5.74ms. Allocated memory is still 142.6MB. Free memory was 52.6MB in the beginning and 52.5MB in the end (delta: 41.6kB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret0 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 7 terminating modules (2 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function (211 + ((long) -2 * \old(n))) and consists of 5 locations. One deterministic module has affine ranking function null and consists of 8 locations. One nondeterministic module has affine ranking function (((long) -2 * n) + 189) and consists of 6 locations. One nondeterministic module has affine ranking function (90 + ((long) -1 * \old(n))) and consists of 19 locations. One nondeterministic module has affine ranking function (((long) -2 * \old(n)) + 201) and consists of 12 locations. 2 modules have a trivial ranking function, the largest among these consists of 15 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.5s and 6 iterations. TraceHistogramMax:8. Analysis of lassos took 3.2s. Construction of modules took 0.6s. Büchi inclusion checks took 4.5s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.0s AutomataMinimizationTime, 6 MinimizatonAttempts, 48 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 1, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 10/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 252 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 238 mSDsluCounter, 397 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 225 mSDsCounter, 210 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 930 IncrementalHoareTripleChecker+Invalid, 1140 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 210 mSolverCounterUnsat, 172 mSDtfsCounter, 930 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT3 conc0 concLT2 SILN0 SILU0 SILI0 SILT0 lasso0 LassoPreprocessingBenchmarks: Lassos: inital12 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq171 hnf91 smp100 dnf100 smp100 tf110 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: sat Degree: 0 Time: 53ms VariablesStem: 0 VariablesLoop: 2 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.1s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-02-08 14:18:12,814 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-02-08 14:18:13,019 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/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