./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 e2fb8bed 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-?-e2fb8be-m [2025-03-09 06:47:34,427 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-09 06:47:34,471 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2025-03-09 06:47:34,475 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-09 06:47:34,475 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-09 06:47:34,475 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-09 06:47:34,490 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-09 06:47:34,490 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-09 06:47:34,490 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-09 06:47:34,491 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-09 06:47:34,491 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-09 06:47:34,491 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-09 06:47:34,491 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-09 06:47:34,491 INFO L153 SettingsManager]: * Use SBE=true [2025-03-09 06:47:34,491 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-09 06:47:34,491 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-09 06:47:34,491 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-09 06:47:34,492 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-09 06:47:34,492 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-09 06:47:34,493 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-09 06:47:34,493 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-09 06:47:34,493 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-09 06:47:34,493 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-09 06:47:34,493 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-09 06:47:34,493 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-09 06:47:34,493 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-09 06:47:34,493 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-09 06:47:34,731 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-09 06:47:34,736 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-09 06:47:34,742 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-09 06:47:34,743 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-09 06:47:34,743 INFO L274 PluginConnector]: CDTParser initialized [2025-03-09 06:47:34,744 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-09 06:47:35,931 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fd2c19b44/eeaee6babc8444539c68a0dcb93049d5/FLAGa67091724 [2025-03-09 06:47:36,144 INFO L384 CDTParser]: Found 1 translation units. [2025-03-09 06:47:36,144 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-03-09 06:47:36,152 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fd2c19b44/eeaee6babc8444539c68a0dcb93049d5/FLAGa67091724 [2025-03-09 06:47:36,519 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fd2c19b44/eeaee6babc8444539c68a0dcb93049d5 [2025-03-09 06:47:36,521 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-09 06:47:36,522 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-09 06:47:36,523 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-09 06:47:36,523 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-09 06:47:36,526 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-09 06:47:36,526 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,527 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7c3d9581 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36, skipping insertion in model container [2025-03-09 06:47:36,527 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,535 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-09 06:47:36,634 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-09 06:47:36,637 INFO L200 MainTranslator]: Completed pre-run [2025-03-09 06:47:36,644 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-09 06:47:36,653 INFO L204 MainTranslator]: Completed translation [2025-03-09 06:47:36,654 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36 WrapperNode [2025-03-09 06:47:36,654 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-09 06:47:36,654 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-09 06:47:36,655 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-09 06:47:36,655 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-09 06:47:36,659 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,661 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,670 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2025-03-09 06:47:36,672 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-09 06:47:36,672 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-09 06:47:36,672 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-09 06:47:36,672 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-09 06:47:36,677 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,678 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,679 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,682 INFO L175 MemorySlicer]: No memory access in input program. [2025-03-09 06:47:36,683 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,683 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,684 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,685 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,685 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,686 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,686 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-09 06:47:36,688 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-09 06:47:36,688 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-09 06:47:36,688 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-09 06:47:36,689 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (1/1) ... [2025-03-09 06:47:36,694 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:36,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:36,716 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-09 06:47:36,719 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-09 06:47:36,744 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-09 06:47:36,744 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-09 06:47:36,744 INFO L130 BoogieDeclarations]: Found specification of procedure mc91 [2025-03-09 06:47:36,744 INFO L138 BoogieDeclarations]: Found implementation of procedure mc91 [2025-03-09 06:47:36,781 INFO L256 CfgBuilder]: Building ICFG [2025-03-09 06:47:36,783 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-09 06:47:36,844 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2025-03-09 06:47:36,845 INFO L307 CfgBuilder]: Performing block encoding [2025-03-09 06:47:36,850 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-09 06:47:36,850 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-09 06:47:36,850 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.03 06:47:36 BoogieIcfgContainer [2025-03-09 06:47:36,851 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-09 06:47:36,851 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-09 06:47:36,851 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-09 06:47:36,855 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-09 06:47:36,855 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-09 06:47:36,855 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.03 06:47:36" (1/3) ... [2025-03-09 06:47:36,856 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3ee15634 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.03 06:47:36, skipping insertion in model container [2025-03-09 06:47:36,856 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-09 06:47:36,856 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.03 06:47:36" (2/3) ... [2025-03-09 06:47:36,856 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3ee15634 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.03 06:47:36, skipping insertion in model container [2025-03-09 06:47:36,856 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-09 06:47:36,856 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.03 06:47:36" (3/3) ... [2025-03-09 06:47:36,857 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91_Recursion.c [2025-03-09 06:47:36,891 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-09 06:47:36,891 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-09 06:47:36,891 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-09 06:47:36,891 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-09 06:47:36,891 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-09 06:47:36,891 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-09 06:47:36,891 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-09 06:47:36,892 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-09 06:47:36,895 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 9 states have internal predecessors, (10), 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-09 06:47:36,904 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-09 06:47:36,904 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 06:47:36,905 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 06:47:36,908 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-09 06:47:36,908 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-09 06:47:36,908 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-09 06:47:36,908 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 9 states have internal predecessors, (10), 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-09 06:47:36,909 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-09 06:47:36,909 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 06:47:36,909 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 06:47:36,909 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-09 06:47:36,909 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-09 06:47:36,913 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-09 06:47:36,914 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< [2025-03-09 06:47:36,918 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:36,918 INFO L85 PathProgramCache]: Analyzing trace with hash 33741, now seen corresponding path program 1 times [2025-03-09 06:47:36,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:36,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1712946625] [2025-03-09 06:47:36,925 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:36,926 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:36,966 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:36,969 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:36,970 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:36,971 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:36,971 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:36,974 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:36,975 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:36,975 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:36,975 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:36,984 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:36,986 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:36,986 INFO L85 PathProgramCache]: Analyzing trace with hash 40689, now seen corresponding path program 1 times [2025-03-09 06:47:36,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:36,986 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [240872722] [2025-03-09 06:47:36,986 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:36,986 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:36,990 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:36,999 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:37,000 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,000 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,001 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:37,002 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:37,005 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:37,008 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,009 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,010 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:37,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:37,011 INFO L85 PathProgramCache]: Analyzing trace with hash 1005189029, now seen corresponding path program 1 times [2025-03-09 06:47:37,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:37,011 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [121375960] [2025-03-09 06:47:37,011 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:37,011 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:37,017 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-09 06:47:37,020 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-09 06:47:37,021 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,022 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,022 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:37,024 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-09 06:47:37,026 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-09 06:47:37,027 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,028 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,029 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:37,111 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:37,111 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:37,111 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:37,112 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:37,112 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 06:47:37,112 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,112 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:37,112 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:37,112 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-03-09 06:47:37,112 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:37,112 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:37,122 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,138 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,141 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,144 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,148 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,187 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:37,187 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 06:47:37,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,190 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-09 06:47:37,192 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-09 06:47:37,193 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:37,193 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:37,214 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2025-03-09 06:47:37,215 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,215 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,218 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-09 06:47:37,220 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-09 06:47:37,222 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 06:47:37,222 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:37,249 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 06:47:37,253 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-09 06:47:37,254 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:37,254 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:37,254 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:37,254 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:37,254 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 06:47:37,254 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,254 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:37,254 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:37,254 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-03-09 06:47:37,254 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:37,254 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:37,255 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,262 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,264 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,266 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,268 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,302 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:37,304 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 06:47:37,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,307 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-09 06:47:37,309 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-09 06:47:37,312 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-09 06:47:37,323 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:37,324 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:37,324 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:37,324 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:37,324 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:37,328 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:37,328 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:37,331 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 06:47:37,338 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 06:47:37,340 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 06:47:37,341 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,344 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-09 06:47:37,347 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-09 06:47:37,347 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 06:47:37,348 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 06:47:37,348 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 06:47:37,349 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 211 Supporting invariants [] [2025-03-09 06:47:37,354 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2025-03-09 06:47:37,357 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 06:47:37,383 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:37,392 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:37,397 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:37,397 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,397 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:37,399 INFO L256 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-09 06:47:37,399 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:37,410 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:37,418 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:37,418 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,418 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:37,419 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 06:47:37,420 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:37,479 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-09 06:47:37,501 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-09 06:47:37,503 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 14 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 9 states have internal predecessors, (10), 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.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 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-09 06:47:37,598 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 14 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 9 states have internal predecessors, (10), 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.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 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 32 states and 39 transitions. Complement of second has 16 states. [2025-03-09 06:47:37,599 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-09 06:47:37,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 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-09 06:47:37,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2025-03-09 06:47:37,607 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2025-03-09 06:47:37,608 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:37,608 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2025-03-09 06:47:37,608 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:37,608 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2025-03-09 06:47:37,609 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:37,609 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 39 transitions. [2025-03-09 06:47:37,611 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-09 06:47:37,613 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 19 states and 25 transitions. [2025-03-09 06:47:37,614 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2025-03-09 06:47:37,614 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2025-03-09 06:47:37,614 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2025-03-09 06:47:37,615 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 06:47:37,615 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2025-03-09 06:47:37,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2025-03-09 06:47:37,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2025-03-09 06:47:37,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 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-09 06:47:37,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2025-03-09 06:47:37,632 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2025-03-09 06:47:37,632 INFO L432 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2025-03-09 06:47:37,632 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-09 06:47:37,632 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2025-03-09 06:47:37,633 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-09 06:47:37,633 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 06:47:37,633 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 06:47:37,637 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 06:47:37,637 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-09 06:47:37,637 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;" >"#18#return;" [2025-03-09 06:47:37,637 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;" >"#18#return;" [2025-03-09 06:47:37,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:37,638 INFO L85 PathProgramCache]: Analyzing trace with hash -1053772474, now seen corresponding path program 1 times [2025-03-09 06:47:37,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:37,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1585177258] [2025-03-09 06:47:37,638 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:37,638 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:37,640 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 06:47:37,643 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 06:47:37,643 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,643 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,643 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:37,644 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 06:47:37,646 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 06:47:37,646 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,646 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,647 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:37,647 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:37,647 INFO L85 PathProgramCache]: Analyzing trace with hash 39827909, now seen corresponding path program 1 times [2025-03-09 06:47:37,647 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:37,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [711319541] [2025-03-09 06:47:37,647 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:37,647 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:37,649 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:37,651 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:37,652 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,652 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,652 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:37,653 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:37,655 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:37,655 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,655 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,658 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:37,659 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:37,659 INFO L85 PathProgramCache]: Analyzing trace with hash -327329270, now seen corresponding path program 1 times [2025-03-09 06:47:37,659 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:37,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1664427583] [2025-03-09 06:47:37,659 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:37,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:37,664 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-09 06:47:37,671 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-09 06:47:37,672 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,672 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,672 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:37,673 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-09 06:47:37,677 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-09 06:47:37,677 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:37,677 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:37,680 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:37,797 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2025-03-09 06:47:37,832 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:37,832 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:37,832 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:37,832 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:37,832 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 06:47:37,832 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,832 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:37,832 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:37,833 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-03-09 06:47:37,833 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:37,833 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:37,833 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,837 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,841 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:37,882 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:37,882 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 06:47:37,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,884 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-09 06:47:37,886 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-09 06:47:37,887 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:37,887 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:37,898 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 06:47:37,898 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-09 06:47:37,906 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2025-03-09 06:47:37,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,906 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,908 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-09 06:47:37,909 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-09 06:47:37,910 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:37,910 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:37,921 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 06:47:37,921 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 06:47:37,927 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-09 06:47:37,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,929 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-09 06:47:37,930 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-09 06:47:37,930 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:37,931 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:37,957 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-09 06:47:37,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:37,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:37,960 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-09 06:47:37,960 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-09 06:47:37,961 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 06:47:37,961 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:38,508 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 06:47:38,523 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-09 06:47:38,523 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:38,523 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:38,523 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:38,523 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:38,523 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 06:47:38,523 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:38,523 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:38,523 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:38,524 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-03-09 06:47:38,524 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:38,524 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:38,525 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:38,526 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:38,539 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:38,577 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:38,577 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 06:47:38,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:38,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:38,579 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-09 06:47:38,581 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-09 06:47:38,582 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-09 06:47:38,592 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:38,592 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:38,592 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:38,592 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:38,592 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:38,593 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:38,593 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:38,594 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 06:47:38,603 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-09 06:47:38,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:38,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:38,605 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-09 06:47:38,606 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-09 06:47:38,608 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-09 06:47:38,619 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:38,619 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:38,619 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:38,620 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:38,620 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:38,622 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:38,622 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:38,626 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 06:47:38,630 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 06:47:38,630 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 06:47:38,630 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:38,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:38,632 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-09 06:47:38,634 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-09 06:47:38,635 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 06:47:38,635 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 06:47:38,635 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 06:47:38,636 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2025-03-09 06:47:38,642 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-09 06:47:38,643 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 06:47:38,646 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2025-03-09 06:47:38,658 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:38,667 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-09 06:47:38,677 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-09 06:47:38,677 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:38,677 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:38,679 INFO L256 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-09 06:47:38,679 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:38,741 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:38,750 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:38,750 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:38,750 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:38,751 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-09 06:47:38,751 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:38,856 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-09 06:47:38,857 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-09 06:47:38,857 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 17 states and 21 transitions. cyclomatic complexity: 6 Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 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-09 06:47:39,003 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 17 states and 21 transitions. cyclomatic complexity: 6. Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 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 51 states and 73 transitions. Complement of second has 32 states. [2025-03-09 06:47:39,004 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-09 06:47:39,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 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-09 06:47:39,005 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2025-03-09 06:47:39,005 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2025-03-09 06:47:39,006 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:39,006 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2025-03-09 06:47:39,006 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:39,006 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2025-03-09 06:47:39,006 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:39,006 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2025-03-09 06:47:39,008 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-09 06:47:39,010 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2025-03-09 06:47:39,010 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2025-03-09 06:47:39,010 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-03-09 06:47:39,010 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2025-03-09 06:47:39,010 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 06:47:39,010 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2025-03-09 06:47:39,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2025-03-09 06:47:39,012 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2025-03-09 06:47:39,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 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-09 06:47:39,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2025-03-09 06:47:39,013 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2025-03-09 06:47:39,013 INFO L432 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2025-03-09 06:47:39,013 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-09 06:47:39,013 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2025-03-09 06:47:39,014 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-09 06:47:39,014 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 06:47:39,014 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 06:47:39,014 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-09 06:47:39,014 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-09 06:47:39,014 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;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume !(~n > 100);" [2025-03-09 06:47:39,014 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" [2025-03-09 06:47:39,015 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:39,015 INFO L85 PathProgramCache]: Analyzing trace with hash -1019791704, now seen corresponding path program 2 times [2025-03-09 06:47:39,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:39,015 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1056284880] [2025-03-09 06:47:39,015 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 06:47:39,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:39,019 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 13 statements into 2 equivalence classes. [2025-03-09 06:47:39,026 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 13 of 13 statements. [2025-03-09 06:47:39,028 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 06:47:39,028 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:39,028 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:39,029 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-09 06:47:39,033 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-09 06:47:39,036 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:39,037 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:39,038 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:39,038 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:39,040 INFO L85 PathProgramCache]: Analyzing trace with hash 46479, now seen corresponding path program 2 times [2025-03-09 06:47:39,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:39,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [831206702] [2025-03-09 06:47:39,040 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 06:47:39,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:39,042 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:39,043 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:39,043 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-09 06:47:39,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:39,043 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:39,043 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:39,044 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:39,044 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:39,044 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:39,044 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:39,045 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:39,045 INFO L85 PathProgramCache]: Analyzing trace with hash 1984014728, now seen corresponding path program 3 times [2025-03-09 06:47:39,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:39,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1630356299] [2025-03-09 06:47:39,045 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-09 06:47:39,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:39,047 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 16 statements into 4 equivalence classes. [2025-03-09 06:47:39,054 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 16 of 16 statements. [2025-03-09 06:47:39,055 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-09 06:47:39,055 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:39,197 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-09 06:47:39,197 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 06:47:39,197 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1630356299] [2025-03-09 06:47:39,197 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1630356299] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-09 06:47:39,198 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-09 06:47:39,198 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-09 06:47:39,198 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [884690948] [2025-03-09 06:47:39,198 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-09 06:47:39,232 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:39,232 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:39,232 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:39,232 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:39,232 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 06:47:39,232 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:39,232 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:39,232 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:39,232 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-03-09 06:47:39,232 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:39,232 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:39,232 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,239 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,244 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,249 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,272 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:39,272 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 06:47:39,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:39,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:39,274 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-09 06:47:39,276 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-09 06:47:39,277 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:39,277 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:39,305 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-09 06:47:39,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:39,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:39,307 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-09 06:47:39,308 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-09 06:47:39,310 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 06:47:39,310 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:39,613 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 06:47:39,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2025-03-09 06:47:39,622 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:39,622 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:39,622 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:39,622 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:39,622 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 06:47:39,623 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:39,623 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:39,623 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:39,623 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-03-09 06:47:39,623 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:39,623 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:39,623 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,633 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,634 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,636 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:39,675 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:39,675 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 06:47:39,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:39,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:39,675 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-09 06:47:39,677 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-09 06:47:39,679 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-09 06:47:39,680 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-09 06:47:39,690 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:39,690 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:39,690 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:39,690 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:39,690 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:39,691 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:39,691 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:39,693 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 06:47:39,696 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 06:47:39,696 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 06:47:39,696 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:39,696 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:39,698 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-09 06:47:39,699 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-09 06:47:39,701 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 06:47:39,701 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 06:47:39,701 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 06:47:39,701 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_~n) = -2*mc91_~n + 189 Supporting invariants [] [2025-03-09 06:47:39,707 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2025-03-09 06:47:39,708 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 06:47:39,721 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:39,728 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-09 06:47:39,740 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-09 06:47:39,740 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:39,740 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:39,741 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-09 06:47:39,742 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:39,803 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:39,807 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:39,807 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:39,807 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:39,808 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 06:47:39,808 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:39,831 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-09 06:47:39,832 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-09 06:47:39,832 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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-09 06:47:39,885 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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 43 states and 59 transitions. Complement of second has 13 states. [2025-03-09 06:47:39,888 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-09 06:47:39,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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-09 06:47:39,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-03-09 06:47:39,890 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-09 06:47:39,890 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:39,890 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:39,900 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:39,905 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-09 06:47:39,914 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-09 06:47:39,914 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:39,914 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:39,915 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-09 06:47:39,916 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:39,963 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:39,966 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:39,966 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:39,966 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:39,966 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 06:47:39,967 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:39,990 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-09 06:47:39,990 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-09 06:47:39,990 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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-09 06:47:40,036 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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 43 states and 59 transitions. Complement of second has 13 states. [2025-03-09 06:47:40,036 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-09 06:47:40,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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-09 06:47:40,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-03-09 06:47:40,037 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-09 06:47:40,037 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:40,037 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:40,046 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:40,052 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-09 06:47:40,062 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-09 06:47:40,063 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:40,063 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:40,063 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-09 06:47:40,064 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:40,117 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-09 06:47:40,121 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-09 06:47:40,121 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:40,121 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:40,121 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-09 06:47:40,122 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:40,138 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-09 06:47:40,139 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-09 06:47:40,139 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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-09 06:47:40,201 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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 71 states and 100 transitions. Complement of second has 16 states. [2025-03-09 06:47:40,201 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-09 06:47:40,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (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-09 06:47:40,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2025-03-09 06:47:40,203 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-09 06:47:40,203 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:40,204 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2025-03-09 06:47:40,204 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:40,204 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2025-03-09 06:47:40,204 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:40,205 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2025-03-09 06:47:40,207 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-03-09 06:47:40,210 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2025-03-09 06:47:40,211 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2025-03-09 06:47:40,211 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2025-03-09 06:47:40,211 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2025-03-09 06:47:40,211 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 06:47:40,211 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2025-03-09 06:47:40,211 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2025-03-09 06:47:40,214 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2025-03-09 06:47:40,215 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 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-09 06:47:40,215 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2025-03-09 06:47:40,215 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2025-03-09 06:47:40,215 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 06:47:40,216 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-09 06:47:40,217 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-09 06:47:40,217 INFO L87 Difference]: Start difference. First operand 42 states and 60 transitions. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 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-09 06:47:40,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 06:47:40,292 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2025-03-09 06:47:40,292 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2025-03-09 06:47:40,294 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-09 06:47:40,296 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2025-03-09 06:47:40,296 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2025-03-09 06:47:40,296 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2025-03-09 06:47:40,296 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2025-03-09 06:47:40,296 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 06:47:40,296 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-09 06:47:40,296 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2025-03-09 06:47:40,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2025-03-09 06:47:40,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.0571428571428572) internal successors, (37), 37 states have internal predecessors, (37), 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-09 06:47:40,300 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2025-03-09 06:47:40,300 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-09 06:47:40,300 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-09 06:47:40,301 INFO L432 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-09 06:47:40,301 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-09 06:47:40,301 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2025-03-09 06:47:40,302 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-09 06:47:40,302 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 06:47:40,302 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 06:47:40,303 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-09 06:47:40,303 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-03-09 06:47:40,303 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;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-03-09 06:47:40,303 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;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-03-09 06:47:40,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:40,303 INFO L85 PathProgramCache]: Analyzing trace with hash 1867148514, now seen corresponding path program 1 times [2025-03-09 06:47:40,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:40,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1721151173] [2025-03-09 06:47:40,304 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:40,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:40,309 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-09 06:47:40,312 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-09 06:47:40,312 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:40,312 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:40,312 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:40,317 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-09 06:47:40,323 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-09 06:47:40,324 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:40,324 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:40,325 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:40,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:40,326 INFO L85 PathProgramCache]: Analyzing trace with hash 161545262, now seen corresponding path program 1 times [2025-03-09 06:47:40,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:40,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1561069507] [2025-03-09 06:47:40,326 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-09 06:47:40,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:40,328 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-09 06:47:40,334 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-09 06:47:40,334 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:40,334 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:40,335 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:40,335 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-09 06:47:40,341 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-09 06:47:40,341 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:40,341 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:40,342 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:40,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:40,342 INFO L85 PathProgramCache]: Analyzing trace with hash 230980013, now seen corresponding path program 2 times [2025-03-09 06:47:40,342 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:40,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [383614739] [2025-03-09 06:47:40,342 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 06:47:40,342 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:40,350 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 41 statements into 2 equivalence classes. [2025-03-09 06:47:40,359 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 41 of 41 statements. [2025-03-09 06:47:40,361 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 06:47:40,361 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:40,426 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2025-03-09 06:47:40,490 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-09 06:47:40,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-09 06:47:40,491 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [383614739] [2025-03-09 06:47:40,491 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [383614739] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-09 06:47:40,491 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1809612409] [2025-03-09 06:47:40,491 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 06:47:40,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-09 06:47:40,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:40,494 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-09 06:47:40,494 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-09 06:47:40,522 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 41 statements into 2 equivalence classes. [2025-03-09 06:47:40,531 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 41 of 41 statements. [2025-03-09 06:47:40,531 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 06:47:40,531 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:40,531 INFO L256 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-09 06:47:40,533 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:40,569 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-09 06:47:40,569 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-09 06:47:40,737 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-09 06:47:40,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1809612409] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-09 06:47:40,737 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-09 06:47:40,737 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-03-09 06:47:40,737 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130727126] [2025-03-09 06:47:40,738 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-09 06:47:40,872 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:40,872 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:40,872 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:40,872 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:40,872 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 06:47:40,872 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:40,872 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:40,872 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:40,872 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-03-09 06:47:40,872 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:40,872 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:40,873 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,877 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,879 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,881 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,883 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,902 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:40,902 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 06:47:40,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:40,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:40,907 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-09 06:47:40,908 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-09 06:47:40,910 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:40,910 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:40,932 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-09 06:47:40,932 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:40,932 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:40,934 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-09 06:47:40,934 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-09 06:47:40,936 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 06:47:40,936 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:40,947 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 06:47:40,953 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-09 06:47:40,953 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:40,953 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:40,953 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:40,953 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:40,953 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 06:47:40,953 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:40,953 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:40,953 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:40,953 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-03-09 06:47:40,953 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:40,953 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:40,954 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,960 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,961 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,963 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,964 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:40,982 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:40,982 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 06:47:40,982 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:40,982 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:40,984 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-09 06:47:40,985 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-09 06:47:40,986 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-09 06:47:40,997 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:40,997 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:40,997 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:40,997 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:40,997 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:41,000 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:41,000 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:41,002 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 06:47:41,004 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 06:47:41,004 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 06:47:41,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:41,004 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:41,006 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-09 06:47:41,008 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-09 06:47:41,009 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 06:47:41,009 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 06:47:41,009 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 06:47:41,010 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -1*mc91_#in~n + 90 Supporting invariants [] [2025-03-09 06:47:41,017 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-09 06:47:41,018 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 06:47:41,026 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:41,035 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-09 06:47:41,050 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-09 06:47:41,051 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:41,051 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:41,054 INFO L256 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-09 06:47:41,055 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:41,187 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-09 06:47:41,210 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-09 06:47:41,213 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-09 06:47:41,213 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:41,213 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:41,214 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-09 06:47:41,215 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:41,398 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-09 06:47:41,398 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-09 06:47:41,399 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 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-09 06:47:41,697 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 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 125 states and 150 transitions. Complement of second has 49 states. [2025-03-09 06:47:41,698 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-09 06:47:41,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 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-09 06:47:41,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2025-03-09 06:47:41,699 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2025-03-09 06:47:41,699 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:41,699 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:41,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:41,714 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-09 06:47:41,733 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-09 06:47:41,733 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:41,734 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:41,734 INFO L256 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-09 06:47:41,735 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:41,856 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-09 06:47:41,868 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-09 06:47:41,868 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:41,868 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:41,869 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 06:47:41,870 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:42,018 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-09 06:47:42,019 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 9 loop predicates [2025-03-09 06:47:42,019 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 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-09 06:47:42,231 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 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 125 states and 150 transitions. Complement of second has 39 states. [2025-03-09 06:47:42,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 14 states 2 stem states 11 non-accepting loop states 1 accepting loop states [2025-03-09 06:47:42,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 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-09 06:47:42,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2025-03-09 06:47:42,233 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 14 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2025-03-09 06:47:42,233 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:42,233 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:42,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:42,256 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-09 06:47:42,274 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-09 06:47:42,274 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:42,274 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:42,275 INFO L256 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-09 06:47:42,276 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:42,378 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-09 06:47:42,389 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-09 06:47:42,389 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:42,389 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:42,390 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 06:47:42,391 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:42,509 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-09 06:47:42,509 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-09 06:47:42,510 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 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-09 06:47:42,943 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 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 325 states and 417 transitions. Complement of second has 131 states. [2025-03-09 06:47:42,945 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-09 06:47:42,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 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-09 06:47:42,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 50 transitions. [2025-03-09 06:47:42,946 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2025-03-09 06:47:42,946 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:42,946 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2025-03-09 06:47:42,947 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:42,947 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2025-03-09 06:47:42,947 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:42,947 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 325 states and 417 transitions. [2025-03-09 06:47:42,954 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 25 [2025-03-09 06:47:42,957 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 325 states to 169 states and 230 transitions. [2025-03-09 06:47:42,957 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2025-03-09 06:47:42,957 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2025-03-09 06:47:42,958 INFO L73 IsDeterministic]: Start isDeterministic. Operand 169 states and 230 transitions. [2025-03-09 06:47:42,958 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 06:47:42,958 INFO L218 hiAutomatonCegarLoop]: Abstraction has 169 states and 230 transitions. [2025-03-09 06:47:42,958 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states and 230 transitions. [2025-03-09 06:47:42,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 140. [2025-03-09 06:47:42,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 86 states have (on average 1.0813953488372092) internal successors, (93), 88 states have internal predecessors, (93), 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-09 06:47:42,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 178 transitions. [2025-03-09 06:47:42,966 INFO L240 hiAutomatonCegarLoop]: Abstraction has 140 states and 178 transitions. [2025-03-09 06:47:42,966 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-09 06:47:42,966 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-09 06:47:42,966 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-03-09 06:47:42,967 INFO L87 Difference]: Start difference. First operand 140 states and 178 transitions. Second operand has 15 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 8 states have internal predecessors, (22), 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-09 06:47:43,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-09 06:47:43,126 INFO L93 Difference]: Finished difference Result 138 states and 163 transitions. [2025-03-09 06:47:43,126 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 138 states and 163 transitions. [2025-03-09 06:47:43,128 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-09 06:47:43,129 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 138 states to 101 states and 121 transitions. [2025-03-09 06:47:43,129 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2025-03-09 06:47:43,129 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2025-03-09 06:47:43,129 INFO L73 IsDeterministic]: Start isDeterministic. Operand 101 states and 121 transitions. [2025-03-09 06:47:43,130 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-09 06:47:43,130 INFO L218 hiAutomatonCegarLoop]: Abstraction has 101 states and 121 transitions. [2025-03-09 06:47:43,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states and 121 transitions. [2025-03-09 06:47:43,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-03-09 06:47:43,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 60 states have (on average 1.05) internal successors, (63), 61 states have internal predecessors, (63), 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-09 06:47:43,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 117 transitions. [2025-03-09 06:47:43,134 INFO L240 hiAutomatonCegarLoop]: Abstraction has 97 states and 117 transitions. [2025-03-09 06:47:43,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-09 06:47:43,135 INFO L432 stractBuchiCegarLoop]: Abstraction has 97 states and 117 transitions. [2025-03-09 06:47:43,135 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-09 06:47:43,135 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 97 states and 117 transitions. [2025-03-09 06:47:43,136 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-09 06:47:43,136 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-09 06:47:43,136 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-09 06:47:43,137 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2025-03-09 06:47:43,137 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-09 06:47:43,137 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;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#16#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#18#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;" >"#18#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;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-03-09 06:47:43,137 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;" >"#18#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-03-09 06:47:43,137 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:43,137 INFO L85 PathProgramCache]: Analyzing trace with hash -1720383910, now seen corresponding path program 3 times [2025-03-09 06:47:43,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:43,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2056811136] [2025-03-09 06:47:43,138 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-09 06:47:43,138 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:43,140 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 38 statements into 7 equivalence classes. [2025-03-09 06:47:43,146 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 38 of 38 statements. [2025-03-09 06:47:43,146 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-09 06:47:43,146 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:43,146 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:43,147 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-09 06:47:43,152 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-09 06:47:43,152 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:43,152 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:43,154 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:43,154 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:43,154 INFO L85 PathProgramCache]: Analyzing trace with hash 965737405, now seen corresponding path program 2 times [2025-03-09 06:47:43,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:43,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [665468193] [2025-03-09 06:47:43,155 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-09 06:47:43,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:43,156 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-03-09 06:47:43,160 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:43,160 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-09 06:47:43,160 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:43,161 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:43,164 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:43,165 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:43,165 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:43,165 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:43,166 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:43,166 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:43,166 INFO L85 PathProgramCache]: Analyzing trace with hash -1268147946, now seen corresponding path program 4 times [2025-03-09 06:47:43,166 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-09 06:47:43,166 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [540144518] [2025-03-09 06:47:43,166 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-09 06:47:43,166 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-09 06:47:43,173 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 46 statements into 2 equivalence classes. [2025-03-09 06:47:43,177 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 46 of 46 statements. [2025-03-09 06:47:43,177 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-09 06:47:43,177 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:43,177 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-09 06:47:43,179 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-03-09 06:47:43,189 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-03-09 06:47:43,189 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:43,189 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-09 06:47:43,191 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-09 06:47:43,246 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:43,246 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:43,247 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:43,247 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:43,247 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-09 06:47:43,247 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,247 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:43,247 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:43,247 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-03-09 06:47:43,247 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:43,247 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:43,247 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,249 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,250 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,254 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,256 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,273 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:43,273 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-09 06:47:43,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,275 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-09 06:47:43,276 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-09 06:47:43,277 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:43,277 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:43,288 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 06:47:43,288 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-09 06:47:43,293 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-09 06:47:43,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,295 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-09 06:47:43,296 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-09 06:47:43,297 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:43,297 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:43,307 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-09 06:47:43,307 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-09 06:47:43,313 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2025-03-09 06:47:43,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,315 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-09 06:47:43,316 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-09 06:47:43,317 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-09 06:47:43,317 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:43,333 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-09 06:47:43,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,335 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-09 06:47:43,337 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-09 06:47:43,338 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-09 06:47:43,338 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-09 06:47:43,349 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-09 06:47:43,354 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-03-09 06:47:43,354 INFO L204 LassoAnalysis]: Preferences: [2025-03-09 06:47:43,355 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-09 06:47:43,355 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-09 06:47:43,355 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-09 06:47:43,355 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-09 06:47:43,355 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,355 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-09 06:47:43,355 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-09 06:47:43,355 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-03-09 06:47:43,355 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-09 06:47:43,355 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-09 06:47:43,355 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,357 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,358 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,368 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,371 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-09 06:47:43,386 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-09 06:47:43,387 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-09 06:47:43,387 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,387 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,389 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-09 06:47:43,389 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-09 06:47:43,390 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-09 06:47:43,400 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:43,400 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:43,400 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:43,400 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:43,400 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:43,400 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:43,400 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:43,401 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 06:47:43,406 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-09 06:47:43,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,408 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-09 06:47:43,409 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-09 06:47:43,410 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-09 06:47:43,420 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:43,420 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:43,421 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:43,421 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:43,421 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:43,421 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:43,421 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:43,422 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-09 06:47:43,430 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2025-03-09 06:47:43,430 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,430 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,432 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-09 06:47:43,434 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-09 06:47:43,434 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-09 06:47:43,445 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-09 06:47:43,445 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-09 06:47:43,445 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-09 06:47:43,445 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-09 06:47:43,445 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-09 06:47:43,445 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-09 06:47:43,446 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-09 06:47:43,447 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-09 06:47:43,449 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-09 06:47:43,449 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-09 06:47:43,449 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-09 06:47:43,449 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-09 06:47:43,451 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-09 06:47:43,453 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-09 06:47:43,454 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-09 06:47:43,454 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-09 06:47:43,454 INFO L474 LassoAnalysis]: Proved termination. [2025-03-09 06:47:43,454 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 201 Supporting invariants [] [2025-03-09 06:47:43,460 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2025-03-09 06:47:43,461 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-09 06:47:43,469 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:43,483 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-09 06:47:43,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-09 06:47:43,512 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:43,512 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:43,513 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 06:47:43,515 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:43,559 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2025-03-09 06:47:43,682 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:43,688 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:43,689 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:43,689 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:43,689 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-09 06:47:43,690 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:43,756 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-09 06:47:43,757 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-09 06:47:43,757 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:43,822 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 107 states and 127 transitions. Complement of second has 16 states. [2025-03-09 06:47:43,823 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-09 06:47:43,824 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:43,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 15 transitions. [2025-03-09 06:47:43,824 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 15 transitions. Stem has 38 letters. Loop has 8 letters. [2025-03-09 06:47:43,824 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:43,824 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:43,831 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:43,844 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-09 06:47:43,865 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-09 06:47:43,865 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:43,865 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:43,867 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 06:47:43,868 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:44,004 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:44,011 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:44,011 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:44,011 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:44,012 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-09 06:47:44,012 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:44,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-09 06:47:44,108 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-09 06:47:44,108 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:44,237 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 125 states and 146 transitions. Complement of second has 28 states. [2025-03-09 06:47:44,237 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-09 06:47:44,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:44,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 20 transitions. [2025-03-09 06:47:44,238 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 20 transitions. Stem has 38 letters. Loop has 8 letters. [2025-03-09 06:47:44,238 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:44,238 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:44,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:44,255 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-09 06:47:44,280 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-09 06:47:44,280 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:44,280 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:44,282 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 06:47:44,283 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:44,419 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:44,425 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:44,426 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:44,426 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:44,426 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-09 06:47:44,427 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:44,489 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-09 06:47:44,490 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-09 06:47:44,490 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:44,555 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 147 states and 167 transitions. Complement of second has 17 states. [2025-03-09 06:47:44,557 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-09 06:47:44,557 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:44,557 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2025-03-09 06:47:44,557 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 38 letters. Loop has 8 letters. [2025-03-09 06:47:44,558 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:44,558 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-09 06:47:44,566 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-09 06:47:44,577 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-09 06:47:44,602 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-09 06:47:44,602 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:44,602 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:44,604 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-09 06:47:44,605 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:44,765 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-09 06:47:44,770 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-09 06:47:44,770 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-09 06:47:44,770 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-09 06:47:44,770 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-09 06:47:44,771 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-09 06:47:44,822 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-09 06:47:44,822 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-09 06:47:44,822 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:45,019 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 182 states and 209 transitions. Complement of second has 51 states. [2025-03-09 06:47:45,019 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-09 06:47:45,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 06:47:45,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 27 transitions. [2025-03-09 06:47:45,020 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 8 letters. [2025-03-09 06:47:45,020 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:45,020 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 46 letters. Loop has 8 letters. [2025-03-09 06:47:45,020 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:45,020 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 16 letters. [2025-03-09 06:47:45,023 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-09 06:47:45,023 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 182 states and 209 transitions. [2025-03-09 06:47:45,025 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-09 06:47:45,025 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 182 states to 0 states and 0 transitions. [2025-03-09 06:47:45,025 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-09 06:47:45,025 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-09 06:47:45,025 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-09 06:47:45,025 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-09 06:47:45,025 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-09 06:47:45,025 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-09 06:47:45,025 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-09 06:47:45,025 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-09 06:47:45,025 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-09 06:47:45,026 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-09 06:47:45,026 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-09 06:47:45,033 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.03 06:47:45 BoogieIcfgContainer [2025-03-09 06:47:45,034 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-09 06:47:45,034 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-09 06:47:45,034 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-09 06:47:45,035 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-09 06:47:45,035 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.03 06:47:36" (3/4) ... [2025-03-09 06:47:45,036 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-09 06:47:45,037 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-09 06:47:45,038 INFO L158 Benchmark]: Toolchain (without parser) took 8515.42ms. Allocated memory is still 142.6MB. Free memory was 103.8MB in the beginning and 55.6MB in the end (delta: 48.2MB). Peak memory consumption was 51.8MB. Max. memory is 16.1GB. [2025-03-09 06:47:45,038 INFO L158 Benchmark]: CDTParser took 0.14ms. Allocated memory is still 201.3MB. Free memory is still 125.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 06:47:45,038 INFO L158 Benchmark]: CACSL2BoogieTranslator took 131.05ms. Allocated memory is still 142.6MB. Free memory was 103.8MB in the beginning and 94.9MB in the end (delta: 9.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-09 06:47:45,038 INFO L158 Benchmark]: Boogie Procedure Inliner took 17.17ms. Allocated memory is still 142.6MB. Free memory was 94.9MB in the beginning and 93.7MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 06:47:45,038 INFO L158 Benchmark]: Boogie Preprocessor took 15.07ms. Allocated memory is still 142.6MB. Free memory was 93.7MB in the beginning and 92.6MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 06:47:45,038 INFO L158 Benchmark]: IcfgBuilder took 162.92ms. Allocated memory is still 142.6MB. Free memory was 92.6MB in the beginning and 82.6MB in the end (delta: 9.9MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-09 06:47:45,038 INFO L158 Benchmark]: BuchiAutomizer took 8182.67ms. Allocated memory is still 142.6MB. Free memory was 82.6MB in the beginning and 55.7MB in the end (delta: 26.9MB). Peak memory consumption was 26.6MB. Max. memory is 16.1GB. [2025-03-09 06:47:45,039 INFO L158 Benchmark]: Witness Printer took 2.71ms. Allocated memory is still 142.6MB. Free memory was 55.7MB in the beginning and 55.6MB in the end (delta: 41.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-09 06:47:45,040 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 125.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 131.05ms. Allocated memory is still 142.6MB. Free memory was 103.8MB in the beginning and 94.9MB in the end (delta: 9.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 17.17ms. Allocated memory is still 142.6MB. Free memory was 94.9MB in the beginning and 93.7MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 15.07ms. Allocated memory is still 142.6MB. Free memory was 93.7MB in the beginning and 92.6MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 162.92ms. Allocated memory is still 142.6MB. Free memory was 92.6MB in the beginning and 82.6MB in the end (delta: 9.9MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * BuchiAutomizer took 8182.67ms. Allocated memory is still 142.6MB. Free memory was 82.6MB in the beginning and 55.7MB in the end (delta: 26.9MB). Peak memory consumption was 26.6MB. Max. memory is 16.1GB. * Witness Printer took 2.71ms. Allocated memory is still 142.6MB. Free memory was 55.7MB in the beginning and 55.6MB in the end (delta: 41.6kB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret0 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 7 terminating modules (2 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function (211 + ((long) -2 * \old(n))) and consists of 5 locations. One deterministic module has affine ranking function null and consists of 8 locations. One nondeterministic module has affine ranking function (((long) -2 * n) + 189) and consists of 6 locations. One nondeterministic module has affine ranking function (90 + ((long) -1 * \old(n))) and consists of 19 locations. One nondeterministic module has affine ranking function (((long) -2 * \old(n)) + 201) and consists of 12 locations. 2 modules have a trivial ranking function, the largest among these consists of 15 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.1s and 6 iterations. TraceHistogramMax:8. Analysis of lassos took 3.1s. Construction of modules took 0.5s. Büchi inclusion checks took 4.2s. 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, 260 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 246 mSDsluCounter, 447 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 261 mSDsCounter, 205 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 944 IncrementalHoareTripleChecker+Invalid, 1149 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 205 mSolverCounterUnsat, 186 mSDtfsCounter, 944 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: 43ms VariablesStem: 0 VariablesLoop: 2 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.1s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-09 06:47:45,053 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-03-09 06:47:45,253 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE