./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash b4d53423478efbe88c69a2c2de1bb984f61e7e586fd7bb6761452f26ace425f7 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-19 14:12:59,749 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 14:12:59,822 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-19 14:12:59,828 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 14:12:59,830 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 14:12:59,849 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 14:12:59,850 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 14:12:59,850 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 14:12:59,851 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 14:12:59,851 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 14:12:59,852 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 14:12:59,853 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 14:12:59,853 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 14:12:59,853 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-19 14:12:59,855 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-19 14:12:59,856 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-19 14:12:59,856 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-19 14:12:59,856 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-19 14:12:59,856 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-19 14:12:59,857 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 14:12:59,857 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-19 14:12:59,860 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 14:12:59,861 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 14:12:59,861 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-19 14:12:59,861 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-19 14:12:59,861 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-19 14:12:59,862 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 14:12:59,862 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-19 14:12:59,862 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 14:12:59,862 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-19 14:12:59,863 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 14:12:59,863 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 14:12:59,863 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 14:12:59,864 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 14:12:59,864 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 14:12:59,864 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-19 14:12:59,865 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/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/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-11-19 14:13:00,148 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 14:13:00,175 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 14:13:00,178 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 14:13:00,179 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 14:13:00,179 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 14:13:00,180 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2024-11-19 14:13:01,588 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 14:13:01,776 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 14:13:01,777 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/McCarthy91_Recursion.c [2024-11-19 14:13:01,782 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/49d1665ed/b43cb4ceeb1941429bae3f8861ad4c96/FLAG9d03a754f [2024-11-19 14:13:01,795 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/49d1665ed/b43cb4ceeb1941429bae3f8861ad4c96 [2024-11-19 14:13:01,797 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 14:13:01,798 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 14:13:01,799 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 14:13:01,799 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 14:13:01,804 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 14:13:01,804 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 02:13:01" (1/1) ... [2024-11-19 14:13:01,805 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2c10d3ad and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:01, skipping insertion in model container [2024-11-19 14:13:01,805 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 02:13:01" (1/1) ... [2024-11-19 14:13:01,819 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 14:13:01,971 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 14:13:01,977 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 14:13:01,988 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 14:13:02,004 INFO L204 MainTranslator]: Completed translation [2024-11-19 14:13:02,005 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02 WrapperNode [2024-11-19 14:13:02,005 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 14:13:02,006 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 14:13:02,006 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 14:13:02,006 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 14:13:02,013 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,019 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,032 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-11-19 14:13:02,032 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 14:13:02,033 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 14:13:02,033 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 14:13:02,033 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 14:13:02,042 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,043 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,043 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,049 INFO L175 MemorySlicer]: No memory access in input program. [2024-11-19 14:13:02,049 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,050 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,051 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,052 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,052 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,052 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,053 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 14:13:02,054 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 14:13:02,054 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 14:13:02,054 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 14:13:02,055 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (1/1) ... [2024-11-19 14:13:02,059 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:02,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:02,082 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:02,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-19 14:13:02,135 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 14:13:02,135 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 14:13:02,136 INFO L130 BoogieDeclarations]: Found specification of procedure mc91 [2024-11-19 14:13:02,136 INFO L138 BoogieDeclarations]: Found implementation of procedure mc91 [2024-11-19 14:13:02,192 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 14:13:02,194 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 14:13:02,369 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2024-11-19 14:13:02,370 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 14:13:02,383 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 14:13:02,384 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-19 14:13:02,384 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:13:02 BoogieIcfgContainer [2024-11-19 14:13:02,384 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 14:13:02,387 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-19 14:13:02,387 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-19 14:13:02,391 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-19 14:13:02,391 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 14:13:02,392 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 19.11 02:13:01" (1/3) ... [2024-11-19 14:13:02,392 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@5c9c0922 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 02:13:02, skipping insertion in model container [2024-11-19 14:13:02,393 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 14:13:02,393 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:02" (2/3) ... [2024-11-19 14:13:02,394 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@5c9c0922 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 02:13:02, skipping insertion in model container [2024-11-19 14:13:02,394 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 14:13:02,394 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:13:02" (3/3) ... [2024-11-19 14:13:02,396 INFO L332 chiAutomizerObserver]: Analyzing ICFG McCarthy91_Recursion.c [2024-11-19 14:13:02,459 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-19 14:13:02,460 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-19 14:13:02,460 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-19 14:13:02,460 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-19 14:13:02,460 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-19 14:13:02,461 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-19 14:13:02,461 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-19 14:13:02,461 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-19 14:13:02,466 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-11-19 14:13:02,484 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-19 14:13:02,484 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:02,485 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:02,491 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 14:13:02,492 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:02,493 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-19 14:13:02,493 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-11-19 14:13:02,494 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-19 14:13:02,496 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:02,496 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:02,497 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 14:13:02,497 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:02,506 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-11-19 14:13:02,506 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-11-19 14:13:02,511 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:02,512 INFO L85 PathProgramCache]: Analyzing trace with hash 29870, now seen corresponding path program 1 times [2024-11-19 14:13:02,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:02,520 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1315121917] [2024-11-19 14:13:02,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:02,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:02,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:02,599 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:02,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:02,620 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:02,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:02,624 INFO L85 PathProgramCache]: Analyzing trace with hash 37870, now seen corresponding path program 1 times [2024-11-19 14:13:02,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:02,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1109634582] [2024-11-19 14:13:02,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:02,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:02,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:02,651 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:02,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:02,658 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:02,663 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:02,663 INFO L85 PathProgramCache]: Analyzing trace with hash 889865249, now seen corresponding path program 1 times [2024-11-19 14:13:02,663 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:02,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [957303612] [2024-11-19 14:13:02,664 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:02,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:02,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:02,673 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:02,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:02,680 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:02,789 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:02,789 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:02,790 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:02,790 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:02,790 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:02,791 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:02,791 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:02,791 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:02,791 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2024-11-19 14:13:02,791 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:02,791 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:02,806 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,824 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,827 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,831 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,835 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,885 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:02,886 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:02,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:02,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:02,891 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:02,893 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-19 14:13:02,894 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:02,894 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:02,921 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-19 14:13:02,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:02,922 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:02,923 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:02,923 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-19 14:13:02,924 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:02,924 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:02,957 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:02,961 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-19 14:13:02,962 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:02,962 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:02,962 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:02,962 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:02,962 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:02,962 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:02,962 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:02,962 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:02,962 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration1_Loop [2024-11-19 14:13:02,963 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:02,963 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:02,964 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,973 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,976 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,978 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:02,981 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:03,010 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:03,015 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:03,016 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,016 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:03,018 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:03,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-19 14:13:03,021 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-11-19 14:13:03,033 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:03,033 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:03,033 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:03,034 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:03,034 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:03,035 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:03,036 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:03,039 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:03,045 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 14:13:03,045 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:03,047 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,047 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:03,067 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:03,068 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-19 14:13:03,069 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:03,069 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:03,070 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:03,071 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 211 Supporting invariants [] [2024-11-19 14:13:03,086 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-19 14:13:03,090 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:03,125 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:03,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:03,147 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-19 14:13:03,149 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:03,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:03,167 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:03,168 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:03,211 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:03,239 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-11-19 14:13:03,242 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-11-19 14:13:03,354 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-11-19 14:13:03,356 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-11-19 14:13:03,361 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-11-19 14:13:03,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2024-11-19 14:13:03,366 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2024-11-19 14:13:03,368 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:03,368 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2024-11-19 14:13:03,368 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:03,368 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2024-11-19 14:13:03,368 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:03,369 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 39 transitions. [2024-11-19 14:13:03,376 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-19 14:13:03,382 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 19 states and 25 transitions. [2024-11-19 14:13:03,384 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2024-11-19 14:13:03,385 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2024-11-19 14:13:03,385 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2024-11-19 14:13:03,387 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:03,387 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2024-11-19 14:13:03,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2024-11-19 14:13:03,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-11-19 14:13:03,412 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-11-19 14:13:03,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-11-19 14:13:03,415 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-19 14:13:03,415 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-19 14:13:03,415 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-19 14:13:03,415 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2024-11-19 14:13:03,417 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-19 14:13:03,418 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:03,418 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:03,419 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:03,419 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:03,420 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-11-19 14:13:03,420 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-11-19 14:13:03,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:03,423 INFO L85 PathProgramCache]: Analyzing trace with hash 1612519912, now seen corresponding path program 1 times [2024-11-19 14:13:03,424 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:03,424 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [443837570] [2024-11-19 14:13:03,424 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:03,424 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:03,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:03,435 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:03,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:03,449 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:03,450 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:03,450 INFO L85 PathProgramCache]: Analyzing trace with hash -696734814, now seen corresponding path program 1 times [2024-11-19 14:13:03,451 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:03,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303894437] [2024-11-19 14:13:03,451 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:03,451 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:03,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:03,462 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:03,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:03,473 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:03,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:03,474 INFO L85 PathProgramCache]: Analyzing trace with hash 1110240905, now seen corresponding path program 1 times [2024-11-19 14:13:03,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:03,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [589756956] [2024-11-19 14:13:03,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:03,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:03,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:03,493 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:03,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:03,507 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:03,658 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-19 14:13:03,673 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:03,673 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:03,673 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:03,673 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:03,674 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:03,674 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,674 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:03,674 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:03,674 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2024-11-19 14:13:03,674 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:03,674 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:03,676 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:03,684 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:03,686 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:03,751 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:03,751 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:03,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:03,755 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:03,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-19 14:13:03,757 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:03,757 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:03,772 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:03,772 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-11-19 14:13:03,785 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-11-19 14:13:03,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:03,787 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:03,788 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-19 14:13:03,788 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:03,788 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:03,800 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:03,800 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:03,811 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:03,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,812 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:03,813 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:03,814 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-19 14:13:03,814 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:03,814 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:03,849 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:03,850 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:03,850 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:03,851 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:03,852 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-19 14:13:03,853 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:03,853 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:15,902 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-19 14:13:15,914 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-19 14:13:15,915 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:15,915 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:15,915 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:15,915 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:15,915 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:15,915 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,915 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:15,916 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:15,916 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration2_Loop [2024-11-19 14:13:15,916 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:15,916 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:15,917 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,921 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,933 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,978 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:15,979 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:15,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,979 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,982 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:15,986 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-19 14:13:15,987 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-11-19 14:13:16,000 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:16,000 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:16,001 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:16,001 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:16,001 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:16,002 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:16,002 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:16,003 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:16,014 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,015 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,016 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:16,017 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-19 14:13:16,018 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-11-19 14:13:16,028 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:16,028 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:16,028 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:16,028 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:16,028 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:16,031 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:16,032 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:16,036 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:16,041 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 14:13:16,042 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:16,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,044 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:16,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-11-19 14:13:16,049 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:16,049 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:16,049 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:16,049 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#t~ret0) = -2*mc91_#t~ret0 + 201 Supporting invariants [] [2024-11-19 14:13:16,070 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,071 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:16,082 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret0 [2024-11-19 14:13:16,096 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:16,123 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-19 14:13:16,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:16,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:16,237 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-19 14:13:16,238 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:16,352 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:16,353 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-11-19 14:13:16,353 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-11-19 14:13:16,547 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-11-19 14:13:16,549 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-11-19 14:13:16,551 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-11-19 14:13:16,553 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-11-19 14:13:16,553 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2024-11-19 14:13:16,556 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:16,556 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2024-11-19 14:13:16,557 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:16,557 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2024-11-19 14:13:16,557 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:16,557 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2024-11-19 14:13:16,563 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-11-19 14:13:16,566 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2024-11-19 14:13:16,567 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-19 14:13:16,568 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2024-11-19 14:13:16,568 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2024-11-19 14:13:16,569 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:16,569 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2024-11-19 14:13:16,569 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2024-11-19 14:13:16,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2024-11-19 14:13:16,573 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-11-19 14:13:16,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2024-11-19 14:13:16,575 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-11-19 14:13:16,575 INFO L425 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-11-19 14:13:16,575 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-19 14:13:16,575 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2024-11-19 14:13:16,576 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-11-19 14:13:16,576 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:16,577 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:16,577 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:16,577 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:16,577 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-11-19 14:13:16,578 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-11-19 14:13:16,578 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,578 INFO L85 PathProgramCache]: Analyzing trace with hash -628486927, now seen corresponding path program 2 times [2024-11-19 14:13:16,578 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,578 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1087251169] [2024-11-19 14:13:16,579 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:16,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,593 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:16,593 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:16,594 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:16,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,604 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:16,606 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,607 INFO L85 PathProgramCache]: Analyzing trace with hash 48310, now seen corresponding path program 2 times [2024-11-19 14:13:16,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,607 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [465800568] [2024-11-19 14:13:16,607 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:16,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,613 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2024-11-19 14:13:16,613 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:16,613 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:16,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,616 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:16,616 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,617 INFO L85 PathProgramCache]: Analyzing trace with hash -1491580474, now seen corresponding path program 3 times [2024-11-19 14:13:16,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2081732424] [2024-11-19 14:13:16,618 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 14:13:16,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,635 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-19 14:13:16,636 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:16,796 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 14:13:16,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:16,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2081732424] [2024-11-19 14:13:16,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2081732424] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 14:13:16,797 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 14:13:16,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-19 14:13:16,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1657629672] [2024-11-19 14:13:16,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 14:13:16,848 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:16,848 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:16,848 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:16,848 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:16,848 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:16,848 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,848 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:16,849 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:16,849 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2024-11-19 14:13:16,849 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:16,849 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:16,849 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,862 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,867 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,869 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,903 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:16,903 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:16,904 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,905 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:16,905 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-19 14:13:16,907 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,907 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,936 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-19 14:13:16,936 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,936 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,937 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:16,938 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-19 14:13:16,939 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:16,939 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:28,970 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-19 14:13:28,979 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:28,979 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:28,979 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:28,979 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:28,979 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:28,979 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:28,979 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:28,979 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:28,979 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:28,979 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration3_Loop [2024-11-19 14:13:28,980 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:28,980 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:28,980 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:28,987 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:28,990 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:28,992 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:29,019 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:29,020 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:29,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:29,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:29,022 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:29,023 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-19 14:13:29,025 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-11-19 14:13:29,038 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:29,038 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:29,038 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:29,038 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:29,038 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:29,040 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:29,040 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:29,044 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:29,047 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 14:13:29,047 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:29,048 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:29,048 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:29,050 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:29,051 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-19 14:13:29,051 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:29,051 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:29,051 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:29,051 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_~n) = -2*mc91_~n + 189 Supporting invariants [] [2024-11-19 14:13:29,062 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-19 14:13:29,063 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:29,078 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:29,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:29,103 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 14:13:29,104 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:29,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:29,195 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:29,196 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:29,224 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:29,225 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-11-19 14:13:29,225 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-11-19 14:13:29,296 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-11-19 14:13:29,296 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-11-19 14:13:29,297 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-11-19 14:13:29,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-19 14:13:29,297 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-11-19 14:13:29,297 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:29,297 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:29,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:29,331 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:29,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:29,351 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 14:13:29,352 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:29,355 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-19 14:13:29,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:29,444 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:29,445 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:29,476 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:29,477 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-11-19 14:13:29,477 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-11-19 14:13:29,540 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-11-19 14:13:29,540 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-11-19 14:13:29,541 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-11-19 14:13:29,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-19 14:13:29,541 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-11-19 14:13:29,542 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:29,542 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:29,553 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:29,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:29,578 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 14:13:29,579 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:29,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:29,643 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:29,643 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:29,674 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:29,675 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-11-19 14:13:29,675 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-11-19 14:13:29,751 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-11-19 14:13:29,752 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-11-19 14:13:29,753 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-11-19 14:13:29,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2024-11-19 14:13:29,753 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2024-11-19 14:13:29,754 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:29,754 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2024-11-19 14:13:29,754 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:29,754 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2024-11-19 14:13:29,754 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:29,755 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2024-11-19 14:13:29,759 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2024-11-19 14:13:29,761 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2024-11-19 14:13:29,761 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-19 14:13:29,762 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-11-19 14:13:29,762 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2024-11-19 14:13:29,762 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:29,762 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2024-11-19 14:13:29,765 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2024-11-19 14:13:29,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2024-11-19 14:13:29,771 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-11-19 14:13:29,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2024-11-19 14:13:29,772 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2024-11-19 14:13:29,772 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:29,776 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 14:13:29,776 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-19 14:13:29,777 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-11-19 14:13:29,880 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:29,880 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2024-11-19 14:13:29,881 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2024-11-19 14:13:29,883 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-19 14:13:29,887 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2024-11-19 14:13:29,887 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2024-11-19 14:13:29,888 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-11-19 14:13:29,888 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2024-11-19 14:13:29,888 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:29,888 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-11-19 14:13:29,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2024-11-19 14:13:29,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-11-19 14:13:29,893 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-11-19 14:13:29,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-11-19 14:13:29,894 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-11-19 14:13:29,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-19 14:13:29,895 INFO L425 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-11-19 14:13:29,895 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-19 14:13:29,895 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2024-11-19 14:13:29,896 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-19 14:13:29,896 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:29,896 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:29,897 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-19 14:13:29,898 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-19 14:13:29,898 INFO L745 eck$LassoCheckResult]: Stem: 848#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 849#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; 830#L16 call main_#t~ret3#1 := mc91(main_~x~0#1);< 832#$Ultimate##0 ~n := #in~n; 855#L10 assume !(~n > 100); 829#L11 call #t~ret0 := mc91(11 + ~n);< 831#$Ultimate##0 ~n := #in~n; 864#L10 assume !(~n > 100); 860#L11 call #t~ret0 := mc91(11 + ~n);< 862#$Ultimate##0 ~n := #in~n; 865#L10 assume ~n > 100;#res := ~n - 10; 863#mc91FINAL assume true; 861#mc91EXIT >#20#return; 841#L11-1 call #t~ret1 := mc91(#t~ret0);< 840#$Ultimate##0 ~n := #in~n; 843#L10 assume ~n > 100;#res := ~n - 10; 854#mc91FINAL assume true; 880#mc91EXIT >#22#return; 856#L11-2 #res := #t~ret1;havoc #t~ret0;havoc #t~ret1; 878#mc91FINAL assume true; 877#mc91EXIT >#20#return; 834#L11-1 call #t~ret1 := mc91(#t~ret0);< 852#$Ultimate##0 [2024-11-19 14:13:29,898 INFO L747 eck$LassoCheckResult]: Loop: 852#$Ultimate##0 ~n := #in~n; 870#L10 assume !(~n > 100); 845#L11 call #t~ret0 := mc91(11 + ~n);< 844#$Ultimate##0 ~n := #in~n; 847#L10 assume !(~n > 100); 846#L11 call #t~ret0 := mc91(11 + ~n);< 866#$Ultimate##0 ~n := #in~n; 876#L10 assume ~n > 100;#res := ~n - 10; 874#mc91FINAL assume true; 872#mc91EXIT >#20#return; 826#L11-1 call #t~ret1 := mc91(#t~ret0);< 869#$Ultimate##0 ~n := #in~n; 867#L10 assume ~n > 100;#res := ~n - 10; 868#mc91FINAL assume true; 879#mc91EXIT >#22#return; 856#L11-2 #res := #t~ret1;havoc #t~ret0;havoc #t~ret1; 878#mc91FINAL assume true; 877#mc91EXIT >#20#return; 835#L11-1 call #t~ret1 := mc91(#t~ret0);< 852#$Ultimate##0 [2024-11-19 14:13:29,898 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:29,898 INFO L85 PathProgramCache]: Analyzing trace with hash 1678623115, now seen corresponding path program 1 times [2024-11-19 14:13:29,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:29,899 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1779771126] [2024-11-19 14:13:29,899 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:29,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:29,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:29,908 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:29,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:29,916 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:29,916 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:29,916 INFO L85 PathProgramCache]: Analyzing trace with hash -2037590184, now seen corresponding path program 1 times [2024-11-19 14:13:29,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:29,916 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1733674721] [2024-11-19 14:13:29,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:29,917 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:29,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:29,924 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:29,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:29,931 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:29,932 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:29,932 INFO L85 PathProgramCache]: Analyzing trace with hash 1698366862, now seen corresponding path program 2 times [2024-11-19 14:13:29,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:29,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1002193279] [2024-11-19 14:13:29,932 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:29,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:29,944 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:29,944 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:30,071 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-19 14:13:30,072 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:30,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1002193279] [2024-11-19 14:13:30,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1002193279] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 14:13:30,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1051060175] [2024-11-19 14:13:30,072 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:30,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 14:13:30,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:30,074 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 14:13:30,076 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-19 14:13:30,117 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:30,118 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:30,119 INFO L255 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-19 14:13:30,120 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:30,160 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-19 14:13:30,160 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 14:13:30,378 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-19 14:13:30,379 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1051060175] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 14:13:30,379 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 14:13:30,380 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2024-11-19 14:13:30,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1082949737] [2024-11-19 14:13:30,380 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 14:13:30,558 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:30,559 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:30,559 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:30,559 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:30,559 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:30,559 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:30,559 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:30,559 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:30,559 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2024-11-19 14:13:30,559 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:30,559 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:30,560 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,567 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,569 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,570 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,572 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,597 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:30,598 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:30,598 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:30,598 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:30,600 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:30,601 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-11-19 14:13:30,602 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:30,602 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:30,638 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-19 14:13:30,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:30,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:30,640 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:30,642 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-19 14:13:30,643 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:30,643 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:30,656 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:30,666 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:30,666 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:30,666 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:30,666 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:30,667 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:30,667 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:30,667 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:30,667 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:30,667 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:30,667 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration4_Loop [2024-11-19 14:13:30,667 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:30,667 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:30,668 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,673 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,675 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,677 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,679 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:30,708 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:30,708 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:30,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:30,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:30,711 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:30,712 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-19 14:13:30,713 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-11-19 14:13:30,724 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:30,724 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:30,724 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:30,724 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:30,725 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:30,725 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:30,726 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:30,728 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:30,730 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 14:13:30,730 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:30,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:30,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:30,732 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:30,733 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-11-19 14:13:30,734 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:30,734 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:30,735 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:30,735 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -1*mc91_#in~n + 90 Supporting invariants [] [2024-11-19 14:13:30,749 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-19 14:13:30,750 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:30,765 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:30,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:30,796 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-19 14:13:30,798 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:30,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:30,987 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-19 14:13:30,989 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:31,198 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-19 14:13:31,199 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-11-19 14:13:31,199 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-11-19 14:13:31,565 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-11-19 14:13:31,566 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-11-19 14:13:31,567 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-11-19 14:13:31,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-11-19 14:13:31,567 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-19 14:13:31,567 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:31,567 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:31,580 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:31,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:31,610 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-19 14:13:31,611 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:31,704 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-11-19 14:13:31,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:31,805 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-19 14:13:31,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:32,010 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-19 14:13:32,011 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-11-19 14:13:32,011 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-11-19 14:13:32,349 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-11-19 14:13:32,349 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-11-19 14:13:32,350 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-11-19 14:13:32,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-11-19 14:13:32,350 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-19 14:13:32,351 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:32,351 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:32,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:32,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:32,388 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-19 14:13:32,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:32,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:32,556 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-19 14:13:32,557 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:32,722 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-19 14:13:32,723 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 9 loop predicates [2024-11-19 14:13:32,724 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-19 14:13:33,292 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Result 325 states and 417 transitions. Complement of second has 131 states. [2024-11-19 14:13:33,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 19 states 2 stem states 16 non-accepting loop states 1 accepting loop states [2024-11-19 14:13:33,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-19 14:13:33,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 50 transitions. [2024-11-19 14:13:33,294 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-19 14:13:33,294 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:33,294 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2024-11-19 14:13:33,295 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:33,295 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2024-11-19 14:13:33,295 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:33,295 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 325 states and 417 transitions. [2024-11-19 14:13:33,302 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 25 [2024-11-19 14:13:33,306 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 325 states to 169 states and 230 transitions. [2024-11-19 14:13:33,306 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-19 14:13:33,308 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2024-11-19 14:13:33,308 INFO L73 IsDeterministic]: Start isDeterministic. Operand 169 states and 230 transitions. [2024-11-19 14:13:33,308 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:33,308 INFO L218 hiAutomatonCegarLoop]: Abstraction has 169 states and 230 transitions. [2024-11-19 14:13:33,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states and 230 transitions. [2024-11-19 14:13:33,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 140. [2024-11-19 14:13:33,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 86 states have (on average 1.0813953488372092) internal successors, (93), 88 states have internal predecessors, (93), 32 states have call successors, (42), 26 states have call predecessors, (42), 22 states have return successors, (43), 25 states have call predecessors, (43), 28 states have call successors, (43) [2024-11-19 14:13:33,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 178 transitions. [2024-11-19 14:13:33,332 INFO L240 hiAutomatonCegarLoop]: Abstraction has 140 states and 178 transitions. [2024-11-19 14:13:33,333 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:33,333 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-19 14:13:33,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2024-11-19 14:13:33,333 INFO L87 Difference]: Start difference. First operand 140 states and 178 transitions. Second operand has 15 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 8 states have internal predecessors, (22), 7 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 7 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-19 14:13:33,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:33,535 INFO L93 Difference]: Finished difference Result 138 states and 163 transitions. [2024-11-19 14:13:33,535 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 138 states and 163 transitions. [2024-11-19 14:13:33,537 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-19 14:13:33,538 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 138 states to 101 states and 121 transitions. [2024-11-19 14:13:33,538 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-19 14:13:33,539 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-19 14:13:33,539 INFO L73 IsDeterministic]: Start isDeterministic. Operand 101 states and 121 transitions. [2024-11-19 14:13:33,539 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:33,539 INFO L218 hiAutomatonCegarLoop]: Abstraction has 101 states and 121 transitions. [2024-11-19 14:13:33,539 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states and 121 transitions. [2024-11-19 14:13:33,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2024-11-19 14:13:33,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 60 states have (on average 1.05) internal successors, (63), 61 states have internal predecessors, (63), 22 states have call successors, (29), 19 states have call predecessors, (29), 15 states have return successors, (25), 16 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-19 14:13:33,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 117 transitions. [2024-11-19 14:13:33,544 INFO L240 hiAutomatonCegarLoop]: Abstraction has 97 states and 117 transitions. [2024-11-19 14:13:33,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-19 14:13:33,546 INFO L425 stractBuchiCegarLoop]: Abstraction has 97 states and 117 transitions. [2024-11-19 14:13:33,546 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-19 14:13:33,546 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 97 states and 117 transitions. [2024-11-19 14:13:33,547 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-19 14:13:33,547 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:33,547 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:33,551 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2024-11-19 14:13:33,551 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:33,552 INFO L745 eck$LassoCheckResult]: Stem: 2738#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 2739#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; 2718#L16 call main_#t~ret3#1 := mc91(main_~x~0#1);< 2719#$Ultimate##0 ~n := #in~n; 2756#L10 assume !(~n > 100); 2757#L11 call #t~ret0 := mc91(11 + ~n);< 2758#$Ultimate##0 ~n := #in~n; 2760#L10 assume !(~n > 100); 2759#L11 call #t~ret0 := mc91(11 + ~n);< 2776#$Ultimate##0 ~n := #in~n; 2778#L10 assume ~n > 100;#res := ~n - 10; 2777#mc91FINAL assume true; 2775#mc91EXIT >#20#return; 2772#L11-1 call #t~ret1 := mc91(#t~ret0);< 2774#$Ultimate##0 ~n := #in~n; 2780#L10 assume ~n > 100;#res := ~n - 10; 2779#mc91FINAL assume true; 2771#mc91EXIT >#22#return; 2769#L11-2 #res := #t~ret1;havoc #t~ret0;havoc #t~ret1; 2767#mc91FINAL assume true; 2766#mc91EXIT >#20#return; 2761#L11-1 call #t~ret1 := mc91(#t~ret0);< 2765#$Ultimate##0 ~n := #in~n; 2763#L10 assume !(~n > 100); 2724#L11 call #t~ret0 := mc91(11 + ~n);< 2732#$Ultimate##0 ~n := #in~n; 2733#L10 assume ~n > 100;#res := ~n - 10; 2747#mc91FINAL assume true; 2813#mc91EXIT >#20#return; 2789#L11-1 call #t~ret1 := mc91(#t~ret0);< 2791#$Ultimate##0 ~n := #in~n; 2806#L10 assume !(~n > 100); 2804#L11 call #t~ret0 := mc91(11 + ~n);< 2722#$Ultimate##0 ~n := #in~n; 2809#L10 assume ~n > 100;#res := ~n - 10; 2808#mc91FINAL assume true; 2803#mc91EXIT >#20#return; 2743#L11-1 call #t~ret1 := mc91(#t~ret0);< 2799#$Ultimate##0 [2024-11-19 14:13:33,552 INFO L747 eck$LassoCheckResult]: Loop: 2799#$Ultimate##0 ~n := #in~n; 2810#L10 assume !(~n > 100); 2805#L11 call #t~ret0 := mc91(11 + ~n);< 2722#$Ultimate##0 ~n := #in~n; 2809#L10 assume ~n > 100;#res := ~n - 10; 2808#mc91FINAL assume true; 2803#mc91EXIT >#20#return; 2742#L11-1 call #t~ret1 := mc91(#t~ret0);< 2799#$Ultimate##0 [2024-11-19 14:13:33,552 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:33,552 INFO L85 PathProgramCache]: Analyzing trace with hash -1106586231, now seen corresponding path program 3 times [2024-11-19 14:13:33,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:33,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [964912955] [2024-11-19 14:13:33,552 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 14:13:33,552 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:33,572 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-19 14:13:33,572 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:33,572 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:33,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:33,588 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:33,588 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:33,588 INFO L85 PathProgramCache]: Analyzing trace with hash 1861921664, now seen corresponding path program 2 times [2024-11-19 14:13:33,588 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:33,588 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [94343341] [2024-11-19 14:13:33,588 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:33,589 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:33,596 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:33,596 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:33,596 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:33,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:33,602 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:33,603 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:33,603 INFO L85 PathProgramCache]: Analyzing trace with hash 935033096, now seen corresponding path program 4 times [2024-11-19 14:13:33,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:33,603 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [189137705] [2024-11-19 14:13:33,603 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 14:13:33,603 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:33,619 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 14:13:33,620 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:33,620 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:33,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:33,642 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:33,718 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:33,718 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:33,719 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:33,719 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:33,719 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:33,719 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,719 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:33,719 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:33,719 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2024-11-19 14:13:33,719 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:33,719 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:33,719 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,723 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,725 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,730 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,732 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,755 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:33,756 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:33,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,761 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,765 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-19 14:13:33,766 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:33,766 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:33,782 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:33,782 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#t~ret0=0} Honda state: {mc91_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:33,797 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:33,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,798 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,800 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-19 14:13:33,802 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:33,802 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:33,815 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:33,815 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mc91_#res=0} Honda state: {mc91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:33,828 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:33,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,832 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-19 14:13:33,835 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:33,835 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:33,863 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:33,863 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,865 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,867 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-11-19 14:13:33,868 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:33,868 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:33,880 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:33,890 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:33,891 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:33,891 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:33,891 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:33,891 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:33,891 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:33,891 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,891 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:33,891 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:33,891 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91_Recursion.c_Iteration5_Loop [2024-11-19 14:13:33,891 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:33,891 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:33,892 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,894 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,896 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,902 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,904 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:33,929 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:33,930 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:33,930 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,932 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,934 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-19 14:13:33,936 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-11-19 14:13:33,948 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:33,948 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:33,948 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:33,948 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:33,948 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:33,949 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:33,949 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:33,952 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:33,964 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:33,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,966 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,967 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-19 14:13:33,967 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-11-19 14:13:33,977 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:33,977 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:33,977 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:33,977 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:33,977 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:33,977 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:33,977 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:33,979 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:33,993 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:33,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:33,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:33,995 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:33,996 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-19 14:13:33,998 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-19 14:13:34,010 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:34,010 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:34,010 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:34,010 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:34,010 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:34,011 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:34,011 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:34,014 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:34,017 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 14:13:34,017 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:34,017 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:34,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:34,019 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-19 14:13:34,020 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-11-19 14:13:34,021 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:34,021 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:34,021 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:34,021 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mc91_#in~n) = -2*mc91_#in~n + 201 Supporting invariants [] [2024-11-19 14:13:34,034 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:34,035 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:34,049 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:34,094 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:34,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:34,120 INFO L255 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-19 14:13:34,122 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:34,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:34,318 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-19 14:13:34,318 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:34,403 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:34,404 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-11-19 14:13:34,404 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:34,494 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 107 states and 127 transitions. Complement of second has 16 states. [2024-11-19 14:13:34,495 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-11-19 14:13:34,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, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:34,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 15 transitions. [2024-11-19 14:13:34,496 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 15 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-19 14:13:34,497 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:34,497 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:34,510 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:34,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:34,577 INFO L255 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-19 14:13:34,579 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:34,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:34,778 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-19 14:13:34,779 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:34,867 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:34,867 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-11-19 14:13:34,868 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:35,052 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 125 states and 146 transitions. Complement of second has 28 states. [2024-11-19 14:13:35,052 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-11-19 14:13:35,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:35,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 20 transitions. [2024-11-19 14:13:35,053 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 20 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-19 14:13:35,054 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:35,054 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:35,064 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:35,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:35,114 INFO L255 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-19 14:13:35,116 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:35,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:35,311 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-19 14:13:35,311 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:35,398 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:35,399 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-11-19 14:13:35,399 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:35,483 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 147 states and 167 transitions. Complement of second has 17 states. [2024-11-19 14:13:35,486 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-11-19 14:13:35,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:35,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-11-19 14:13:35,487 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-19 14:13:35,487 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:35,487 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:35,501 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:35,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:35,551 INFO L255 TraceCheckSpWp]: Trace formula consists of 341 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-19 14:13:35,552 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:35,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:35,763 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-19 14:13:35,764 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:35,863 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:35,864 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-19 14:13:35,864 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:36,150 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 182 states and 209 transitions. Complement of second has 51 states. [2024-11-19 14:13:36,151 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 12 states 2 stem states 9 non-accepting loop states 1 accepting loop states [2024-11-19 14:13:36,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-19 14:13:36,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 27 transitions. [2024-11-19 14:13:36,154 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-19 14:13:36,154 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:36,154 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 46 letters. Loop has 8 letters. [2024-11-19 14:13:36,154 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:36,154 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 16 letters. [2024-11-19 14:13:36,155 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:36,155 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 182 states and 209 transitions. [2024-11-19 14:13:36,157 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 14:13:36,157 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 182 states to 0 states and 0 transitions. [2024-11-19 14:13:36,159 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-19 14:13:36,159 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-19 14:13:36,159 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-19 14:13:36,159 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 14:13:36,159 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:36,160 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:36,160 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:36,160 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-19 14:13:36,160 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-19 14:13:36,160 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 14:13:36,160 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-19 14:13:36,166 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 19.11 02:13:36 BoogieIcfgContainer [2024-11-19 14:13:36,167 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-19 14:13:36,168 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-19 14:13:36,168 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-19 14:13:36,168 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-19 14:13:36,168 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:13:02" (3/4) ... [2024-11-19 14:13:36,170 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-19 14:13:36,171 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-19 14:13:36,173 INFO L158 Benchmark]: Toolchain (without parser) took 34373.75ms. Allocated memory was 144.7MB in the beginning and 174.1MB in the end (delta: 29.4MB). Free memory was 106.4MB in the beginning and 110.7MB in the end (delta: -4.4MB). Peak memory consumption was 23.4MB. Max. memory is 16.1GB. [2024-11-19 14:13:36,173 INFO L158 Benchmark]: CDTParser took 0.48ms. Allocated memory is still 144.7MB. Free memory is still 111.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 14:13:36,173 INFO L158 Benchmark]: CACSL2BoogieTranslator took 205.94ms. Allocated memory is still 144.7MB. Free memory was 105.9MB in the beginning and 95.3MB in the end (delta: 10.6MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-19 14:13:36,173 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.43ms. Allocated memory is still 144.7MB. Free memory was 95.3MB in the beginning and 93.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 14:13:36,174 INFO L158 Benchmark]: Boogie Preprocessor took 20.51ms. Allocated memory is still 144.7MB. Free memory was 93.8MB in the beginning and 92.4MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 14:13:36,174 INFO L158 Benchmark]: RCFGBuilder took 330.58ms. Allocated memory is still 144.7MB. Free memory was 92.4MB in the beginning and 110.8MB in the end (delta: -18.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-19 14:13:36,175 INFO L158 Benchmark]: BuchiAutomizer took 33780.45ms. Allocated memory was 144.7MB in the beginning and 174.1MB in the end (delta: 29.4MB). Free memory was 110.8MB in the beginning and 110.7MB in the end (delta: 5.8kB). Peak memory consumption was 30.1MB. Max. memory is 16.1GB. [2024-11-19 14:13:36,176 INFO L158 Benchmark]: Witness Printer took 3.80ms. Allocated memory is still 174.1MB. Free memory is still 110.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 14:13:36,177 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.48ms. Allocated memory is still 144.7MB. Free memory is still 111.8MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 205.94ms. Allocated memory is still 144.7MB. Free memory was 105.9MB in the beginning and 95.3MB in the end (delta: 10.6MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.43ms. Allocated memory is still 144.7MB. Free memory was 95.3MB in the beginning and 93.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 20.51ms. Allocated memory is still 144.7MB. Free memory was 93.8MB in the beginning and 92.4MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 330.58ms. Allocated memory is still 144.7MB. Free memory was 92.4MB in the beginning and 110.8MB in the end (delta: -18.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 33780.45ms. Allocated memory was 144.7MB in the beginning and 174.1MB in the end (delta: 29.4MB). Free memory was 110.8MB in the beginning and 110.7MB in the end (delta: 5.8kB). Peak memory consumption was 30.1MB. Max. memory is 16.1GB. * Witness Printer took 3.80ms. Allocated memory is still 174.1MB. Free memory is still 110.7MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret0 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 7 terminating modules (2 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function (211 + ((long) -2 * \old(n))) and consists of 5 locations. One deterministic module has affine ranking function null and consists of 8 locations. One nondeterministic module has affine ranking function (((long) -2 * n) + 189) and consists of 6 locations. One nondeterministic module has affine ranking function (90 + ((long) -1 * \old(n))) and consists of 19 locations. One nondeterministic module has affine ranking function (((long) -2 * \old(n)) + 201) and consists of 12 locations. 2 modules have a trivial ranking function, the largest among these consists of 15 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 33.7s and 6 iterations. TraceHistogramMax:8. Analysis of lassos took 27.0s. Construction of modules took 0.7s. Büchi inclusion checks took 5.6s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 48 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 1, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 10/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 262 SdHoareTripleChecker+Valid, 0.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 248 mSDsluCounter, 453 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 267 mSDsCounter, 201 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 994 IncrementalHoareTripleChecker+Invalid, 1195 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 201 mSolverCounterUnsat, 186 mSDtfsCounter, 994 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT3 conc0 concLT2 SILN0 SILU0 SILI0 SILT0 lasso0 LassoPreprocessingBenchmarks: Lassos: inital12 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq171 hnf91 smp100 dnf100 smp100 tf110 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: sat Degree: 0 Time: 54ms VariablesStem: 0 VariablesLoop: 2 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 3 LassoNonterminationAnalysisUnknown: 2 LassoNonterminationAnalysisTime: 24.4s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-19 14:13:36,203 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-19 14:13:36,403 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE