./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/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.2.5-dev-84cfde4 [2024-10-12 00:11:54,277 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-12 00:11:54,349 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-10-12 00:11:54,353 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-12 00:11:54,354 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-12 00:11:54,384 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-12 00:11:54,385 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-12 00:11:54,386 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-12 00:11:54,387 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-12 00:11:54,388 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-12 00:11:54,389 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-12 00:11:54,389 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-12 00:11:54,390 INFO L153 SettingsManager]: * Use SBE=true [2024-10-12 00:11:54,390 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-12 00:11:54,392 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-12 00:11:54,393 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-12 00:11:54,393 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-12 00:11:54,393 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-12 00:11:54,393 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-12 00:11:54,394 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-12 00:11:54,394 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-12 00:11:54,394 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-12 00:11:54,395 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-12 00:11:54,395 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-12 00:11:54,395 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-12 00:11:54,395 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-12 00:11:54,396 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-12 00:11:54,396 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-12 00:11:54,396 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-12 00:11:54,396 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-12 00:11:54,396 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-12 00:11:54,397 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-12 00:11:54,397 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-12 00:11:54,397 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-12 00:11:54,397 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-12 00:11:54,398 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-12 00:11:54,399 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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-clean/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 [2024-10-12 00:11:54,686 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-12 00:11:54,716 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-12 00:11:54,719 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-12 00:11:54,720 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-12 00:11:54,721 INFO L274 PluginConnector]: CDTParser initialized [2024-10-12 00:11:54,722 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2024-10-12 00:11:56,223 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-12 00:11:56,425 INFO L384 CDTParser]: Found 1 translation units. [2024-10-12 00:11:56,426 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2024-10-12 00:11:56,434 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/7b59a3567/928d5370273e40d2992fc0a30753406b/FLAG41736b4e8 [2024-10-12 00:11:56,811 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/7b59a3567/928d5370273e40d2992fc0a30753406b [2024-10-12 00:11:56,814 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-12 00:11:56,815 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-12 00:11:56,817 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-12 00:11:56,817 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-12 00:11:56,823 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-12 00:11:56,823 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 12:11:56" (1/1) ... [2024-10-12 00:11:56,824 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1dc63947 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:56, skipping insertion in model container [2024-10-12 00:11:56,824 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 12:11:56" (1/1) ... [2024-10-12 00:11:56,853 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-12 00:11:57,024 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 00:11:57,039 INFO L200 MainTranslator]: Completed pre-run [2024-10-12 00:11:57,067 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 00:11:57,133 INFO L204 MainTranslator]: Completed translation [2024-10-12 00:11:57,134 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57 WrapperNode [2024-10-12 00:11:57,134 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-12 00:11:57,135 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-12 00:11:57,136 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-12 00:11:57,136 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-12 00:11:57,150 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,157 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,175 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-10-12 00:11:57,176 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-12 00:11:57,176 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-12 00:11:57,177 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-12 00:11:57,177 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-12 00:11:57,186 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,187 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,188 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,195 INFO L175 MemorySlicer]: No memory access in input program. [2024-10-12 00:11:57,195 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,196 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,197 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,199 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,199 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,200 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,201 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-12 00:11:57,203 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-12 00:11:57,203 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-12 00:11:57,203 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-12 00:11:57,204 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (1/1) ... [2024-10-12 00:11:57,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:57,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:57,238 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:57,240 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-10-12 00:11:57,289 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-12 00:11:57,289 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-12 00:11:57,289 INFO L130 BoogieDeclarations]: Found specification of procedure mc91 [2024-10-12 00:11:57,290 INFO L138 BoogieDeclarations]: Found implementation of procedure mc91 [2024-10-12 00:11:57,340 INFO L238 CfgBuilder]: Building ICFG [2024-10-12 00:11:57,343 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-12 00:11:57,432 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2024-10-12 00:11:57,433 INFO L287 CfgBuilder]: Performing block encoding [2024-10-12 00:11:57,443 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-12 00:11:57,444 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-12 00:11:57,444 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 12:11:57 BoogieIcfgContainer [2024-10-12 00:11:57,444 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-12 00:11:57,445 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-12 00:11:57,445 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-12 00:11:57,449 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-12 00:11:57,453 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-12 00:11:57,453 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 12.10 12:11:56" (1/3) ... [2024-10-12 00:11:57,454 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@264967e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 12.10 12:11:57, skipping insertion in model container [2024-10-12 00:11:57,454 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-12 00:11:57,454 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:11:57" (2/3) ... [2024-10-12 00:11:57,454 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@264967e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 12.10 12:11:57, skipping insertion in model container [2024-10-12 00:11:57,455 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-12 00:11:57,455 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 12:11:57" (3/3) ... [2024-10-12 00:11:57,456 INFO L332 chiAutomizerObserver]: Analyzing ICFG McCarthy91_Recursion.c [2024-10-12 00:11:57,518 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-12 00:11:57,519 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-12 00:11:57,519 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-12 00:11:57,519 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-12 00:11:57,519 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-12 00:11:57,519 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-12 00:11:57,519 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-12 00:11:57,519 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-12 00:11:57,523 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) [2024-10-12 00:11:57,539 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-12 00:11:57,540 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:11:57,540 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:11:57,545 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-12 00:11:57,545 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-12 00:11:57,545 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-12 00:11:57,545 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) [2024-10-12 00:11:57,547 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-12 00:11:57,547 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:11:57,547 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:11:57,548 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-12 00:11:57,548 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-12 00:11:57,554 INFO L745 eck$LassoCheckResult]: Stem: 12#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true; 5#L-1true 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; 2#L16true call main_#t~ret3#1 := mc91(main_~x~0#1);< 11#$Ultimate##0true [2024-10-12 00:11:57,554 INFO L747 eck$LassoCheckResult]: Loop: 11#$Ultimate##0true ~n := #in~n; 8#L10true assume !(~n > 100); 9#L11true call #t~ret0 := mc91(11 + ~n);< 11#$Ultimate##0true [2024-10-12 00:11:57,560 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:57,560 INFO L85 PathProgramCache]: Analyzing trace with hash 29870, now seen corresponding path program 1 times [2024-10-12 00:11:57,569 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:11:57,570 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [36105466] [2024-10-12 00:11:57,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:11:57,571 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:11:57,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:57,642 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:11:57,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:57,672 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:11:57,675 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:57,675 INFO L85 PathProgramCache]: Analyzing trace with hash 37870, now seen corresponding path program 1 times [2024-10-12 00:11:57,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:11:57,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2043139572] [2024-10-12 00:11:57,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:11:57,676 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:11:57,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:57,699 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:11:57,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:57,706 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:11:57,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:57,707 INFO L85 PathProgramCache]: Analyzing trace with hash 889865249, now seen corresponding path program 1 times [2024-10-12 00:11:57,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:11:57,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [476778902] [2024-10-12 00:11:57,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:11:57,708 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:11:57,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:57,714 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:11:57,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:57,720 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:11:57,790 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:11:57,791 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:11:57,791 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:11:57,791 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:11:57,791 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:11:57,791 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:57,792 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:11:57,792 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:11:57,792 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2024-10-12 00:11:57,792 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:11:57,792 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:11:57,803 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,817 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,820 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,823 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,826 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,880 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:11:57,882 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:11:57,884 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:57,884 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:57,887 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:57,888 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-10-12 00:11:57,889 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:11:57,889 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:11:57,919 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-10-12 00:11:57,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:57,920 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:57,921 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:57,922 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-10-12 00:11:57,923 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:11:57,923 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:11:57,959 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:11:57,964 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-10-12 00:11:57,965 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:11:57,965 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:11:57,966 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:11:57,966 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:11:57,966 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:11:57,966 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:57,966 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:11:57,966 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:11:57,966 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2024-10-12 00:11:57,966 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:11:57,966 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:11:57,968 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,976 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,980 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,985 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:57,989 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:58,026 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:11:58,030 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:11:58,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,032 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:58,034 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:58,036 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-10-12 00:11:58,037 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 [2024-10-12 00:11:58,051 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:11:58,052 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:11:58,052 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:11:58,052 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:11:58,053 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:11:58,055 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:11:58,055 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:11:58,058 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:11:58,063 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:11:58,064 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-12 00:11:58,065 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,065 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:58,084 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:58,085 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-10-12 00:11:58,086 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:11:58,086 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:11:58,087 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:11:58,088 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 211 Supporting invariants [] [2024-10-12 00:11:58,104 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-10-12 00:11:58,108 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:11:58,149 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:58,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:11:58,168 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-12 00:11:58,169 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:11:58,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:11:58,192 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:11:58,193 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:11:58,239 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:11:58,273 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 [2024-10-12 00:11:58,275 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) [2024-10-12 00:11:58,299 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-10-12 00:11:58,415 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. [2024-10-12 00:11:58,419 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 [2024-10-12 00:11:58,426 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) [2024-10-12 00:11:58,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2024-10-12 00:11:58,428 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2024-10-12 00:11:58,429 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:11:58,429 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2024-10-12 00:11:58,429 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:11:58,430 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2024-10-12 00:11:58,430 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:11:58,431 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 39 transitions. [2024-10-12 00:11:58,434 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-12 00:11:58,440 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 19 states and 25 transitions. [2024-10-12 00:11:58,441 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2024-10-12 00:11:58,443 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2024-10-12 00:11:58,443 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2024-10-12 00:11:58,445 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:11:58,446 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2024-10-12 00:11:58,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2024-10-12 00:11:58,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-10-12 00:11:58,471 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) [2024-10-12 00:11:58,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-10-12 00:11:58,473 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-10-12 00:11:58,473 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-10-12 00:11:58,473 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-12 00:11:58,474 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2024-10-12 00:11:58,474 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-12 00:11:58,475 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:11:58,475 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:11:58,476 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:11:58,476 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-10-12 00:11:58,476 INFO L745 eck$LassoCheckResult]: Stem: 114#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 115#L-1 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; 107#L16 call main_#t~ret3#1 := mc91(main_~x~0#1);< 109#$Ultimate##0 ~n := #in~n; 112#L10 assume !(~n > 100); 106#L11 call #t~ret0 := mc91(11 + ~n);< 108#$Ultimate##0 ~n := #in~n; 113#L10 assume ~n > 100;#res := ~n - 10; 110#mc91FINAL assume true; 111#mc91EXIT >#20#return; 104#L11-1 [2024-10-12 00:11:58,476 INFO L747 eck$LassoCheckResult]: Loop: 104#L11-1 call #t~ret1 := mc91(#t~ret0);< 105#$Ultimate##0 ~n := #in~n; 118#L10 assume !(~n > 100); 103#L11 call #t~ret0 := mc91(11 + ~n);< 105#$Ultimate##0 ~n := #in~n; 118#L10 assume ~n > 100;#res := ~n - 10; 117#mc91FINAL assume true; 119#mc91EXIT >#20#return; 104#L11-1 [2024-10-12 00:11:58,477 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:58,477 INFO L85 PathProgramCache]: Analyzing trace with hash 1612519912, now seen corresponding path program 1 times [2024-10-12 00:11:58,477 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:11:58,478 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1122178467] [2024-10-12 00:11:58,478 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:11:58,478 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:11:58,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:58,491 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:11:58,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:58,504 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:11:58,504 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:58,505 INFO L85 PathProgramCache]: Analyzing trace with hash -696734814, now seen corresponding path program 1 times [2024-10-12 00:11:58,505 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:11:58,507 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1182476139] [2024-10-12 00:11:58,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:11:58,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:11:58,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:58,518 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:11:58,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:58,531 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:11:58,534 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:11:58,534 INFO L85 PathProgramCache]: Analyzing trace with hash 1110240905, now seen corresponding path program 1 times [2024-10-12 00:11:58,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:11:58,535 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2121000685] [2024-10-12 00:11:58,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:11:58,535 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:11:58,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:58,561 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:11:58,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:11:58,580 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:11:58,754 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:11:58,754 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:11:58,755 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:11:58,755 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:11:58,755 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:11:58,755 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,755 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:11:58,755 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:11:58,756 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2024-10-12 00:11:58,756 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:11:58,756 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:11:58,757 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:58,760 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:58,763 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:11:58,814 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:11:58,814 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:11:58,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,814 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:58,816 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:58,819 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-10-12 00:11:58,820 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:11:58,820 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:11:58,833 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:11:58,834 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#t~ret1=0} Honda state: {mc91_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:11:58,849 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-10-12 00:11:58,850 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,850 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:58,852 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:58,854 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-10-12 00:11:58,855 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:11:58,856 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:11:58,874 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:11:58,875 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:11:58,906 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-12 00:11:58,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:58,912 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:58,920 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-10-12 00:11:58,920 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:11:58,920 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:11:58,965 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-10-12 00:11:58,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:11:58,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:11:58,967 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:11:58,968 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-10-12 00:11:58,971 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:11:58,971 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:11,037 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-10-12 00:12:11,050 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-10-12 00:12:11,051 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:11,051 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:11,051 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:11,051 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:11,052 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:12:11,052 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:11,052 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:11,052 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:11,052 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2024-10-12 00:12:11,052 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:11,052 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:11,054 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:11,057 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:11,072 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:11,117 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:11,117 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:12:11,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:11,118 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:11,122 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:11,124 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-10-12 00:12:11,125 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 [2024-10-12 00:12:11,139 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:12:11,139 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:12:11,139 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:12:11,139 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:12:11,139 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:12:11,140 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:12:11,140 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:12:11,144 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:12:11,159 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-10-12 00:12:11,160 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:11,160 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:11,161 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:11,162 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-10-12 00:12:11,163 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 [2024-10-12 00:12:11,173 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:12:11,174 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:12:11,174 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:12:11,174 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:12:11,174 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:12:11,176 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:12:11,176 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:12:11,180 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:12:11,185 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:12:11,185 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-12 00:12:11,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:11,186 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:11,187 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:11,190 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-10-12 00:12:11,190 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:12:11,190 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:12:11,190 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:12:11,191 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2024-10-12 00:12:11,203 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-10-12 00:12:11,205 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:12:11,208 WARN L953 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2024-10-12 00:12:11,220 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:11,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:11,252 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-12 00:12:11,254 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:11,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:11,381 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-12 00:12:11,382 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:11,506 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:11,507 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 [2024-10-12 00:12:11,507 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) [2024-10-12 00:12:11,725 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-10-12 00:12:11,748 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. [2024-10-12 00:12:11,770 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 [2024-10-12 00:12:11,771 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) [2024-10-12 00:12:11,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-10-12 00:12:11,777 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2024-10-12 00:12:11,778 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:11,778 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2024-10-12 00:12:11,778 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:11,778 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2024-10-12 00:12:11,778 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:11,779 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2024-10-12 00:12:11,790 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-10-12 00:12:11,796 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2024-10-12 00:12:11,801 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-10-12 00:12:11,805 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2024-10-12 00:12:11,806 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2024-10-12 00:12:11,806 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:12:11,806 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2024-10-12 00:12:11,806 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2024-10-12 00:12:11,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2024-10-12 00:12:11,818 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) [2024-10-12 00:12:11,821 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2024-10-12 00:12:11,823 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-10-12 00:12:11,823 INFO L425 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-10-12 00:12:11,824 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-12 00:12:11,824 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2024-10-12 00:12:11,825 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-10-12 00:12:11,825 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:12:11,825 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:12:11,826 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:12:11,826 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-12 00:12:11,827 INFO L745 eck$LassoCheckResult]: Stem: 306#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 307#L-1 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; 288#L16 call main_#t~ret3#1 := mc91(main_~x~0#1);< 289#$Ultimate##0 ~n := #in~n; 302#L10 assume !(~n > 100); 295#L11 call #t~ret0 := mc91(11 + ~n);< 296#$Ultimate##0 ~n := #in~n; 305#L10 assume ~n > 100;#res := ~n - 10; 321#mc91FINAL assume true; 319#mc91EXIT >#20#return; 293#L11-1 call #t~ret1 := mc91(#t~ret0);< 314#$Ultimate##0 ~n := #in~n; 323#L10 assume !(~n > 100); 290#L11 [2024-10-12 00:12:11,827 INFO L747 eck$LassoCheckResult]: Loop: 290#L11 call #t~ret0 := mc91(11 + ~n);< 291#$Ultimate##0 ~n := #in~n; 315#L10 assume !(~n > 100); 290#L11 [2024-10-12 00:12:11,827 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:11,827 INFO L85 PathProgramCache]: Analyzing trace with hash -628486927, now seen corresponding path program 2 times [2024-10-12 00:12:11,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:11,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1869286152] [2024-10-12 00:12:11,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:11,828 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:11,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:11,841 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:12:11,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:11,848 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:12:11,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:11,849 INFO L85 PathProgramCache]: Analyzing trace with hash 48310, now seen corresponding path program 2 times [2024-10-12 00:12:11,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:11,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1437769792] [2024-10-12 00:12:11,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:11,850 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:11,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:11,853 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:12:11,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:11,856 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:12:11,856 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:11,857 INFO L85 PathProgramCache]: Analyzing trace with hash -1491580474, now seen corresponding path program 3 times [2024-10-12 00:12:11,857 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:11,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524092401] [2024-10-12 00:12:11,857 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:11,857 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:11,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:12,016 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-12 00:12:12,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:12,064 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-12 00:12:12,065 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:12:12,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1524092401] [2024-10-12 00:12:12,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1524092401] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 00:12:12,066 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 00:12:12,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-12 00:12:12,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1038237117] [2024-10-12 00:12:12,067 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 00:12:12,120 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:12,120 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:12,120 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:12,121 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:12,121 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:12:12,121 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:12,121 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:12,121 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:12,121 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2024-10-12 00:12:12,122 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:12,122 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:12,123 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:12,136 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:12,138 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:12,140 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:12,166 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:12,166 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:12:12,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:12,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:12,168 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:12,170 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-10-12 00:12:12,171 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:12:12,171 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:12,213 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-10-12 00:12:12,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:12,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:12,215 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:12,217 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-10-12 00:12:12,218 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:12:12,218 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:24,397 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-10-12 00:12:24,410 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-10-12 00:12:24,411 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:24,411 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:24,411 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:24,411 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:24,411 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:12:24,411 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:24,411 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:24,411 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:24,411 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2024-10-12 00:12:24,411 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:24,411 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:24,412 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:24,422 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:24,424 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:24,426 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:24,455 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:24,456 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:12:24,456 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:24,456 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:24,459 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:24,460 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-10-12 00:12:24,461 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 [2024-10-12 00:12:24,475 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:12:24,475 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:12:24,475 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:12:24,475 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:12:24,475 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:12:24,478 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:12:24,478 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:12:24,482 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:12:24,486 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:12:24,486 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-12 00:12:24,487 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:24,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:24,489 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:24,490 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-10-12 00:12:24,491 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:12:24,491 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:12:24,491 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:12:24,491 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_~n) = -2*mc91_~n + 189 Supporting invariants [] [2024-10-12 00:12:24,508 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-10-12 00:12:24,509 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:12:24,520 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:24,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:24,544 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-12 00:12:24,546 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:24,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:24,637 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:12:24,638 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:24,668 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:24,668 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 [2024-10-12 00:12:24,669 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) [2024-10-12 00:12:24,746 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. [2024-10-12 00:12:24,749 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 [2024-10-12 00:12:24,750 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) [2024-10-12 00:12:24,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-12 00:12:24,750 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-10-12 00:12:24,751 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:24,751 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:12:24,763 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:24,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:24,786 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-12 00:12:24,787 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:24,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:24,868 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:12:24,869 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:24,897 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:24,898 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 [2024-10-12 00:12:24,898 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) [2024-10-12 00:12:24,963 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. [2024-10-12 00:12:24,965 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 [2024-10-12 00:12:24,966 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) [2024-10-12 00:12:24,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-12 00:12:24,966 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-10-12 00:12:24,966 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:24,966 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:12:24,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:24,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,000 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-12 00:12:25,001 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:25,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,065 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:12:25,065 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:25,093 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:25,094 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 [2024-10-12 00:12:25,094 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) [2024-10-12 00:12:25,179 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. [2024-10-12 00:12:25,180 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 [2024-10-12 00:12:25,180 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) [2024-10-12 00:12:25,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2024-10-12 00:12:25,181 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2024-10-12 00:12:25,182 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:25,182 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2024-10-12 00:12:25,182 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:25,182 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2024-10-12 00:12:25,182 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:25,183 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2024-10-12 00:12:25,185 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2024-10-12 00:12:25,187 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2024-10-12 00:12:25,188 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-10-12 00:12:25,188 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-10-12 00:12:25,188 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2024-10-12 00:12:25,188 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:12:25,188 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2024-10-12 00:12:25,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2024-10-12 00:12:25,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2024-10-12 00:12:25,195 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) [2024-10-12 00:12:25,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2024-10-12 00:12:25,198 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2024-10-12 00:12:25,198 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:12:25,201 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-12 00:12:25,202 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-10-12 00:12:25,203 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) [2024-10-12 00:12:25,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:12:25,306 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2024-10-12 00:12:25,306 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2024-10-12 00:12:25,308 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-10-12 00:12:25,312 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2024-10-12 00:12:25,312 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2024-10-12 00:12:25,312 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-10-12 00:12:25,313 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2024-10-12 00:12:25,313 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:12:25,313 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-10-12 00:12:25,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2024-10-12 00:12:25,333 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-10-12 00:12:25,334 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) [2024-10-12 00:12:25,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-10-12 00:12:25,335 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-10-12 00:12:25,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-12 00:12:25,339 INFO L425 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-10-12 00:12:25,339 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-12 00:12:25,339 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2024-10-12 00:12:25,341 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-10-12 00:12:25,341 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:12:25,341 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:12:25,342 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-10-12 00:12:25,342 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-10-12 00:12:25,344 INFO L745 eck$LassoCheckResult]: Stem: 852#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 853#L-1 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; 834#L16 call main_#t~ret3#1 := mc91(main_~x~0#1);< 836#$Ultimate##0 ~n := #in~n; 859#L10 assume !(~n > 100); 833#L11 call #t~ret0 := mc91(11 + ~n);< 835#$Ultimate##0 ~n := #in~n; 868#L10 assume !(~n > 100); 864#L11 call #t~ret0 := mc91(11 + ~n);< 866#$Ultimate##0 ~n := #in~n; 869#L10 assume ~n > 100;#res := ~n - 10; 867#mc91FINAL assume true; 865#mc91EXIT >#20#return; 846#L11-1 call #t~ret1 := mc91(#t~ret0);< 844#$Ultimate##0 ~n := #in~n; 847#L10 assume ~n > 100;#res := ~n - 10; 858#mc91FINAL assume true; 884#mc91EXIT >#22#return; 860#L11-2 #res := #t~ret1;havoc #t~ret0;havoc #t~ret1; 882#mc91FINAL assume true; 881#mc91EXIT >#20#return; 838#L11-1 call #t~ret1 := mc91(#t~ret0);< 856#$Ultimate##0 [2024-10-12 00:12:25,344 INFO L747 eck$LassoCheckResult]: Loop: 856#$Ultimate##0 ~n := #in~n; 874#L10 assume !(~n > 100); 849#L11 call #t~ret0 := mc91(11 + ~n);< 848#$Ultimate##0 ~n := #in~n; 851#L10 assume !(~n > 100); 850#L11 call #t~ret0 := mc91(11 + ~n);< 870#$Ultimate##0 ~n := #in~n; 880#L10 assume ~n > 100;#res := ~n - 10; 878#mc91FINAL assume true; 876#mc91EXIT >#20#return; 830#L11-1 call #t~ret1 := mc91(#t~ret0);< 873#$Ultimate##0 ~n := #in~n; 871#L10 assume ~n > 100;#res := ~n - 10; 872#mc91FINAL assume true; 883#mc91EXIT >#22#return; 860#L11-2 #res := #t~ret1;havoc #t~ret0;havoc #t~ret1; 882#mc91FINAL assume true; 881#mc91EXIT >#20#return; 839#L11-1 call #t~ret1 := mc91(#t~ret0);< 856#$Ultimate##0 [2024-10-12 00:12:25,345 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:25,345 INFO L85 PathProgramCache]: Analyzing trace with hash 1678623115, now seen corresponding path program 1 times [2024-10-12 00:12:25,345 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:25,345 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1596231621] [2024-10-12 00:12:25,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:25,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:25,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:25,354 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:12:25,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:25,361 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:12:25,362 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:25,362 INFO L85 PathProgramCache]: Analyzing trace with hash -2037590184, now seen corresponding path program 1 times [2024-10-12 00:12:25,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:25,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2017034133] [2024-10-12 00:12:25,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:25,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:25,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:25,382 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:12:25,389 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-10-12 00:12:25,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:25,397 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:12:25,400 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:25,400 INFO L85 PathProgramCache]: Analyzing trace with hash 1698366862, now seen corresponding path program 2 times [2024-10-12 00:12:25,400 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:25,400 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1063534922] [2024-10-12 00:12:25,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:25,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:25,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,548 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-12 00:12:25,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,593 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-12 00:12:25,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,598 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 00:12:25,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,619 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-12 00:12:25,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-12 00:12:25,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,731 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 00:12:25,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:25,736 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-12 00:12:25,736 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:12:25,736 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1063534922] [2024-10-12 00:12:25,736 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1063534922] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 00:12:25,736 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [898417998] [2024-10-12 00:12:25,736 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 00:12:25,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 00:12:25,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:25,738 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 00:12:25,740 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-10-12 00:12:25,781 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 00:12:25,781 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 00:12:25,782 INFO L255 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-12 00:12:25,785 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:25,836 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-12 00:12:25,836 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 00:12:26,083 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-12 00:12:26,083 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [898417998] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 00:12:26,083 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 00:12:26,084 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 17 [2024-10-12 00:12:26,084 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [108342117] [2024-10-12 00:12:26,084 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 00:12:26,256 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:26,256 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:26,256 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:26,256 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:26,257 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:12:26,257 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:26,257 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:26,257 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:26,257 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2024-10-12 00:12:26,257 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:26,257 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:26,258 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,267 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,272 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,274 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,276 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,299 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:26,299 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:12:26,299 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:26,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:26,301 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:26,303 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-10-12 00:12:26,304 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:12:26,304 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:26,342 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-10-12 00:12:26,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:26,343 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:26,345 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:26,347 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-10-12 00:12:26,348 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:12:26,348 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:26,364 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:12:26,379 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-10-12 00:12:26,379 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:26,379 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:26,379 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:26,379 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:26,380 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:12:26,380 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:26,380 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:26,380 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:26,380 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2024-10-12 00:12:26,380 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:26,380 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:26,381 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,385 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,388 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,389 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,391 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:26,416 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:26,416 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:12:26,416 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:26,416 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:26,418 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:26,420 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-10-12 00:12:26,421 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 [2024-10-12 00:12:26,433 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:12:26,433 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:12:26,434 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:12:26,434 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:12:26,434 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:12:26,437 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:12:26,437 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:12:26,440 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:12:26,443 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:12:26,443 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-12 00:12:26,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:26,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:26,445 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:26,446 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-10-12 00:12:26,447 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:12:26,447 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:12:26,447 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:12:26,448 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -1*mc91_#in~n + 90 Supporting invariants [] [2024-10-12 00:12:26,462 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-10-12 00:12:26,463 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:12:26,478 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:26,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:26,510 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-12 00:12:26,512 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:26,614 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-10-12 00:12:26,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:26,731 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-12 00:12:26,733 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:26,934 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 00:12:26,935 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 [2024-10-12 00:12:26,936 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) [2024-10-12 00:12:27,345 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. [2024-10-12 00:12:27,346 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 [2024-10-12 00:12:27,347 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) [2024-10-12 00:12:27,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-10-12 00:12:27,347 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-10-12 00:12:27,348 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:27,348 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:12:27,358 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:27,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:27,390 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-12 00:12:27,392 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:27,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:27,556 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-12 00:12:27,558 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:27,770 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 00:12:27,771 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 [2024-10-12 00:12:27,771 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) [2024-10-12 00:12:28,116 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. [2024-10-12 00:12:28,116 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 [2024-10-12 00:12:28,117 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) [2024-10-12 00:12:28,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-10-12 00:12:28,118 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-10-12 00:12:28,118 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:28,118 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:12:28,132 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:28,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:28,160 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-12 00:12:28,161 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:28,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:28,325 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-12 00:12:28,327 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:28,521 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 00:12:28,522 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 10 loop predicates [2024-10-12 00:12:28,522 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) [2024-10-12 00:12:29,230 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 431 states and 531 transitions. Complement of second has 224 states. [2024-10-12 00:12:29,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 21 states 2 stem states 18 non-accepting loop states 1 accepting loop states [2024-10-12 00:12:29,232 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) [2024-10-12 00:12:29,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 50 transitions. [2024-10-12 00:12:29,234 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2024-10-12 00:12:29,234 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:29,234 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2024-10-12 00:12:29,235 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:29,235 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2024-10-12 00:12:29,236 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:29,236 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 431 states and 531 transitions. [2024-10-12 00:12:29,254 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 29 [2024-10-12 00:12:29,262 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 431 states to 203 states and 269 transitions. [2024-10-12 00:12:29,266 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 95 [2024-10-12 00:12:29,267 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 106 [2024-10-12 00:12:29,267 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 269 transitions. [2024-10-12 00:12:29,268 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:12:29,268 INFO L218 hiAutomatonCegarLoop]: Abstraction has 203 states and 269 transitions. [2024-10-12 00:12:29,268 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 269 transitions. [2024-10-12 00:12:29,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 157. [2024-10-12 00:12:29,284 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 97 states have (on average 1.092783505154639) internal successors, (106), 99 states have internal predecessors, (106), 35 states have call successors, (45), 29 states have call predecessors, (45), 25 states have return successors, (47), 28 states have call predecessors, (47), 32 states have call successors, (47) [2024-10-12 00:12:29,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 198 transitions. [2024-10-12 00:12:29,286 INFO L240 hiAutomatonCegarLoop]: Abstraction has 157 states and 198 transitions. [2024-10-12 00:12:29,286 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:12:29,287 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-12 00:12:29,287 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=228, Unknown=0, NotChecked=0, Total=272 [2024-10-12 00:12:29,287 INFO L87 Difference]: Start difference. First operand 157 states and 198 transitions. Second operand has 17 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 10 states have internal predecessors, (24), 8 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 7 states have call predecessors, (10), 5 states have call successors, (10) [2024-10-12 00:12:29,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:12:29,472 INFO L93 Difference]: Finished difference Result 159 states and 188 transitions. [2024-10-12 00:12:29,472 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 159 states and 188 transitions. [2024-10-12 00:12:29,478 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-10-12 00:12:29,480 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 159 states to 104 states and 123 transitions. [2024-10-12 00:12:29,482 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2024-10-12 00:12:29,483 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-12 00:12:29,483 INFO L73 IsDeterministic]: Start isDeterministic. Operand 104 states and 123 transitions. [2024-10-12 00:12:29,483 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:12:29,483 INFO L218 hiAutomatonCegarLoop]: Abstraction has 104 states and 123 transitions. [2024-10-12 00:12:29,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states and 123 transitions. [2024-10-12 00:12:29,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 100. [2024-10-12 00:12:29,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 63 states have (on average 1.0476190476190477) internal successors, (66), 64 states have internal predecessors, (66), 21 states have call successors, (28), 20 states have call predecessors, (28), 16 states have return successors, (25), 15 states have call predecessors, (25), 18 states have call successors, (25) [2024-10-12 00:12:29,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 119 transitions. [2024-10-12 00:12:29,492 INFO L240 hiAutomatonCegarLoop]: Abstraction has 100 states and 119 transitions. [2024-10-12 00:12:29,493 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-12 00:12:29,493 INFO L425 stractBuchiCegarLoop]: Abstraction has 100 states and 119 transitions. [2024-10-12 00:12:29,493 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-12 00:12:29,493 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 100 states and 119 transitions. [2024-10-12 00:12:29,495 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-10-12 00:12:29,495 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:12:29,495 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:12:29,497 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1] [2024-10-12 00:12:29,497 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-10-12 00:12:29,498 INFO L745 eck$LassoCheckResult]: Stem: 3030#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 3031#L-1 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; 3009#L16 call main_#t~ret3#1 := mc91(main_~x~0#1);< 3010#$Ultimate##0 ~n := #in~n; 3048#L10 assume !(~n > 100); 3049#L11 call #t~ret0 := mc91(11 + ~n);< 3050#$Ultimate##0 ~n := #in~n; 3052#L10 assume !(~n > 100); 3051#L11 call #t~ret0 := mc91(11 + ~n);< 3068#$Ultimate##0 ~n := #in~n; 3070#L10 assume ~n > 100;#res := ~n - 10; 3069#mc91FINAL assume true; 3067#mc91EXIT >#20#return; 3064#L11-1 call #t~ret1 := mc91(#t~ret0);< 3066#$Ultimate##0 ~n := #in~n; 3072#L10 assume ~n > 100;#res := ~n - 10; 3071#mc91FINAL assume true; 3063#mc91EXIT >#22#return; 3061#L11-2 #res := #t~ret1;havoc #t~ret0;havoc #t~ret1; 3059#mc91FINAL assume true; 3058#mc91EXIT >#20#return; 3053#L11-1 call #t~ret1 := mc91(#t~ret0);< 3057#$Ultimate##0 ~n := #in~n; 3055#L10 assume !(~n > 100); 3015#L11 call #t~ret0 := mc91(11 + ~n);< 3017#$Ultimate##0 ~n := #in~n; 3060#L10 assume !(~n > 100); 3014#L11 call #t~ret0 := mc91(11 + ~n);< 3016#$Ultimate##0 ~n := #in~n; 3108#L10 assume ~n > 100;#res := ~n - 10; 3104#mc91FINAL assume true; 3103#mc91EXIT >#20#return; 3012#L11-1 [2024-10-12 00:12:29,498 INFO L747 eck$LassoCheckResult]: Loop: 3012#L11-1 call #t~ret1 := mc91(#t~ret0);< 3036#$Ultimate##0 ~n := #in~n; 3105#L10 assume !(~n > 100); 3011#L11 call #t~ret0 := mc91(11 + ~n);< 3013#$Ultimate##0 ~n := #in~n; 3107#L10 assume ~n > 100;#res := ~n - 10; 3106#mc91FINAL assume true; 3102#mc91EXIT >#20#return; 3012#L11-1 [2024-10-12 00:12:29,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:29,498 INFO L85 PathProgramCache]: Analyzing trace with hash -1028640846, now seen corresponding path program 3 times [2024-10-12 00:12:29,498 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:29,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [480636579] [2024-10-12 00:12:29,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:29,499 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:29,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:29,562 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-12 00:12:29,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:29,592 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-12 00:12:29,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:29,596 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-12 00:12:29,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:29,604 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-12 00:12:29,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:29,607 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 28 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-12 00:12:29,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:12:29,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [480636579] [2024-10-12 00:12:29,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [480636579] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 00:12:29,608 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [872337732] [2024-10-12 00:12:29,608 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-12 00:12:29,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 00:12:29,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:29,610 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 00:12:29,612 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-10-12 00:12:29,646 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-10-12 00:12:29,647 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 00:12:29,647 INFO L255 TraceCheckSpWp]: Trace formula consists of 61 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-12 00:12:29,649 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:29,667 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 00:12:29,667 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 00:12:29,667 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [872337732] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 00:12:29,667 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-12 00:12:29,668 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 9 [2024-10-12 00:12:29,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [483919993] [2024-10-12 00:12:29,668 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 00:12:29,668 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-12 00:12:29,669 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:29,669 INFO L85 PathProgramCache]: Analyzing trace with hash -696734814, now seen corresponding path program 2 times [2024-10-12 00:12:29,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:12:29,669 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2009114278] [2024-10-12 00:12:29,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:12:29,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:12:29,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:29,672 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:12:29,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:12:29,674 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:12:29,756 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:29,756 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:29,756 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:29,756 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:29,756 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:12:29,756 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:29,756 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:29,756 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:29,757 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2024-10-12 00:12:29,757 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:29,757 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:29,757 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:29,759 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:29,765 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:29,801 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:29,801 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:12:29,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:29,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:29,802 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:29,803 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-10-12 00:12:29,804 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:12:29,804 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:29,815 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:12:29,816 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:12:29,826 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-10-12 00:12:29,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:29,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:29,828 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:29,829 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-10-12 00:12:29,830 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:12:29,830 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:29,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-10-12 00:12:29,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:29,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:29,872 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:29,873 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-10-12 00:12:29,873 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:12:29,874 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:12:42,166 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-10-12 00:12:42,185 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2024-10-12 00:12:42,185 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:12:42,185 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:12:42,185 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:12:42,185 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:12:42,185 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:12:42,185 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:42,185 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:12:42,186 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:12:42,186 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2024-10-12 00:12:42,186 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:12:42,186 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:12:42,186 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:42,193 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:42,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:12:42,220 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:12:42,220 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:12:42,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:42,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:42,222 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:42,223 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-10-12 00:12:42,226 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 [2024-10-12 00:12:42,237 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:12:42,238 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:12:42,238 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:12:42,238 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:12:42,238 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:12:42,240 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:12:42,240 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:12:42,243 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:12:42,245 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:12:42,245 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-12 00:12:42,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:12:42,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:12:42,248 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:12:42,249 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-10-12 00:12:42,250 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:12:42,250 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:12:42,250 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:12:42,250 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2024-10-12 00:12:42,265 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-10-12 00:12:42,267 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:12:42,268 WARN L953 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2024-10-12 00:12:42,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:42,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:42,316 INFO L255 TraceCheckSpWp]: Trace formula consists of 269 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-12 00:12:42,318 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:42,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:42,498 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-12 00:12:42,499 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:42,569 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:42,569 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 [2024-10-12 00:12:42,569 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 00:12:42,690 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 139 states and 161 transitions. Complement of second has 24 states. [2024-10-12 00:12:42,690 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 [2024-10-12 00:12:42,691 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 00:12:42,691 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-10-12 00:12:42,691 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2024-10-12 00:12:42,691 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:42,691 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:12:42,702 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:42,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:42,739 INFO L255 TraceCheckSpWp]: Trace formula consists of 269 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-12 00:12:42,741 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:42,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:42,905 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-12 00:12:42,906 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:42,984 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:42,985 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 [2024-10-12 00:12:42,985 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 00:12:42,993 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-10-12 00:12:43,101 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 139 states and 161 transitions. Complement of second has 24 states. [2024-10-12 00:12:43,102 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 [2024-10-12 00:12:43,103 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 00:12:43,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-10-12 00:12:43,103 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2024-10-12 00:12:43,104 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:43,104 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:12:43,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:12:43,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:43,149 INFO L255 TraceCheckSpWp]: Trace formula consists of 269 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-12 00:12:43,150 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:43,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:12:43,309 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-12 00:12:43,310 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:12:43,375 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:12:43,376 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 [2024-10-12 00:12:43,376 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 00:12:43,494 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 181 states and 211 transitions. Complement of second has 27 states. [2024-10-12 00:12:43,496 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 [2024-10-12 00:12:43,496 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 00:12:43,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 21 transitions. [2024-10-12 00:12:43,497 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 8 letters. [2024-10-12 00:12:43,497 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:43,497 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 40 letters. Loop has 8 letters. [2024-10-12 00:12:43,498 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:43,498 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 16 letters. [2024-10-12 00:12:43,499 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:12:43,499 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 181 states and 211 transitions. [2024-10-12 00:12:43,501 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-12 00:12:43,501 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 181 states to 0 states and 0 transitions. [2024-10-12 00:12:43,501 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-12 00:12:43,501 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-12 00:12:43,501 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-12 00:12:43,501 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-12 00:12:43,501 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:12:43,501 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:12:43,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:12:43,502 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-12 00:12:43,502 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-12 00:12:43,502 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 5 states have internal predecessors, (16), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 00:12:43,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:12:43,502 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-10-12 00:12:43,502 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-10-12 00:12:43,502 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-12 00:12:43,502 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-10-12 00:12:43,503 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-12 00:12:43,503 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-12 00:12:43,503 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-12 00:12:43,503 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-12 00:12:43,503 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:12:43,503 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:12:43,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-12 00:12:43,503 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:12:43,503 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-12 00:12:43,503 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-12 00:12:43,503 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-12 00:12:43,503 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-12 00:12:43,510 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 12.10 12:12:43 BoogieIcfgContainer [2024-10-12 00:12:43,511 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-12 00:12:43,511 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-12 00:12:43,511 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-12 00:12:43,512 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-12 00:12:43,512 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 12:11:57" (3/4) ... [2024-10-12 00:12:43,514 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-12 00:12:43,515 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-12 00:12:43,516 INFO L158 Benchmark]: Toolchain (without parser) took 46700.62ms. Allocated memory was 144.7MB in the beginning and 174.1MB in the end (delta: 29.4MB). Free memory was 76.0MB in the beginning and 76.9MB in the end (delta: -959.8kB). Peak memory consumption was 27.7MB. Max. memory is 16.1GB. [2024-10-12 00:12:43,516 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 144.7MB. Free memory is still 120.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 00:12:43,516 INFO L158 Benchmark]: CACSL2BoogieTranslator took 317.64ms. Allocated memory is still 144.7MB. Free memory was 76.0MB in the beginning and 115.7MB in the end (delta: -39.8MB). Peak memory consumption was 5.1MB. Max. memory is 16.1GB. [2024-10-12 00:12:43,516 INFO L158 Benchmark]: Boogie Procedure Inliner took 40.33ms. Allocated memory is still 144.7MB. Free memory was 115.7MB in the beginning and 114.4MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 00:12:43,517 INFO L158 Benchmark]: Boogie Preprocessor took 25.03ms. Allocated memory is still 144.7MB. Free memory was 114.4MB in the beginning and 113.1MB in the end (delta: 1.2MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-12 00:12:43,517 INFO L158 Benchmark]: RCFGBuilder took 241.68ms. Allocated memory is still 144.7MB. Free memory was 113.1MB in the beginning and 102.7MB in the end (delta: 10.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-12 00:12:43,517 INFO L158 Benchmark]: BuchiAutomizer took 46065.56ms. Allocated memory was 144.7MB in the beginning and 174.1MB in the end (delta: 29.4MB). Free memory was 102.7MB in the beginning and 78.0MB in the end (delta: 24.7MB). Peak memory consumption was 56.0MB. Max. memory is 16.1GB. [2024-10-12 00:12:43,518 INFO L158 Benchmark]: Witness Printer took 3.53ms. Allocated memory is still 174.1MB. Free memory was 78.0MB in the beginning and 76.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 00:12:43,519 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.12ms. Allocated memory is still 144.7MB. Free memory is still 120.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 317.64ms. Allocated memory is still 144.7MB. Free memory was 76.0MB in the beginning and 115.7MB in the end (delta: -39.8MB). Peak memory consumption was 5.1MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 40.33ms. Allocated memory is still 144.7MB. Free memory was 115.7MB in the beginning and 114.4MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 25.03ms. Allocated memory is still 144.7MB. Free memory was 114.4MB in the beginning and 113.1MB in the end (delta: 1.2MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 241.68ms. Allocated memory is still 144.7MB. Free memory was 113.1MB in the beginning and 102.7MB in the end (delta: 10.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 46065.56ms. Allocated memory was 144.7MB in the beginning and 174.1MB in the end (delta: 29.4MB). Free memory was 102.7MB in the beginning and 78.0MB in the end (delta: 24.7MB). Peak memory consumption was 56.0MB. Max. memory is 16.1GB. * Witness Printer took 3.53ms. Allocated memory is still 174.1MB. Free memory was 78.0MB in the beginning and 76.9MB in the end (delta: 1.0MB). 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 - 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 8 terminating modules (3 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 21 locations. One nondeterministic module has affine ranking function null and consists of 8 locations. 3 modules have a trivial ranking function, the largest among these consists of 17 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 46.0s and 6 iterations. TraceHistogramMax:7. Analysis of lassos took 39.8s. Construction of modules took 0.7s. Büchi inclusion checks took 5.1s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 65 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, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 12/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 235 SdHoareTripleChecker+Valid, 0.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 220 mSDsluCounter, 426 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 256 mSDsCounter, 192 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 970 IncrementalHoareTripleChecker+Invalid, 1162 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 192 mSolverCounterUnsat, 170 mSDtfsCounter, 970 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT2 conc0 concLT2 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital13 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq176 hnf90 smp100 dnf100 smp100 tf110 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: sat Degree: 0 Time: 55ms VariablesStem: 0 VariablesLoop: 2 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 3 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 2 LassoNonterminationAnalysisUnknown: 3 LassoNonterminationAnalysisTime: 36.8s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-12 00:12:43,547 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Ended with exit code 0 [2024-10-12 00:12:43,747 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-10-12 00:12:43,948 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/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