./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 551b0097 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-10 06:59:48,736 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-10 06:59:48,816 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2025-01-10 06:59:48,820 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-10 06:59:48,821 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-10 06:59:48,850 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-10 06:59:48,851 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-10 06:59:48,851 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-10 06:59:48,852 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-10 06:59:48,852 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-10 06:59:48,853 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-10 06:59:48,853 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-10 06:59:48,853 INFO L153 SettingsManager]: * Use SBE=true [2025-01-10 06:59:48,853 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-01-10 06:59:48,854 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-01-10 06:59:48,854 INFO L153 SettingsManager]: * Use old map elimination=false [2025-01-10 06:59:48,854 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-01-10 06:59:48,854 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-01-10 06:59:48,855 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-10 06:59:48,855 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-10 06:59:48,855 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-10 06:59:48,855 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-10 06:59:48,856 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-10 06:59:48,856 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-01-10 06:59:48,856 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 [2025-01-10 06:59:49,160 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-10 06:59:49,169 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-10 06:59:49,173 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-10 06:59:49,174 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-10 06:59:49,174 INFO L274 PluginConnector]: CDTParser initialized [2025-01-10 06:59:49,175 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-01-10 06:59:50,512 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/afdfef78b/98e9d4f3bc964a1980520423996e3157/FLAG6fc88e206 [2025-01-10 06:59:50,716 INFO L384 CDTParser]: Found 1 translation units. [2025-01-10 06:59:50,717 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2025-01-10 06:59:50,736 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/afdfef78b/98e9d4f3bc964a1980520423996e3157/FLAG6fc88e206 [2025-01-10 06:59:50,757 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/afdfef78b/98e9d4f3bc964a1980520423996e3157 [2025-01-10 06:59:50,760 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-10 06:59:50,762 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-10 06:59:50,764 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-10 06:59:50,765 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-10 06:59:50,769 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-10 06:59:50,770 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,772 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6bc1643d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50, skipping insertion in model container [2025-01-10 06:59:50,773 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,786 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-10 06:59:50,913 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-10 06:59:50,919 INFO L200 MainTranslator]: Completed pre-run [2025-01-10 06:59:50,928 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-10 06:59:50,941 INFO L204 MainTranslator]: Completed translation [2025-01-10 06:59:50,942 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50 WrapperNode [2025-01-10 06:59:50,942 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-10 06:59:50,943 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-10 06:59:50,944 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-10 06:59:50,944 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-10 06:59:50,949 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,953 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,965 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2025-01-10 06:59:50,965 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-10 06:59:50,966 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-10 06:59:50,966 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-10 06:59:50,966 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-10 06:59:50,973 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,973 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,974 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,978 INFO L175 MemorySlicer]: No memory access in input program. [2025-01-10 06:59:50,978 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,978 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,979 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,979 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,980 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,981 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,981 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,982 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-10 06:59:50,982 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-10 06:59:50,983 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-10 06:59:50,983 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-10 06:59:50,984 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (1/1) ... [2025-01-10 06:59:50,988 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:50,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:51,011 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:51,018 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2025-01-10 06:59:51,035 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-10 06:59:51,035 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-10 06:59:51,035 INFO L130 BoogieDeclarations]: Found specification of procedure mc91 [2025-01-10 06:59:51,035 INFO L138 BoogieDeclarations]: Found implementation of procedure mc91 [2025-01-10 06:59:51,072 INFO L234 CfgBuilder]: Building ICFG [2025-01-10 06:59:51,074 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-10 06:59:51,154 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2025-01-10 06:59:51,154 INFO L283 CfgBuilder]: Performing block encoding [2025-01-10 06:59:51,160 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-10 06:59:51,161 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-10 06:59:51,161 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 06:59:51 BoogieIcfgContainer [2025-01-10 06:59:51,161 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-10 06:59:51,162 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-01-10 06:59:51,162 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-01-10 06:59:51,167 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-01-10 06:59:51,168 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-01-10 06:59:51,168 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 10.01 06:59:50" (1/3) ... [2025-01-10 06:59:51,169 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@412883a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.01 06:59:51, skipping insertion in model container [2025-01-10 06:59:51,169 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-01-10 06:59:51,169 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:59:50" (2/3) ... [2025-01-10 06:59:51,169 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@412883a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.01 06:59:51, skipping insertion in model container [2025-01-10 06:59:51,169 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-01-10 06:59:51,170 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 06:59:51" (3/3) ... [2025-01-10 06:59:51,171 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91_Recursion.c [2025-01-10 06:59:51,215 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-01-10 06:59:51,215 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-01-10 06:59:51,216 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-01-10 06:59:51,216 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-01-10 06:59:51,216 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-01-10 06:59:51,216 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-01-10 06:59:51,216 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-01-10 06:59:51,216 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-01-10 06:59:51,220 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-01-10 06:59:51,232 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-01-10 06:59:51,232 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-01-10 06:59:51,232 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-01-10 06:59:51,235 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-01-10 06:59:51,235 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-01-10 06:59:51,236 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-01-10 06:59:51,236 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-01-10 06:59:51,237 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-01-10 06:59:51,237 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-01-10 06:59:51,237 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-01-10 06:59:51,237 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-01-10 06:59:51,237 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-01-10 06:59:51,241 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-01-10 06:59:51,241 INFO L754 eck$LassoCheckResult]: Loop: "~n := #in~n;" "assume !(~n > 100);" "call #t~ret0 := mc91(11 + ~n);"< [2025-01-10 06:59:51,245 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:51,245 INFO L85 PathProgramCache]: Analyzing trace with hash 29870, now seen corresponding path program 1 times [2025-01-10 06:59:51,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:51,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [425046037] [2025-01-10 06:59:51,252 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:51,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:51,304 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:51,307 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:51,307 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,307 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:51,308 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:51,310 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:51,310 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:51,311 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,311 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:51,323 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:51,325 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:51,325 INFO L85 PathProgramCache]: Analyzing trace with hash 37870, now seen corresponding path program 1 times [2025-01-10 06:59:51,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:51,325 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1105235979] [2025-01-10 06:59:51,325 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:51,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:51,331 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:51,340 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:51,341 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,341 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:51,341 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:51,343 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:51,350 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:51,350 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,350 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:51,351 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:51,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:51,352 INFO L85 PathProgramCache]: Analyzing trace with hash 889865249, now seen corresponding path program 1 times [2025-01-10 06:59:51,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:51,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1532248686] [2025-01-10 06:59:51,353 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:51,353 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:51,360 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-01-10 06:59:51,362 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-01-10 06:59:51,362 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,362 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:51,362 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:51,363 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-01-10 06:59:51,368 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-01-10 06:59:51,368 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,368 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:51,370 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:51,464 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:51,465 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:51,465 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:51,465 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:51,465 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-01-10 06:59:51,466 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:51,466 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:51,466 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:51,466 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-01-10 06:59:51,466 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:51,467 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:51,478 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,496 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,500 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,504 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,508 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,559 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:51,560 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-01-10 06:59:51,562 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:51,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:51,565 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:51,567 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2025-01-10 06:59:51,568 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:51,568 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:51,588 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2025-01-10 06:59:51,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:51,589 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:51,591 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:51,593 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2025-01-10 06:59:51,593 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-01-10 06:59:51,593 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:51,621 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-01-10 06:59:51,625 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:51,626 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:51,626 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:51,626 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:51,626 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:51,626 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-01-10 06:59:51,626 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:51,626 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:51,626 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:51,626 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2025-01-10 06:59:51,626 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:51,626 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:51,628 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,641 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,644 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,648 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,652 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:51,696 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:51,700 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-01-10 06:59:51,701 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:51,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:51,704 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:51,706 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2025-01-10 06:59:51,707 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-01-10 06:59:51,719 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:51,719 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:51,719 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:51,719 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:51,720 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:51,724 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:51,724 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:51,726 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-01-10 06:59:51,731 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-01-10 06:59:51,733 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-01-10 06:59:51,734 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:51,734 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:51,739 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:51,742 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2025-01-10 06:59:51,742 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-01-10 06:59:51,742 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-01-10 06:59:51,743 INFO L474 LassoAnalysis]: Proved termination. [2025-01-10 06:59:51,743 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 211 Supporting invariants [] [2025-01-10 06:59:51,749 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2025-01-10 06:59:51,752 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-01-10 06:59:51,786 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:51,798 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:51,803 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:51,803 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,803 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:51,805 INFO L256 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-01-10 06:59:51,806 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:51,819 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:51,829 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:51,829 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:51,829 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:51,831 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-01-10 06:59:51,832 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:51,891 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 06:59:51,920 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-01-10 06:59:51,923 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-01-10 06:59:52,020 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-01-10 06:59:52,023 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-01-10 06:59:52,028 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-01-10 06:59:52,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2025-01-10 06:59:52,036 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2025-01-10 06:59:52,038 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:52,038 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2025-01-10 06:59:52,039 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:52,039 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2025-01-10 06:59:52,039 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:52,039 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 39 transitions. [2025-01-10 06:59:52,041 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-01-10 06:59:52,045 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 19 states and 25 transitions. [2025-01-10 06:59:52,046 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2025-01-10 06:59:52,046 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2025-01-10 06:59:52,046 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2025-01-10 06:59:52,047 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-01-10 06:59:52,047 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2025-01-10 06:59:52,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2025-01-10 06:59:52,071 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2025-01-10 06:59:52,072 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-01-10 06:59:52,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2025-01-10 06:59:52,074 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2025-01-10 06:59:52,075 INFO L432 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2025-01-10 06:59:52,075 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-01-10 06:59:52,075 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2025-01-10 06:59:52,075 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-01-10 06:59:52,077 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-01-10 06:59:52,077 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-01-10 06:59:52,078 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 06:59:52,078 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-01-10 06:59:52,078 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;" >"#20#return;" [2025-01-10 06:59:52,078 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;" >"#20#return;" [2025-01-10 06:59:52,079 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:52,080 INFO L85 PathProgramCache]: Analyzing trace with hash 1612519912, now seen corresponding path program 1 times [2025-01-10 06:59:52,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:52,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1595988369] [2025-01-10 06:59:52,080 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:52,081 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:52,086 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-01-10 06:59:52,092 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-01-10 06:59:52,092 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:52,092 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:52,092 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:52,095 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-01-10 06:59:52,101 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-01-10 06:59:52,102 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:52,102 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:52,103 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:52,105 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:52,106 INFO L85 PathProgramCache]: Analyzing trace with hash -696734814, now seen corresponding path program 1 times [2025-01-10 06:59:52,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:52,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [604401478] [2025-01-10 06:59:52,106 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:52,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:52,112 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 06:59:52,119 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:52,119 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:52,119 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:52,120 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:52,121 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 06:59:52,124 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:52,124 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:52,124 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:52,125 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:52,126 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:52,126 INFO L85 PathProgramCache]: Analyzing trace with hash 1110240905, now seen corresponding path program 1 times [2025-01-10 06:59:52,126 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:52,126 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1153878297] [2025-01-10 06:59:52,127 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:52,127 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:52,131 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-01-10 06:59:52,138 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-01-10 06:59:52,138 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:52,139 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:52,139 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:52,141 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-01-10 06:59:52,148 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-01-10 06:59:52,149 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:52,149 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:52,151 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:52,324 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:52,325 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:52,325 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:52,325 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:52,325 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-01-10 06:59:52,325 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:52,325 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:52,325 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:52,325 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-01-10 06:59:52,325 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:52,325 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:52,326 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:52,329 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:52,332 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:52,348 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2025-01-10 06:59:52,408 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:52,409 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-01-10 06:59:52,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:52,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:52,412 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:52,415 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2025-01-10 06:59:52,416 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:52,416 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:52,430 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-01-10 06:59:52,431 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-01-10 06:59:52,438 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:52,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:52,439 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:52,442 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:52,444 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-01-10 06:59:52,445 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:52,445 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:52,463 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-01-10 06:59:52,464 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-01-10 06:59:52,471 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-01-10 06:59:52,472 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:52,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:52,474 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:52,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2025-01-10 06:59:52,478 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:52,478 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:52,511 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2025-01-10 06:59:52,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:52,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:52,514 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:52,515 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2025-01-10 06:59:52,515 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-01-10 06:59:52,515 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:53,100 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-01-10 06:59:53,114 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2025-01-10 06:59:53,114 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:53,114 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:53,114 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:53,114 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:53,114 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-01-10 06:59:53,114 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:53,114 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:53,114 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:53,114 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2025-01-10 06:59:53,114 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:53,114 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:53,115 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:53,118 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:53,129 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:53,170 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:53,170 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-01-10 06:59:53,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:53,170 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:53,174 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:53,175 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2025-01-10 06:59:53,177 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-01-10 06:59:53,190 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:53,190 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:53,190 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:53,190 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:53,190 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:53,191 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:53,191 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:53,194 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-01-10 06:59:53,200 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:53,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:53,200 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:53,202 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:53,203 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2025-01-10 06:59:53,204 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-01-10 06:59:53,216 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:53,216 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:53,216 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:53,216 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:53,216 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:53,218 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:53,218 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:53,222 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-01-10 06:59:53,225 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-01-10 06:59:53,225 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-01-10 06:59:53,226 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:53,226 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:53,228 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:53,230 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-01-10 06:59:53,231 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-01-10 06:59:53,231 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-01-10 06:59:53,231 INFO L474 LassoAnalysis]: Proved termination. [2025-01-10 06:59:53,231 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2025-01-10 06:59:53,236 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2025-01-10 06:59:53,238 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-01-10 06:59:53,241 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2025-01-10 06:59:53,254 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:53,261 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-01-10 06:59:53,274 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-01-10 06:59:53,275 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:53,275 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:53,275 INFO L256 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-01-10 06:59:53,276 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:53,377 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 06:59:53,392 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:53,392 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:53,392 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:53,393 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-01-10 06:59:53,394 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:53,498 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 06:59:53,499 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-01-10 06:59:53,499 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-01-10 06:59:53,691 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-01-10 06:59:53,692 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-01-10 06:59:53,693 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-01-10 06:59:53,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2025-01-10 06:59:53,694 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2025-01-10 06:59:53,695 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:53,695 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2025-01-10 06:59:53,695 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:53,695 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2025-01-10 06:59:53,696 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:53,696 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2025-01-10 06:59:53,699 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-01-10 06:59:53,702 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2025-01-10 06:59:53,702 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2025-01-10 06:59:53,703 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-01-10 06:59:53,703 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2025-01-10 06:59:53,703 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-01-10 06:59:53,703 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2025-01-10 06:59:53,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2025-01-10 06:59:53,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2025-01-10 06:59:53,707 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-01-10 06:59:53,708 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2025-01-10 06:59:53,708 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2025-01-10 06:59:53,708 INFO L432 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2025-01-10 06:59:53,708 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-01-10 06:59:53,709 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2025-01-10 06:59:53,710 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-01-10 06:59:53,710 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-01-10 06:59:53,710 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-01-10 06:59:53,710 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-10 06:59:53,711 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-01-10 06:59:53,711 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;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume !(~n > 100);" [2025-01-10 06:59:53,712 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret0 := mc91(11 + ~n);"< "~n := #in~n;" "assume !(~n > 100);" [2025-01-10 06:59:53,712 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:53,712 INFO L85 PathProgramCache]: Analyzing trace with hash -628486927, now seen corresponding path program 2 times [2025-01-10 06:59:53,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:53,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1496174308] [2025-01-10 06:59:53,713 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 06:59:53,713 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:53,717 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 13 statements into 2 equivalence classes. [2025-01-10 06:59:53,723 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 13 of 13 statements. [2025-01-10 06:59:53,723 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 06:59:53,723 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:53,723 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:53,725 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-01-10 06:59:53,728 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-01-10 06:59:53,728 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:53,728 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:53,730 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:53,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:53,730 INFO L85 PathProgramCache]: Analyzing trace with hash 48310, now seen corresponding path program 2 times [2025-01-10 06:59:53,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:53,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1950676237] [2025-01-10 06:59:53,731 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 06:59:53,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:53,733 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:53,735 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:53,735 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-01-10 06:59:53,735 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:53,735 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:53,735 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:53,736 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:53,736 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:53,736 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:53,742 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:53,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:53,743 INFO L85 PathProgramCache]: Analyzing trace with hash -1491580474, now seen corresponding path program 3 times [2025-01-10 06:59:53,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:53,743 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2003547754] [2025-01-10 06:59:53,743 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 06:59:53,743 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:53,747 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 16 statements into 4 equivalence classes. [2025-01-10 06:59:53,753 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 16 of 16 statements. [2025-01-10 06:59:53,753 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-01-10 06:59:53,753 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:53,894 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-01-10 06:59:53,895 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 06:59:53,895 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2003547754] [2025-01-10 06:59:53,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2003547754] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-10 06:59:53,895 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-10 06:59:53,896 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-01-10 06:59:53,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1076625580] [2025-01-10 06:59:53,896 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-10 06:59:53,946 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:53,946 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:53,946 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:53,946 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:53,946 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-01-10 06:59:53,946 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:53,946 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:53,946 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:53,947 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-01-10 06:59:53,947 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:53,947 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:53,947 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:53,958 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:53,961 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:53,967 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:54,004 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:54,004 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-01-10 06:59:54,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:54,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:54,007 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:54,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2025-01-10 06:59:54,010 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:54,010 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:54,037 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:54,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:54,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:54,040 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:54,041 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2025-01-10 06:59:54,042 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-01-10 06:59:54,042 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:54,389 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-01-10 06:59:54,398 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:54,398 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:54,398 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:54,398 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:54,398 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:54,399 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-01-10 06:59:54,399 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:54,399 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:54,399 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:54,399 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2025-01-10 06:59:54,399 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:54,399 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:54,400 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:54,406 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:54,409 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:54,411 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:54,441 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:54,441 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-01-10 06:59:54,441 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:54,441 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:54,443 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:54,446 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2025-01-10 06:59:54,447 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-01-10 06:59:54,459 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:54,460 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:54,460 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:54,460 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:54,460 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:54,461 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:54,462 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:54,465 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-01-10 06:59:54,467 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-01-10 06:59:54,467 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-01-10 06:59:54,467 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:54,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:54,469 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:54,470 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2025-01-10 06:59:54,470 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-01-10 06:59:54,470 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-01-10 06:59:54,470 INFO L474 LassoAnalysis]: Proved termination. [2025-01-10 06:59:54,470 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_~n) = -2*mc91_~n + 189 Supporting invariants [] [2025-01-10 06:59:54,476 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2025-01-10 06:59:54,477 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-01-10 06:59:54,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:54,507 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-01-10 06:59:54,542 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2025-01-10 06:59:54,547 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-01-10 06:59:54,548 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:54,548 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:54,549 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2025-01-10 06:59:54,550 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 06:59:54,551 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:54,622 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:54,626 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:54,627 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:54,627 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:54,627 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-01-10 06:59:54,628 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:54,657 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 06:59:54,658 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-01-10 06:59:54,658 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-01-10 06:59:54,728 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-01-10 06:59:54,731 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-01-10 06:59:54,732 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-01-10 06:59:54,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-01-10 06:59:54,732 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2025-01-10 06:59:54,732 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:54,732 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 06:59:54,743 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:54,753 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-01-10 06:59:54,767 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-01-10 06:59:54,768 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:54,768 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:54,769 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 06:59:54,771 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:54,834 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:54,839 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:54,839 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:54,839 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:54,839 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-01-10 06:59:54,840 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:54,863 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 06:59:54,864 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-01-10 06:59:54,864 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-01-10 06:59:54,915 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-01-10 06:59:54,918 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-01-10 06:59:54,918 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-01-10 06:59:54,919 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-01-10 06:59:54,919 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2025-01-10 06:59:54,919 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:54,919 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 06:59:54,927 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:54,936 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-01-10 06:59:54,950 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-01-10 06:59:54,950 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:54,950 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:54,951 INFO L256 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-10 06:59:54,952 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:55,014 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-01-10 06:59:55,019 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-01-10 06:59:55,019 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:55,019 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:55,020 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-01-10 06:59:55,020 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:55,043 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 06:59:55,044 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-01-10 06:59:55,044 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-01-10 06:59:55,112 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-01-10 06:59:55,113 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-01-10 06:59:55,114 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-01-10 06:59:55,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2025-01-10 06:59:55,114 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2025-01-10 06:59:55,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:55,115 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2025-01-10 06:59:55,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:55,115 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2025-01-10 06:59:55,115 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:55,115 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2025-01-10 06:59:55,118 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-01-10 06:59:55,119 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2025-01-10 06:59:55,119 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2025-01-10 06:59:55,120 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2025-01-10 06:59:55,120 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2025-01-10 06:59:55,120 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-01-10 06:59:55,120 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2025-01-10 06:59:55,120 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2025-01-10 06:59:55,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2025-01-10 06:59:55,124 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-01-10 06:59:55,125 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2025-01-10 06:59:55,125 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2025-01-10 06:59:55,125 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 06:59:55,126 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-10 06:59:55,127 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-01-10 06:59:55,129 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-01-10 06:59:55,232 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 06:59:55,232 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2025-01-10 06:59:55,233 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2025-01-10 06:59:55,234 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-01-10 06:59:55,238 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2025-01-10 06:59:55,238 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2025-01-10 06:59:55,239 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2025-01-10 06:59:55,239 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2025-01-10 06:59:55,239 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-01-10 06:59:55,239 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-01-10 06:59:55,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2025-01-10 06:59:55,242 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2025-01-10 06:59:55,243 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-01-10 06:59:55,244 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2025-01-10 06:59:55,244 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-01-10 06:59:55,244 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-01-10 06:59:55,245 INFO L432 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-01-10 06:59:55,245 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-01-10 06:59:55,245 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2025-01-10 06:59:55,246 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-01-10 06:59:55,246 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-01-10 06:59:55,246 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-01-10 06:59:55,247 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-01-10 06:59:55,247 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-01-10 06:59:55,247 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;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#22#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-01-10 06:59:55,247 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;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#22#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-01-10 06:59:55,252 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:55,252 INFO L85 PathProgramCache]: Analyzing trace with hash 1678623115, now seen corresponding path program 1 times [2025-01-10 06:59:55,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:55,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1598003276] [2025-01-10 06:59:55,252 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:55,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:55,255 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-01-10 06:59:55,262 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-01-10 06:59:55,263 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:55,263 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:55,263 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:55,264 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-01-10 06:59:55,273 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-01-10 06:59:55,273 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:55,273 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:55,275 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:55,275 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:55,276 INFO L85 PathProgramCache]: Analyzing trace with hash -2037590184, now seen corresponding path program 1 times [2025-01-10 06:59:55,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:55,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [503254554] [2025-01-10 06:59:55,276 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-10 06:59:55,276 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:55,279 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-01-10 06:59:55,287 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-01-10 06:59:55,288 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:55,288 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:55,288 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:55,289 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-01-10 06:59:55,293 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-01-10 06:59:55,293 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:55,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:55,298 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:55,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:55,299 INFO L85 PathProgramCache]: Analyzing trace with hash 1698366862, now seen corresponding path program 2 times [2025-01-10 06:59:55,299 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:55,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1579343589] [2025-01-10 06:59:55,299 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 06:59:55,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:55,304 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 41 statements into 2 equivalence classes. [2025-01-10 06:59:55,315 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 41 of 41 statements. [2025-01-10 06:59:55,315 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 06:59:55,315 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:55,519 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-01-10 06:59:55,520 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-10 06:59:55,520 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1579343589] [2025-01-10 06:59:55,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1579343589] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-10 06:59:55,520 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1703742350] [2025-01-10 06:59:55,520 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 06:59:55,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-10 06:59:55,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:55,523 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-10 06:59:55,525 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-01-10 06:59:55,546 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 41 statements into 2 equivalence classes. [2025-01-10 06:59:55,557 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 41 of 41 statements. [2025-01-10 06:59:55,558 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 06:59:55,558 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:55,558 INFO L256 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-01-10 06:59:55,560 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:55,598 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-01-10 06:59:55,599 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-10 06:59:55,833 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-01-10 06:59:55,834 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1703742350] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-10 06:59:55,834 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-10 06:59:55,834 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-01-10 06:59:55,834 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1934227331] [2025-01-10 06:59:55,834 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-10 06:59:56,009 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:56,009 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:56,009 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:56,009 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:56,009 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-01-10 06:59:56,010 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:56,010 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:56,010 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:56,010 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-01-10 06:59:56,010 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:56,010 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:56,011 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,015 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,017 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,019 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,021 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,045 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:56,045 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-01-10 06:59:56,045 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:56,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:56,048 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:56,051 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-01-10 06:59:56,054 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:56,054 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:56,076 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-01-10 06:59:56,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:56,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:56,079 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:56,080 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2025-01-10 06:59:56,081 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-01-10 06:59:56,081 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:56,092 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-01-10 06:59:56,098 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2025-01-10 06:59:56,098 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:56,098 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:56,098 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:56,098 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:56,098 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-01-10 06:59:56,098 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:56,099 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:56,099 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:56,099 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2025-01-10 06:59:56,099 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:56,099 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:56,099 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,104 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,106 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,108 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,110 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:56,133 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:56,133 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-01-10 06:59:56,133 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:56,133 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:56,135 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:56,136 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2025-01-10 06:59:56,137 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-01-10 06:59:56,147 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:56,147 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:56,147 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:56,147 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:56,147 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:56,148 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:56,148 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:56,152 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-01-10 06:59:56,155 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-01-10 06:59:56,155 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-01-10 06:59:56,155 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:56,155 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:56,157 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:56,159 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2025-01-10 06:59:56,160 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-01-10 06:59:56,160 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-01-10 06:59:56,161 INFO L474 LassoAnalysis]: Proved termination. [2025-01-10 06:59:56,161 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -1*mc91_#in~n + 90 Supporting invariants [] [2025-01-10 06:59:56,168 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2025-01-10 06:59:56,169 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-01-10 06:59:56,183 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:56,193 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-01-10 06:59:56,214 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-01-10 06:59:56,214 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:56,214 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:56,215 INFO L256 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-01-10 06:59:56,217 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:56,388 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-01-10 06:59:56,406 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-01-10 06:59:56,406 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:56,406 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:56,407 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-01-10 06:59:56,409 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:56,446 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:56,643 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-01-10 06:59:56,644 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-01-10 06:59:56,645 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-01-10 06:59:57,017 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-01-10 06:59:57,019 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-01-10 06:59:57,020 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-01-10 06:59:57,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2025-01-10 06:59:57,021 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2025-01-10 06:59:57,021 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:57,021 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 06:59:57,033 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:57,043 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-01-10 06:59:57,068 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-01-10 06:59:57,068 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:57,068 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:57,070 INFO L256 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-01-10 06:59:57,071 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:57,216 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-01-10 06:59:57,233 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-01-10 06:59:57,233 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:57,233 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:57,234 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-01-10 06:59:57,236 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:57,466 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-01-10 06:59:57,467 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 10 loop predicates [2025-01-10 06:59:57,467 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-01-10 06:59:57,802 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-01-10 06:59:57,802 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-01-10 06:59:57,803 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-01-10 06:59:57,804 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2025-01-10 06:59:57,804 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2025-01-10 06:59:57,804 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:57,804 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 06:59:57,815 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:57,825 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-01-10 06:59:57,842 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-01-10 06:59:57,842 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:57,842 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:57,843 INFO L256 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-01-10 06:59:57,844 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:57,983 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-01-10 06:59:58,000 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-01-10 06:59:58,000 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:58,000 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:58,003 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-01-10 06:59:58,005 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:58,168 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-10 06:59:58,168 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-01-10 06:59:58,169 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-01-10 06:59:58,673 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-01-10 06:59:58,674 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-01-10 06:59:58,674 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-01-10 06:59:58,675 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 50 transitions. [2025-01-10 06:59:58,675 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2025-01-10 06:59:58,675 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:58,675 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2025-01-10 06:59:58,676 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:58,676 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2025-01-10 06:59:58,676 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:58,676 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 325 states and 417 transitions. [2025-01-10 06:59:58,682 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 25 [2025-01-10 06:59:58,686 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 325 states to 169 states and 230 transitions. [2025-01-10 06:59:58,686 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2025-01-10 06:59:58,688 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2025-01-10 06:59:58,689 INFO L73 IsDeterministic]: Start isDeterministic. Operand 169 states and 230 transitions. [2025-01-10 06:59:58,689 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-01-10 06:59:58,689 INFO L218 hiAutomatonCegarLoop]: Abstraction has 169 states and 230 transitions. [2025-01-10 06:59:58,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states and 230 transitions. [2025-01-10 06:59:58,699 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 140. [2025-01-10 06:59:58,700 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-01-10 06:59:58,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 178 transitions. [2025-01-10 06:59:58,702 INFO L240 hiAutomatonCegarLoop]: Abstraction has 140 states and 178 transitions. [2025-01-10 06:59:58,702 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-10 06:59:58,702 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-01-10 06:59:58,702 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-01-10 06:59:58,702 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-01-10 06:59:58,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-10 06:59:58,869 INFO L93 Difference]: Finished difference Result 138 states and 163 transitions. [2025-01-10 06:59:58,869 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 138 states and 163 transitions. [2025-01-10 06:59:58,871 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-01-10 06:59:58,873 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 138 states to 101 states and 121 transitions. [2025-01-10 06:59:58,873 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2025-01-10 06:59:58,873 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2025-01-10 06:59:58,873 INFO L73 IsDeterministic]: Start isDeterministic. Operand 101 states and 121 transitions. [2025-01-10 06:59:58,873 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-01-10 06:59:58,873 INFO L218 hiAutomatonCegarLoop]: Abstraction has 101 states and 121 transitions. [2025-01-10 06:59:58,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states and 121 transitions. [2025-01-10 06:59:58,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-01-10 06:59:58,881 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-01-10 06:59:58,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 117 transitions. [2025-01-10 06:59:58,882 INFO L240 hiAutomatonCegarLoop]: Abstraction has 97 states and 117 transitions. [2025-01-10 06:59:58,883 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-01-10 06:59:58,883 INFO L432 stractBuchiCegarLoop]: Abstraction has 97 states and 117 transitions. [2025-01-10 06:59:58,883 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-01-10 06:59:58,883 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 97 states and 117 transitions. [2025-01-10 06:59:58,885 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-01-10 06:59:58,885 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-01-10 06:59:58,885 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-01-10 06:59:58,886 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2025-01-10 06:59:58,886 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-01-10 06:59:58,886 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;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< "~n := #in~n;" "assume ~n > 100;#res := ~n - 10;" "assume true;" >"#22#return;" "#res := #t~ret1;havoc #t~ret0;havoc #t~ret1;" "assume true;" >"#20#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;" >"#20#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;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-01-10 06:59:58,886 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;" >"#20#return;" "call #t~ret1 := mc91(#t~ret0);"< [2025-01-10 06:59:58,886 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:58,886 INFO L85 PathProgramCache]: Analyzing trace with hash -1106586231, now seen corresponding path program 3 times [2025-01-10 06:59:58,886 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:58,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2018324244] [2025-01-10 06:59:58,886 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-10 06:59:58,886 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:58,892 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 38 statements into 7 equivalence classes. [2025-01-10 06:59:58,907 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 38 of 38 statements. [2025-01-10 06:59:58,907 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-01-10 06:59:58,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:58,907 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:58,909 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-10 06:59:58,914 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-10 06:59:58,914 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:58,914 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:58,916 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:58,916 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:58,917 INFO L85 PathProgramCache]: Analyzing trace with hash 1861921664, now seen corresponding path program 2 times [2025-01-10 06:59:58,917 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:58,917 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [61191072] [2025-01-10 06:59:58,917 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-10 06:59:58,917 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:58,918 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-01-10 06:59:58,920 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:58,920 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-10 06:59:58,920 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:58,920 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:58,921 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 06:59:58,922 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:58,922 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:58,922 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:58,923 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:58,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:58,923 INFO L85 PathProgramCache]: Analyzing trace with hash 935033096, now seen corresponding path program 4 times [2025-01-10 06:59:58,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-10 06:59:58,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [113835857] [2025-01-10 06:59:58,923 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-10 06:59:58,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-10 06:59:58,926 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 46 statements into 2 equivalence classes. [2025-01-10 06:59:58,932 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 46 of 46 statements. [2025-01-10 06:59:58,934 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-01-10 06:59:58,934 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:58,934 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-10 06:59:58,936 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-01-10 06:59:58,942 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-01-10 06:59:58,942 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:58,942 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-10 06:59:58,944 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-10 06:59:59,015 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:59,015 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:59,015 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:59,015 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:59,016 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-01-10 06:59:59,016 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,016 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:59,016 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:59,016 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-01-10 06:59:59,016 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:59,016 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:59,016 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,018 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,020 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,026 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,027 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,051 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:59,051 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-01-10 06:59:59,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,053 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,054 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2025-01-10 06:59:59,055 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:59,055 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:59,065 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-01-10 06:59:59,065 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-01-10 06:59:59,071 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:59,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,073 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2025-01-10 06:59:59,075 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:59,075 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:59,085 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-01-10 06:59:59,085 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-01-10 06:59:59,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2025-01-10 06:59:59,091 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,091 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,093 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,093 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2025-01-10 06:59:59,094 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-01-10 06:59:59,094 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:59,110 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2025-01-10 06:59:59,110 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,110 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,112 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,113 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-01-10 06:59:59,113 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-01-10 06:59:59,113 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-01-10 06:59:59,125 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-01-10 06:59:59,132 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-01-10 06:59:59,132 INFO L204 LassoAnalysis]: Preferences: [2025-01-10 06:59:59,132 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-01-10 06:59:59,133 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-01-10 06:59:59,133 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-01-10 06:59:59,133 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-01-10 06:59:59,133 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,133 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-01-10 06:59:59,133 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-01-10 06:59:59,133 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2025-01-10 06:59:59,133 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-01-10 06:59:59,133 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-01-10 06:59:59,133 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,136 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,142 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,146 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-01-10 06:59:59,174 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-01-10 06:59:59,174 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-01-10 06:59:59,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,174 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,176 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,187 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-01-10 06:59:59,187 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-01-10 06:59:59,198 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:59,198 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:59,198 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:59,198 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:59,198 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:59,198 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:59,199 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:59,200 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-01-10 06:59:59,205 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2025-01-10 06:59:59,205 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,207 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,208 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2025-01-10 06:59:59,209 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-01-10 06:59:59,218 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:59,219 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:59,219 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:59,219 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:59,219 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:59,219 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:59,219 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:59,221 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-01-10 06:59:59,228 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2025-01-10 06:59:59,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,231 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,232 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2025-01-10 06:59:59,233 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-01-10 06:59:59,242 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-01-10 06:59:59,243 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-01-10 06:59:59,243 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-01-10 06:59:59,243 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-01-10 06:59:59,243 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-01-10 06:59:59,243 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-01-10 06:59:59,243 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-01-10 06:59:59,245 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-01-10 06:59:59,246 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-01-10 06:59:59,247 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-01-10 06:59:59,247 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-01-10 06:59:59,247 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-10 06:59:59,249 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-01-10 06:59:59,250 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2025-01-10 06:59:59,250 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-01-10 06:59:59,250 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-01-10 06:59:59,250 INFO L474 LassoAnalysis]: Proved termination. [2025-01-10 06:59:59,250 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 201 Supporting invariants [] [2025-01-10 06:59:59,256 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2025-01-10 06:59:59,258 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-01-10 06:59:59,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:59,285 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-10 06:59:59,319 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-10 06:59:59,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:59,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:59,321 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-01-10 06:59:59,323 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:59,522 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 06:59:59,530 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:59,530 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:59,530 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:59,531 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-01-10 06:59:59,532 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:59,618 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 06:59:59,618 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-01-10 06:59:59,618 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-01-10 06:59:59,690 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-01-10 06:59:59,691 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-01-10 06:59:59,692 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-01-10 06:59:59,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 15 transitions. [2025-01-10 06:59:59,692 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 15 transitions. Stem has 38 letters. Loop has 8 letters. [2025-01-10 06:59:59,692 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 06:59:59,692 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 06:59:59,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 06:59:59,721 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-10 06:59:59,750 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-10 06:59:59,751 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:59,751 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:59,752 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-01-10 06:59:59,753 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 06:59:59,888 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2025-01-10 06:59:59,951 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 06:59:59,959 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 06:59:59,960 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 06:59:59,960 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 06:59:59,961 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-01-10 06:59:59,961 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 07:00:00,045 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 07:00:00,046 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-01-10 07:00:00,046 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-01-10 07:00:00,238 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-01-10 07:00:00,240 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-01-10 07:00:00,241 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-01-10 07:00:00,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 20 transitions. [2025-01-10 07:00:00,241 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 20 transitions. Stem has 38 letters. Loop has 8 letters. [2025-01-10 07:00:00,241 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 07:00:00,241 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 07:00:00,253 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 07:00:00,270 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-10 07:00:00,305 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-10 07:00:00,305 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 07:00:00,305 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 07:00:00,308 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-01-10 07:00:00,309 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 07:00:00,506 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 07:00:00,515 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 07:00:00,515 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 07:00:00,515 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 07:00:00,516 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-01-10 07:00:00,517 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 07:00:00,593 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 07:00:00,593 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-01-10 07:00:00,594 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-01-10 07:00:00,680 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-01-10 07:00:00,681 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-01-10 07:00:00,682 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-01-10 07:00:00,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2025-01-10 07:00:00,682 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 38 letters. Loop has 8 letters. [2025-01-10 07:00:00,683 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 07:00:00,683 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-01-10 07:00:00,692 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-10 07:00:00,706 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-10 07:00:00,739 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-10 07:00:00,740 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 07:00:00,740 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 07:00:00,741 INFO L256 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-01-10 07:00:00,743 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 07:00:00,913 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-10 07:00:00,919 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-10 07:00:00,919 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-10 07:00:00,920 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-10 07:00:00,920 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-01-10 07:00:00,921 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-10 07:00:00,983 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-10 07:00:00,984 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-01-10 07:00:00,984 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-01-10 07:00:01,193 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-01-10 07:00:01,193 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-01-10 07:00:01,194 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-01-10 07:00:01,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 27 transitions. [2025-01-10 07:00:01,194 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 8 letters. [2025-01-10 07:00:01,195 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 07:00:01,195 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 46 letters. Loop has 8 letters. [2025-01-10 07:00:01,195 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 07:00:01,195 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 16 letters. [2025-01-10 07:00:01,195 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-01-10 07:00:01,195 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 182 states and 209 transitions. [2025-01-10 07:00:01,198 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-01-10 07:00:01,198 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 182 states to 0 states and 0 transitions. [2025-01-10 07:00:01,198 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-01-10 07:00:01,198 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-01-10 07:00:01,198 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-01-10 07:00:01,198 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-01-10 07:00:01,198 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-01-10 07:00:01,198 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-01-10 07:00:01,198 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-01-10 07:00:01,198 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-01-10 07:00:01,198 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-01-10 07:00:01,198 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-01-10 07:00:01,198 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-01-10 07:00:01,206 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 10.01 07:00:01 BoogieIcfgContainer [2025-01-10 07:00:01,206 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-01-10 07:00:01,207 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-01-10 07:00:01,207 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-01-10 07:00:01,207 INFO L274 PluginConnector]: Witness Printer initialized [2025-01-10 07:00:01,208 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 06:59:51" (3/4) ... [2025-01-10 07:00:01,210 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-01-10 07:00:01,210 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-01-10 07:00:01,211 INFO L158 Benchmark]: Toolchain (without parser) took 10448.77ms. Allocated memory is still 142.6MB. Free memory was 113.5MB in the beginning and 43.6MB in the end (delta: 69.9MB). Peak memory consumption was 69.5MB. Max. memory is 16.1GB. [2025-01-10 07:00:01,211 INFO L158 Benchmark]: CDTParser took 0.26ms. Allocated memory is still 201.3MB. Free memory is still 123.2MB. There was no memory consumed. Max. memory is 16.1GB. [2025-01-10 07:00:01,211 INFO L158 Benchmark]: CACSL2BoogieTranslator took 179.15ms. Allocated memory is still 142.6MB. Free memory was 113.0MB in the beginning and 103.5MB in the end (delta: 9.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-10 07:00:01,212 INFO L158 Benchmark]: Boogie Procedure Inliner took 21.89ms. Allocated memory is still 142.6MB. Free memory was 103.5MB in the beginning and 102.6MB in the end (delta: 989.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-10 07:00:01,212 INFO L158 Benchmark]: Boogie Preprocessor took 15.97ms. Allocated memory is still 142.6MB. Free memory was 102.6MB in the beginning and 102.1MB in the end (delta: 489.0kB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-10 07:00:01,212 INFO L158 Benchmark]: RCFGBuilder took 178.96ms. Allocated memory is still 142.6MB. Free memory was 101.6MB in the beginning and 92.2MB in the end (delta: 9.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-10 07:00:01,212 INFO L158 Benchmark]: BuchiAutomizer took 10043.99ms. Allocated memory is still 142.6MB. Free memory was 92.2MB in the beginning and 43.6MB in the end (delta: 48.6MB). Peak memory consumption was 52.7MB. Max. memory is 16.1GB. [2025-01-10 07:00:01,212 INFO L158 Benchmark]: Witness Printer took 3.52ms. Allocated memory is still 142.6MB. Free memory was 43.6MB in the beginning and 43.6MB in the end (delta: 27.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-10 07:00:01,214 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.26ms. Allocated memory is still 201.3MB. Free memory is still 123.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 179.15ms. Allocated memory is still 142.6MB. Free memory was 113.0MB in the beginning and 103.5MB in the end (delta: 9.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 21.89ms. Allocated memory is still 142.6MB. Free memory was 103.5MB in the beginning and 102.6MB in the end (delta: 989.1kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 15.97ms. Allocated memory is still 142.6MB. Free memory was 102.6MB in the beginning and 102.1MB in the end (delta: 489.0kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 178.96ms. Allocated memory is still 142.6MB. Free memory was 101.6MB in the beginning and 92.2MB in the end (delta: 9.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 10043.99ms. Allocated memory is still 142.6MB. Free memory was 92.2MB in the beginning and 43.6MB in the end (delta: 48.6MB). Peak memory consumption was 52.7MB. Max. memory is 16.1GB. * Witness Printer took 3.52ms. Allocated memory is still 142.6MB. Free memory was 43.6MB in the beginning and 43.6MB in the end (delta: 27.1kB). 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 9.9s and 6 iterations. TraceHistogramMax:8. Analysis of lassos took 3.7s. Construction of modules took 0.7s. Büchi inclusion checks took 5.3s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.1s 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, 262 SdHoareTripleChecker+Valid, 0.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 248 mSDsluCounter, 453 SdHoareTripleChecker+Invalid, 0.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 267 mSDsCounter, 201 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 994 IncrementalHoareTripleChecker+Invalid, 1195 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 201 mSolverCounterUnsat, 186 mSDtfsCounter, 994 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: 41ms VariablesStem: 0 VariablesLoop: 2 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.2s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-01-10 07:00:01,228 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-01-10 07:00:01,427 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE