./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 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-17 19:50:19,035 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 19:50:19,089 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2025-03-17 19:50:19,096 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 19:50:19,096 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 19:50:19,096 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-17 19:50:19,111 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 19:50:19,111 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 19:50:19,111 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 19:50:19,111 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 19:50:19,112 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 19:50:19,112 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-17 19:50:19,112 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-17 19:50:19,112 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 19:50:19,113 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 19:50:19,113 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 19:50:19,113 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-17 19:50:19,113 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 [2025-03-17 19:50:19,346 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 19:50:19,355 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 19:50:19,358 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 19:50:19,359 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 19:50:19,359 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 19:50:19,360 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-03-17 19:50:20,481 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8bd8196f8/27e0a2ac63db4d00a7db89a2523e8c5a/FLAGc05dd5981 [2025-03-17 19:50:20,704 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 19:50:20,705 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-03-17 19:50:20,710 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8bd8196f8/27e0a2ac63db4d00a7db89a2523e8c5a/FLAGc05dd5981 [2025-03-17 19:50:20,723 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8bd8196f8/27e0a2ac63db4d00a7db89a2523e8c5a [2025-03-17 19:50:20,726 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 19:50:20,738 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 19:50:20,739 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 19:50:20,740 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 19:50:20,744 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 19:50:20,745 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,747 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5f2603c2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20, skipping insertion in model container [2025-03-17 19:50:20,748 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,761 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 19:50:20,858 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 19:50:20,861 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 19:50:20,870 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 19:50:20,883 INFO L204 MainTranslator]: Completed translation [2025-03-17 19:50:20,884 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20 WrapperNode [2025-03-17 19:50:20,884 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 19:50:20,885 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 19:50:20,886 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 19:50:20,886 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 19:50:20,892 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,895 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,905 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2025-03-17 19:50:20,906 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 19:50:20,907 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 19:50:20,907 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 19:50:20,907 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 19:50:20,913 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,914 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,914 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,919 INFO L175 MemorySlicer]: No memory access in input program. [2025-03-17 19:50:20,920 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,920 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,922 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,922 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,923 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,924 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,925 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 19:50:20,926 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 19:50:20,927 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 19:50:20,927 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 19:50:20,928 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (1/1) ... [2025-03-17 19:50:20,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:20,946 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:20,961 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:20,966 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2025-03-17 19:50:20,991 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 19:50:20,992 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 19:50:20,992 INFO L130 BoogieDeclarations]: Found specification of procedure mc91 [2025-03-17 19:50:20,992 INFO L138 BoogieDeclarations]: Found implementation of procedure mc91 [2025-03-17 19:50:21,025 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 19:50:21,026 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 19:50:21,122 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2025-03-17 19:50:21,122 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 19:50:21,131 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 19:50:21,132 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 19:50:21,132 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:50:21 BoogieIcfgContainer [2025-03-17 19:50:21,132 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 19:50:21,133 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-17 19:50:21,133 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-17 19:50:21,138 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-17 19:50:21,139 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 19:50:21,139 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.03 07:50:20" (1/3) ... [2025-03-17 19:50:21,139 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@421f16bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 07:50:21, skipping insertion in model container [2025-03-17 19:50:21,140 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 19:50:21,140 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 07:50:20" (2/3) ... [2025-03-17 19:50:21,140 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@421f16bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 07:50:21, skipping insertion in model container [2025-03-17 19:50:21,140 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 19:50:21,140 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:50:21" (3/3) ... [2025-03-17 19:50:21,141 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91_Recursion.c [2025-03-17 19:50:21,181 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-17 19:50:21,182 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-17 19:50:21,183 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-17 19:50:21,183 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-17 19:50:21,183 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-17 19:50:21,183 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-17 19:50:21,183 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-17 19:50:21,183 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-17 19:50:21,187 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-03-17 19:50:21,199 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 19:50:21,199 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:21,200 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:21,203 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 19:50:21,204 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:21,204 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-17 19:50:21,204 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-03-17 19:50:21,205 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 19:50:21,205 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:21,206 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:21,206 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 19:50:21,206 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:21,211 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-03-17 19:50:21,211 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< [2025-03-17 19:50:21,214 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:21,215 INFO L85 PathProgramCache]: Analyzing trace with hash 1034, now seen corresponding path program 1 times [2025-03-17 19:50:21,220 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:21,220 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [163377775] [2025-03-17 19:50:21,220 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:21,221 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:21,263 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:21,266 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:21,269 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,269 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,270 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:21,271 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:21,272 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:21,274 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,274 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,285 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:21,287 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:21,288 INFO L85 PathProgramCache]: Analyzing trace with hash 38703, now seen corresponding path program 1 times [2025-03-17 19:50:21,288 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:21,288 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2034231280] [2025-03-17 19:50:21,288 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:21,288 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:21,292 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:21,299 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:21,300 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,300 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,300 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:21,305 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:21,306 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:21,306 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,306 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,307 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:21,311 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:21,311 INFO L85 PathProgramCache]: Analyzing trace with hash 30812806, now seen corresponding path program 1 times [2025-03-17 19:50:21,311 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:21,311 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1475202103] [2025-03-17 19:50:21,311 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:21,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:21,314 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-03-17 19:50:21,319 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-03-17 19:50:21,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,319 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:21,320 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-03-17 19:50:21,321 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-03-17 19:50:21,321 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,321 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,325 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:21,399 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:21,400 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:21,400 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:21,401 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:21,401 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:21,401 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:21,401 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:21,401 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:21,402 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-03-17 19:50:21,402 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:21,402 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:21,414 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,435 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,438 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,441 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,444 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,496 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:21,497 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:21,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:21,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:21,502 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:21,508 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2025-03-17 19:50:21,508 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:21,509 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:21,533 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2025-03-17 19:50:21,534 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:21,534 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:21,537 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:21,538 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2025-03-17 19:50:21,538 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:21,538 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:21,566 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:21,570 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2025-03-17 19:50:21,571 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:21,571 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:21,571 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:21,571 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:21,571 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:21,571 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:21,571 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:21,571 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:21,571 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-03-17 19:50:21,571 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:21,571 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:21,572 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,580 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,583 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,586 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,589 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:21,615 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:21,618 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:21,619 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:21,619 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:21,621 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:21,622 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2025-03-17 19:50:21,624 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:21,635 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:21,635 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:21,636 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:21,636 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:21,636 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:21,643 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:21,643 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:21,647 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:21,651 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 19:50:21,654 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:21,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:21,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:21,660 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:21,661 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2025-03-17 19:50:21,662 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:21,662 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:21,663 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:21,663 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 211 Supporting invariants [] [2025-03-17 19:50:21,669 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2025-03-17 19:50:21,673 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:21,703 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:21,718 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 19:50:21,729 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 19:50:21,730 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,730 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:21,732 INFO L256 TraceCheckSpWp]: Trace formula consists of 35 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-17 19:50:21,733 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:21,742 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:21,751 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:21,751 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,751 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:21,752 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:21,753 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:21,811 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:21,832 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2025-03-17 19:50:21,833 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-03-17 19:50:21,936 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-03-17 19:50:21,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-17 19:50:21,942 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-03-17 19:50:21,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 7 transitions. [2025-03-17 19:50:21,948 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 3 letters. [2025-03-17 19:50:21,949 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:21,949 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 5 letters. Loop has 3 letters. [2025-03-17 19:50:21,949 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:21,949 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 6 letters. [2025-03-17 19:50:21,950 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:21,950 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 30 states and 37 transitions. [2025-03-17 19:50:21,952 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 19:50:21,956 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 30 states to 18 states and 24 transitions. [2025-03-17 19:50:21,957 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2025-03-17 19:50:21,957 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 13 [2025-03-17 19:50:21,958 INFO L73 IsDeterministic]: Start isDeterministic. Operand 18 states and 24 transitions. [2025-03-17 19:50:21,958 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:21,958 INFO L218 hiAutomatonCegarLoop]: Abstraction has 18 states and 24 transitions. [2025-03-17 19:50:21,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states and 24 transitions. [2025-03-17 19:50:21,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 16. [2025-03-17 19:50:21,975 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-03-17 19:50:21,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 20 transitions. [2025-03-17 19:50:21,977 INFO L240 hiAutomatonCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-03-17 19:50:21,977 INFO L432 stractBuchiCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-03-17 19:50:21,977 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-17 19:50:21,977 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 16 states and 20 transitions. [2025-03-17 19:50:21,978 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 19:50:21,978 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:21,978 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:21,979 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:21,979 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:21,979 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-03-17 19:50:21,979 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-03-17 19:50:21,980 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:21,980 INFO L85 PathProgramCache]: Analyzing trace with hash 2115346215, now seen corresponding path program 1 times [2025-03-17 19:50:21,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:21,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1400407650] [2025-03-17 19:50:21,980 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:21,980 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:21,983 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 19:50:21,987 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 19:50:21,987 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,987 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,987 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:21,989 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 19:50:21,992 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 19:50:21,992 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:21,992 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:21,993 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:21,994 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:21,994 INFO L85 PathProgramCache]: Analyzing trace with hash -984999739, now seen corresponding path program 1 times [2025-03-17 19:50:21,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:21,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1548626747] [2025-03-17 19:50:21,995 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:21,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:22,000 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:22,005 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:22,005 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:22,005 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:22,005 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:22,006 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:22,009 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:22,009 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:22,009 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:22,011 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:22,012 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:22,012 INFO L85 PathProgramCache]: Analyzing trace with hash -512151061, now seen corresponding path program 1 times [2025-03-17 19:50:22,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:22,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [307330549] [2025-03-17 19:50:22,013 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:22,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:22,018 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-17 19:50:22,026 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-17 19:50:22,027 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:22,027 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:22,027 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:22,029 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-17 19:50:22,035 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-17 19:50:22,035 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:22,035 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:22,040 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:22,164 ERROR L418 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Exception during sending of exit command (exit): Broken pipe [2025-03-17 19:50:22,169 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:22,181 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:22,181 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:22,181 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:22,181 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:22,181 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:22,181 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,181 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:22,181 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:22,181 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-03-17 19:50:22,181 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:22,181 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:22,182 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:22,184 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:22,186 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:22,238 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:22,238 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:22,238 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,238 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:22,244 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:22,245 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2025-03-17 19:50:22,246 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:22,246 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:22,258 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:22,258 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-03-17 19:50:22,264 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2025-03-17 19:50:22,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:22,266 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:22,267 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-03-17 19:50:22,268 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:22,268 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:22,281 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:22,281 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:22,286 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-03-17 19:50:22,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:22,288 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:22,289 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2025-03-17 19:50:22,290 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:22,290 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:22,329 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2025-03-17 19:50:22,329 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:22,332 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:22,333 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2025-03-17 19:50:22,334 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:22,334 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:22,886 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:22,901 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2025-03-17 19:50:22,901 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:22,901 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:22,901 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:22,901 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:22,901 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:22,901 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,901 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:22,901 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:22,902 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-03-17 19:50:22,902 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:22,902 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:22,903 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:22,909 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:22,920 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:22,963 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:22,963 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:22,963 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:22,967 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:22,968 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2025-03-17 19:50:22,969 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:22,980 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:22,980 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:22,981 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:22,981 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:22,981 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:22,981 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:22,982 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:22,987 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:22,994 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2025-03-17 19:50:22,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:22,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:22,997 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:22,997 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2025-03-17 19:50:22,998 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:23,008 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:23,008 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:23,008 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:23,009 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:23,009 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:23,010 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:23,010 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:23,013 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:23,015 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 19:50:23,015 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:23,015 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:23,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:23,017 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:23,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-03-17 19:50:23,023 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:23,023 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:23,023 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:23,023 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2025-03-17 19:50:23,031 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:23,034 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:23,040 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2025-03-17 19:50:23,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:23,059 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 19:50:23,076 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 19:50:23,076 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:23,076 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:23,077 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-17 19:50:23,078 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:23,154 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:23,170 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:23,170 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:23,170 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:23,171 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 19:50:23,172 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:23,272 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:23,272 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-03-17 19:50:23,273 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-03-17 19:50:23,425 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-03-17 19:50:23,427 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-03-17 19:50:23,427 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-03-17 19:50:23,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 19:50:23,428 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 8 letters. [2025-03-17 19:50:23,429 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:23,429 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 17 letters. Loop has 8 letters. [2025-03-17 19:50:23,429 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:23,429 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 16 letters. [2025-03-17 19:50:23,429 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:23,429 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 50 states and 72 transitions. [2025-03-17 19:50:23,431 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-17 19:50:23,432 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 50 states to 41 states and 61 transitions. [2025-03-17 19:50:23,432 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-03-17 19:50:23,433 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 26 [2025-03-17 19:50:23,433 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 61 transitions. [2025-03-17 19:50:23,433 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:23,433 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 61 transitions. [2025-03-17 19:50:23,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 61 transitions. [2025-03-17 19:50:23,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 35. [2025-03-17 19:50:23,437 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-03-17 19:50:23,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 50 transitions. [2025-03-17 19:50:23,437 INFO L240 hiAutomatonCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-03-17 19:50:23,437 INFO L432 stractBuchiCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-03-17 19:50:23,438 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-17 19:50:23,438 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 35 states and 50 transitions. [2025-03-17 19:50:23,438 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-17 19:50:23,438 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:23,438 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:23,439 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:23,439 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 19:50:23,439 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-03-17 19:50:23,439 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" [2025-03-17 19:50:23,439 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:23,439 INFO L85 PathProgramCache]: Analyzing trace with hash -1776030363, now seen corresponding path program 2 times [2025-03-17 19:50:23,439 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:23,439 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1657946636] [2025-03-17 19:50:23,439 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:23,439 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:23,446 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 12 statements into 2 equivalence classes. [2025-03-17 19:50:23,453 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 19:50:23,453 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:23,453 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:23,454 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:23,455 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 19:50:23,457 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 19:50:23,457 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:23,457 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:23,458 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:23,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:23,458 INFO L85 PathProgramCache]: Analyzing trace with hash 44493, now seen corresponding path program 2 times [2025-03-17 19:50:23,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:23,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117929331] [2025-03-17 19:50:23,458 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:23,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:23,460 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:23,462 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:23,462 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-17 19:50:23,462 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:23,462 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:23,464 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:23,465 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:23,466 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:23,466 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:23,467 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:23,468 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:23,468 INFO L85 PathProgramCache]: Analyzing trace with hash -18410007, now seen corresponding path program 3 times [2025-03-17 19:50:23,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:23,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [82180018] [2025-03-17 19:50:23,468 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 19:50:23,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:23,471 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 15 statements into 4 equivalence classes. [2025-03-17 19:50:23,477 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 15 of 15 statements. [2025-03-17 19:50:23,479 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-17 19:50:23,479 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:23,612 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-17 19:50:23,613 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:23,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [82180018] [2025-03-17 19:50:23,613 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [82180018] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 19:50:23,613 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 19:50:23,613 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-17 19:50:23,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1081711346] [2025-03-17 19:50:23,614 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 19:50:23,662 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:23,662 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:23,662 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:23,662 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:23,663 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:23,663 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:23,663 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:23,663 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:23,663 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-03-17 19:50:23,663 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:23,663 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:23,663 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:23,672 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:23,677 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:23,684 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:23,709 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:23,709 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:23,709 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:23,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:23,711 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:23,713 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2025-03-17 19:50:23,714 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:23,714 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:23,741 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:23,741 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:23,741 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:23,767 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:23,769 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2025-03-17 19:50:23,769 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:23,769 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:24,097 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:24,108 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2025-03-17 19:50:24,108 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:24,109 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:24,109 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:24,109 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:24,109 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:24,109 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:24,109 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:24,109 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:24,109 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-03-17 19:50:24,109 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:24,109 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:24,110 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:24,119 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:24,122 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:24,124 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:24,148 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:24,148 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:24,148 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:24,148 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:24,150 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:24,153 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2025-03-17 19:50:24,153 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:24,164 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:24,164 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:24,165 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:24,165 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:24,165 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:24,165 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:24,165 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:24,167 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:24,169 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 19:50:24,169 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:24,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:24,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:24,171 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:24,173 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2025-03-17 19:50:24,173 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:24,173 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:24,173 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:24,173 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_~n) = -2*mc91_~n + 189 Supporting invariants [] [2025-03-17 19:50:24,179 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:24,180 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:24,202 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:24,208 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2025-03-17 19:50:24,212 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:24,218 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 19:50:24,229 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 19:50:24,229 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,229 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,230 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 19:50:24,231 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:24,278 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:24,282 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:24,282 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,282 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,283 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:24,283 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:24,304 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:24,305 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-17 19:50:24,305 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-03-17 19:50:24,361 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-03-17 19:50:24,361 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-17 19:50:24,361 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-03-17 19:50:24,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 19:50:24,362 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 19:50:24,362 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:24,362 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:24,370 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:24,375 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 19:50:24,387 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 19:50:24,387 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,387 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,387 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 19:50:24,388 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:24,446 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:24,451 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:24,451 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,451 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,452 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:24,452 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:24,473 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:24,473 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-17 19:50:24,474 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-03-17 19:50:24,523 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-03-17 19:50:24,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-17 19:50:24,525 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-03-17 19:50:24,525 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 19:50:24,526 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 19:50:24,526 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:24,526 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:24,535 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:24,542 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 19:50:24,552 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 19:50:24,552 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,552 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,553 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 19:50:24,553 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:24,605 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 19:50:24,608 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 19:50:24,608 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,608 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,608 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 19:50:24,609 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:24,632 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:24,632 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-17 19:50:24,632 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-03-17 19:50:24,697 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-03-17 19:50:24,701 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-17 19:50:24,701 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-03-17 19:50:24,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2025-03-17 19:50:24,702 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 19:50:24,702 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:24,702 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 15 letters. Loop has 3 letters. [2025-03-17 19:50:24,702 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:24,702 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 6 letters. [2025-03-17 19:50:24,702 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:24,702 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 70 states and 99 transitions. [2025-03-17 19:50:24,704 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-03-17 19:50:24,708 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 70 states to 47 states and 73 transitions. [2025-03-17 19:50:24,709 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-03-17 19:50:24,709 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-03-17 19:50:24,709 INFO L73 IsDeterministic]: Start isDeterministic. Operand 47 states and 73 transitions. [2025-03-17 19:50:24,710 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:24,710 INFO L218 hiAutomatonCegarLoop]: Abstraction has 47 states and 73 transitions. [2025-03-17 19:50:24,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states and 73 transitions. [2025-03-17 19:50:24,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 41. [2025-03-17 19:50:24,713 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-03-17 19:50:24,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 59 transitions. [2025-03-17 19:50:24,714 INFO L240 hiAutomatonCegarLoop]: Abstraction has 41 states and 59 transitions. [2025-03-17 19:50:24,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:24,715 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-17 19:50:24,715 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-17 19:50:24,716 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-03-17 19:50:24,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:24,793 INFO L93 Difference]: Finished difference Result 62 states and 81 transitions. [2025-03-17 19:50:24,793 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 62 states and 81 transitions. [2025-03-17 19:50:24,795 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 19:50:24,796 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 62 states to 57 states and 74 transitions. [2025-03-17 19:50:24,796 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2025-03-17 19:50:24,796 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 41 [2025-03-17 19:50:24,796 INFO L73 IsDeterministic]: Start isDeterministic. Operand 57 states and 74 transitions. [2025-03-17 19:50:24,796 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:24,796 INFO L218 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-17 19:50:24,797 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states and 74 transitions. [2025-03-17 19:50:24,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2025-03-17 19:50:24,799 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-03-17 19:50:24,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2025-03-17 19:50:24,800 INFO L240 hiAutomatonCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-03-17 19:50:24,800 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-17 19:50:24,801 INFO L432 stractBuchiCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-03-17 19:50:24,801 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-17 19:50:24,801 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 56 states and 73 transitions. [2025-03-17 19:50:24,802 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 19:50:24,802 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:24,802 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:24,802 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2025-03-17 19:50:24,802 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-03-17 19:50:24,803 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-03-17 19:50:24,803 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-03-17 19:50:24,803 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:24,803 INFO L85 PathProgramCache]: Analyzing trace with hash 1357151171, now seen corresponding path program 1 times [2025-03-17 19:50:24,803 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:24,803 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [613405216] [2025-03-17 19:50:24,803 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:24,803 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:24,805 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 19:50:24,809 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 19:50:24,809 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,809 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:24,809 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:24,810 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 19:50:24,813 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 19:50:24,813 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,813 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:24,815 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:24,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:24,816 INFO L85 PathProgramCache]: Analyzing trace with hash -1529186708, now seen corresponding path program 1 times [2025-03-17 19:50:24,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:24,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2000293330] [2025-03-17 19:50:24,816 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 19:50:24,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:24,818 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 19:50:24,823 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 19:50:24,823 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,823 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:24,823 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:24,824 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 19:50:24,831 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 19:50:24,831 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:24,831 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:24,834 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:24,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:24,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1944416406, now seen corresponding path program 2 times [2025-03-17 19:50:24,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:24,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1517679414] [2025-03-17 19:50:24,835 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:24,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:24,840 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-17 19:50:24,849 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-17 19:50:24,852 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:24,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:24,966 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-17 19:50:24,966 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 19:50:24,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1517679414] [2025-03-17 19:50:24,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1517679414] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 19:50:24,967 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1499541228] [2025-03-17 19:50:24,967 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:24,967 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 19:50:24,967 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:24,969 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 19:50:24,971 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-17 19:50:24,993 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-17 19:50:25,013 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-17 19:50:25,013 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:25,013 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:25,014 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 19:50:25,015 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:25,047 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-17 19:50:25,047 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 19:50:25,237 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-17 19:50:25,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1499541228] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 19:50:25,238 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 19:50:25,238 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-03-17 19:50:25,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2091073113] [2025-03-17 19:50:25,238 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 19:50:25,385 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:25,386 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:25,386 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:25,386 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:25,386 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:25,386 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:25,386 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:25,386 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:25,386 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-03-17 19:50:25,386 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:25,386 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:25,387 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,390 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,392 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,393 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,394 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,416 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:25,416 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:25,416 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:25,416 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:25,421 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:25,423 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-03-17 19:50:25,423 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:25,423 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:25,449 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-03-17 19:50:25,449 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:25,450 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:25,452 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:25,453 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2025-03-17 19:50:25,455 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:25,455 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:25,470 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:25,477 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:25,478 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:25,478 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:25,478 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:25,478 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:25,478 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:25,478 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:25,478 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:25,478 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:25,478 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-03-17 19:50:25,478 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:25,478 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:25,479 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,487 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,488 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,490 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,491 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:25,512 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:25,512 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:25,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:25,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:25,518 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:25,521 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2025-03-17 19:50:25,522 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:25,531 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:25,532 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:25,532 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:25,532 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:25,532 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:25,534 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:25,534 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:25,537 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:25,538 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 19:50:25,539 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:25,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:25,539 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:25,541 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:25,543 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:25,543 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:25,543 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:25,543 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -1*mc91_#in~n + 90 Supporting invariants [] [2025-03-17 19:50:25,543 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2025-03-17 19:50:25,550 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:25,551 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:25,561 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:25,574 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 19:50:25,589 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 19:50:25,589 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:25,589 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:25,590 INFO L256 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 19:50:25,591 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:25,732 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 19:50:25,749 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 19:50:25,749 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:25,749 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:25,750 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 19:50:25,751 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:25,835 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:25,925 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-17 19:50:25,926 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-03-17 19:50:25,926 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-03-17 19:50:26,240 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-03-17 19:50:26,241 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-03-17 19:50:26,242 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-03-17 19:50:26,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-03-17 19:50:26,242 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 19:50:26,242 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:26,242 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:26,250 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:26,257 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 19:50:26,277 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 19:50:26,278 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:26,278 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:26,279 INFO L256 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 19:50:26,280 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:26,404 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 19:50:26,417 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 19:50:26,417 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:26,417 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:26,418 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 19:50:26,419 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:26,595 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-17 19:50:26,596 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-03-17 19:50:26,596 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-03-17 19:50:26,868 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-03-17 19:50:26,870 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-03-17 19:50:26,870 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-03-17 19:50:26,870 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-03-17 19:50:26,871 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 19:50:26,871 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:26,871 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:26,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:26,891 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 19:50:26,907 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 19:50:26,907 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:26,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:26,908 INFO L256 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 19:50:26,909 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:27,017 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 19:50:27,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 19:50:27,029 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:27,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:27,030 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-17 19:50:27,031 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:27,151 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-17 19:50:27,152 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-03-17 19:50:27,152 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-03-17 19:50:27,595 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-03-17 19:50:27,595 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-03-17 19:50:27,596 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-03-17 19:50:27,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 49 transitions. [2025-03-17 19:50:27,596 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 49 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 19:50:27,597 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:27,597 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 49 transitions. Stem has 40 letters. Loop has 19 letters. [2025-03-17 19:50:27,597 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:27,597 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 49 transitions. Stem has 21 letters. Loop has 38 letters. [2025-03-17 19:50:27,597 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:27,597 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 324 states and 416 transitions. [2025-03-17 19:50:27,603 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 25 [2025-03-17 19:50:27,605 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 324 states to 168 states and 229 transitions. [2025-03-17 19:50:27,605 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 80 [2025-03-17 19:50:27,606 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 89 [2025-03-17 19:50:27,606 INFO L73 IsDeterministic]: Start isDeterministic. Operand 168 states and 229 transitions. [2025-03-17 19:50:27,606 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:27,606 INFO L218 hiAutomatonCegarLoop]: Abstraction has 168 states and 229 transitions. [2025-03-17 19:50:27,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states and 229 transitions. [2025-03-17 19:50:27,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 139. [2025-03-17 19:50:27,616 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-03-17 19:50:27,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 177 transitions. [2025-03-17 19:50:27,617 INFO L240 hiAutomatonCegarLoop]: Abstraction has 139 states and 177 transitions. [2025-03-17 19:50:27,617 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 19:50:27,617 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-17 19:50:27,617 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-03-17 19:50:27,617 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-03-17 19:50:27,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 19:50:27,757 INFO L93 Difference]: Finished difference Result 137 states and 162 transitions. [2025-03-17 19:50:27,757 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 137 states and 162 transitions. [2025-03-17 19:50:27,760 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 19:50:27,762 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 137 states to 100 states and 120 transitions. [2025-03-17 19:50:27,762 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2025-03-17 19:50:27,762 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 72 [2025-03-17 19:50:27,762 INFO L73 IsDeterministic]: Start isDeterministic. Operand 100 states and 120 transitions. [2025-03-17 19:50:27,762 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 19:50:27,762 INFO L218 hiAutomatonCegarLoop]: Abstraction has 100 states and 120 transitions. [2025-03-17 19:50:27,762 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states and 120 transitions. [2025-03-17 19:50:27,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 96. [2025-03-17 19:50:27,767 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-03-17 19:50:27,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 116 transitions. [2025-03-17 19:50:27,768 INFO L240 hiAutomatonCegarLoop]: Abstraction has 96 states and 116 transitions. [2025-03-17 19:50:27,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-17 19:50:27,769 INFO L432 stractBuchiCegarLoop]: Abstraction has 96 states and 116 transitions. [2025-03-17 19:50:27,769 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-17 19:50:27,770 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 116 transitions. [2025-03-17 19:50:27,772 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 19:50:27,772 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 19:50:27,772 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 19:50:27,772 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1] [2025-03-17 19:50:27,773 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-17 19:50:27,773 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-03-17 19:50:27,773 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-03-17 19:50:27,773 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:27,773 INFO L85 PathProgramCache]: Analyzing trace with hash -1752895173, now seen corresponding path program 3 times [2025-03-17 19:50:27,773 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:27,773 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [528811607] [2025-03-17 19:50:27,773 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 19:50:27,773 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:27,777 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 37 statements into 7 equivalence classes. [2025-03-17 19:50:27,784 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 37 of 37 statements. [2025-03-17 19:50:27,784 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-17 19:50:27,784 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:27,785 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:27,786 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-17 19:50:27,790 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-17 19:50:27,791 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:27,791 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:27,793 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:27,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:27,793 INFO L85 PathProgramCache]: Analyzing trace with hash -59090243, now seen corresponding path program 2 times [2025-03-17 19:50:27,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:27,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1737057767] [2025-03-17 19:50:27,793 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 19:50:27,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:27,795 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-03-17 19:50:27,796 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:27,796 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 19:50:27,796 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:27,796 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:27,796 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:27,797 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:27,797 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:27,797 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:27,801 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:27,801 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:27,801 INFO L85 PathProgramCache]: Analyzing trace with hash -738233865, now seen corresponding path program 4 times [2025-03-17 19:50:27,801 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 19:50:27,801 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1762155761] [2025-03-17 19:50:27,801 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-17 19:50:27,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 19:50:27,804 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 45 statements into 2 equivalence classes. [2025-03-17 19:50:27,814 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 45 of 45 statements. [2025-03-17 19:50:27,814 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-17 19:50:27,814 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:27,814 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 19:50:27,816 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-17 19:50:27,823 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-17 19:50:27,824 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:27,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 19:50:27,826 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 19:50:27,886 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:27,886 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:27,886 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:27,886 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:27,886 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 19:50:27,886 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:27,886 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:27,886 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:27,886 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-03-17 19:50:27,886 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:27,886 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:27,887 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:27,889 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:27,890 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:27,895 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:27,896 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:27,916 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:27,916 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 19:50:27,916 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:27,916 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:27,918 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:27,919 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2025-03-17 19:50:27,920 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:27,920 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:27,931 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:27,931 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-03-17 19:50:27,936 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2025-03-17 19:50:27,936 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:27,936 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:27,938 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:27,938 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2025-03-17 19:50:27,939 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:27,939 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:27,949 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 19:50:27,950 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 19:50:27,955 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2025-03-17 19:50:27,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:27,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:27,957 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:27,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2025-03-17 19:50:27,958 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 19:50:27,958 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:27,974 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2025-03-17 19:50:27,974 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:27,974 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:27,976 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:27,977 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-03-17 19:50:27,978 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 19:50:27,978 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 19:50:27,994 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 19:50:27,999 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:28,000 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 19:50:28,000 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 19:50:28,000 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 19:50:28,000 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 19:50:28,000 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 19:50:28,000 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:28,000 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 19:50:28,000 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 19:50:28,000 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-03-17 19:50:28,000 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 19:50:28,000 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 19:50:28,000 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:28,002 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:28,003 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:28,007 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:28,008 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 19:50:28,025 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 19:50:28,026 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 19:50:28,026 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:28,026 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:28,027 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:28,028 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-03-17 19:50:28,029 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:28,039 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:28,039 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:28,039 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:28,039 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:28,039 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:28,040 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:28,040 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:28,040 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:28,045 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2025-03-17 19:50:28,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:28,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:28,047 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:28,049 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2025-03-17 19:50:28,050 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:28,059 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:28,060 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:28,060 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:28,060 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:28,060 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:28,060 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:28,060 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:28,061 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 19:50:28,066 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:28,067 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:28,067 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:28,069 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:28,070 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2025-03-17 19:50:28,071 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 19:50:28,081 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 19:50:28,081 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 19:50:28,081 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 19:50:28,081 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 19:50:28,081 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 19:50:28,082 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 19:50:28,082 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 19:50:28,083 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 19:50:28,086 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 19:50:28,086 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 19:50:28,086 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 19:50:28,086 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 19:50:28,088 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 19:50:28,089 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2025-03-17 19:50:28,090 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 19:50:28,090 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 19:50:28,090 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 19:50:28,090 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 201 Supporting invariants [] [2025-03-17 19:50:28,096 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:28,096 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 19:50:28,105 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:28,115 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-17 19:50:28,143 ERROR L418 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Exception during sending of exit command (exit): Broken pipe [2025-03-17 19:50:28,144 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2025-03-17 19:50:28,151 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-17 19:50:28,152 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:28,152 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:28,153 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-17 19:50:28,154 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:28,307 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:28,313 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:28,313 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:28,313 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:28,314 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 19:50:28,314 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:28,384 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:28,384 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-03-17 19:50:28,384 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-03-17 19:50:28,439 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-03-17 19:50:28,440 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-17 19:50:28,440 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-03-17 19:50:28,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 14 transitions. [2025-03-17 19:50:28,440 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 14 transitions. Stem has 37 letters. Loop has 8 letters. [2025-03-17 19:50:28,440 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:28,440 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:28,447 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:28,462 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-17 19:50:28,485 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-17 19:50:28,486 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:28,486 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:28,487 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-17 19:50:28,488 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:28,623 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:28,629 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:28,629 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:28,629 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:28,631 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 19:50:28,632 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:28,714 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:28,715 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-03-17 19:50:28,715 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-03-17 19:50:28,851 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-03-17 19:50:28,851 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-03-17 19:50:28,852 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-03-17 19:50:28,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 19 transitions. [2025-03-17 19:50:28,852 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 19 transitions. Stem has 37 letters. Loop has 8 letters. [2025-03-17 19:50:28,852 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:28,852 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:28,864 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:28,873 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-17 19:50:28,899 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-17 19:50:28,900 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:28,900 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:28,901 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-17 19:50:28,902 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:29,033 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:29,038 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:29,038 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:29,038 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:29,039 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 19:50:29,040 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:29,107 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:29,108 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-03-17 19:50:29,108 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-03-17 19:50:29,175 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-03-17 19:50:29,176 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-17 19:50:29,176 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-03-17 19:50:29,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2025-03-17 19:50:29,176 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 37 letters. Loop has 8 letters. [2025-03-17 19:50:29,177 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:29,177 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 19:50:29,184 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 19:50:29,196 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-17 19:50:29,217 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-17 19:50:29,217 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:29,217 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:29,218 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-17 19:50:29,219 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:29,376 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 19:50:29,382 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 19:50:29,382 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 19:50:29,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 19:50:29,382 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 19:50:29,383 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 19:50:29,455 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 19:50:29,455 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-03-17 19:50:29,455 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-03-17 19:50:29,699 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-03-17 19:50:29,699 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-03-17 19:50:29,699 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-03-17 19:50:29,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 26 transitions. [2025-03-17 19:50:29,700 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 26 transitions. Stem has 37 letters. Loop has 8 letters. [2025-03-17 19:50:29,700 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:29,700 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 26 transitions. Stem has 45 letters. Loop has 8 letters. [2025-03-17 19:50:29,700 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:29,700 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 26 transitions. Stem has 37 letters. Loop has 16 letters. [2025-03-17 19:50:29,701 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 19:50:29,701 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 181 states and 208 transitions. [2025-03-17 19:50:29,703 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 19:50:29,703 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 181 states to 0 states and 0 transitions. [2025-03-17 19:50:29,703 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 19:50:29,703 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 19:50:29,703 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 19:50:29,703 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 19:50:29,703 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:29,703 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:29,703 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 19:50:29,703 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-17 19:50:29,703 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-17 19:50:29,703 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 19:50:29,703 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-17 19:50:29,709 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.03 07:50:29 BoogieIcfgContainer [2025-03-17 19:50:29,709 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-17 19:50:29,709 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-17 19:50:29,709 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-17 19:50:29,709 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-17 19:50:29,710 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 07:50:21" (3/4) ... [2025-03-17 19:50:29,711 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-17 19:50:29,712 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-17 19:50:29,712 INFO L158 Benchmark]: Toolchain (without parser) took 8975.11ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 106.9MB in the beginning and 196.9MB in the end (delta: -90.0MB). Peak memory consumption was 48.6MB. Max. memory is 16.1GB. [2025-03-17 19:50:29,712 INFO L158 Benchmark]: CDTParser took 0.14ms. Allocated memory is still 201.3MB. Free memory is still 115.6MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:29,712 INFO L158 Benchmark]: CACSL2BoogieTranslator took 145.47ms. Allocated memory is still 142.6MB. Free memory was 105.9MB in the beginning and 96.8MB in the end (delta: 9.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 19:50:29,712 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.87ms. Allocated memory is still 142.6MB. Free memory was 96.8MB in the beginning and 95.8MB in the end (delta: 991.8kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:29,713 INFO L158 Benchmark]: Boogie Preprocessor took 18.92ms. Allocated memory is still 142.6MB. Free memory was 95.8MB in the beginning and 94.8MB in the end (delta: 996.0kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:29,713 INFO L158 Benchmark]: IcfgBuilder took 205.93ms. Allocated memory is still 142.6MB. Free memory was 94.8MB in the beginning and 85.0MB in the end (delta: 9.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 19:50:29,713 INFO L158 Benchmark]: BuchiAutomizer took 8575.63ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 85.0MB in the beginning and 198.3MB in the end (delta: -113.4MB). Peak memory consumption was 31.8MB. Max. memory is 16.1GB. [2025-03-17 19:50:29,713 INFO L158 Benchmark]: Witness Printer took 2.36ms. Allocated memory is still 285.2MB. Free memory was 198.3MB in the beginning and 196.9MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 19:50:29,714 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.14ms. Allocated memory is still 201.3MB. Free memory is still 115.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 145.47ms. Allocated memory is still 142.6MB. Free memory was 105.9MB in the beginning and 96.8MB in the end (delta: 9.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.87ms. Allocated memory is still 142.6MB. Free memory was 96.8MB in the beginning and 95.8MB in the end (delta: 991.8kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 18.92ms. Allocated memory is still 142.6MB. Free memory was 95.8MB in the beginning and 94.8MB in the end (delta: 996.0kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 205.93ms. Allocated memory is still 142.6MB. Free memory was 94.8MB in the beginning and 85.0MB in the end (delta: 9.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 8575.63ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 85.0MB in the beginning and 198.3MB in the end (delta: -113.4MB). Peak memory consumption was 31.8MB. Max. memory is 16.1GB. * Witness Printer took 2.36ms. Allocated memory is still 285.2MB. Free memory was 198.3MB in the beginning and 196.9MB in the end (delta: 1.5MB). 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.3s. Construction of modules took 0.6s. Büchi inclusion checks took 4.4s. 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.8s 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: 44ms VariablesStem: 0 VariablesLoop: 2 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.2s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-17 19:50:29,725 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-17 19:50:29,925 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE