./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.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/NestedRecursion_1d.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 9c9c032ca120503dfa93615a57a0bb47775014248f579f3a3fd38a4985b2298b --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-19 14:13:09,844 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 14:13:09,902 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-19 14:13:09,906 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 14:13:09,906 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 14:13:09,925 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 14:13:09,926 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 14:13:09,927 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 14:13:09,927 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 14:13:09,927 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 14:13:09,928 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 14:13:09,928 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 14:13:09,929 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 14:13:09,929 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-19 14:13:09,929 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-19 14:13:09,930 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-19 14:13:09,930 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-19 14:13:09,931 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-19 14:13:09,931 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-19 14:13:09,931 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 14:13:09,932 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-19 14:13:09,932 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 14:13:09,933 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 14:13:09,933 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-19 14:13:09,933 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-19 14:13:09,933 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-19 14:13:09,934 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 14:13:09,934 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-19 14:13:09,934 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 14:13:09,935 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-19 14:13:09,935 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 14:13:09,935 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 14:13:09,936 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 14:13:09,936 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 14:13:09,936 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 14:13:09,937 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-19 14:13:09,937 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 -> 9c9c032ca120503dfa93615a57a0bb47775014248f579f3a3fd38a4985b2298b [2024-11-19 14:13:10,174 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 14:13:10,202 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 14:13:10,206 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 14:13:10,207 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 14:13:10,208 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 14:13:10,209 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-11-19 14:13:11,638 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 14:13:11,798 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 14:13:11,799 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-11-19 14:13:11,805 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4759a3aa5/678f58a5ee154be2bbabc938e7fef193/FLAG80dd4db94 [2024-11-19 14:13:11,818 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4759a3aa5/678f58a5ee154be2bbabc938e7fef193 [2024-11-19 14:13:11,820 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 14:13:11,821 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 14:13:11,823 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 14:13:11,823 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 14:13:11,829 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 14:13:11,830 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 02:13:11" (1/1) ... [2024-11-19 14:13:11,831 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6ee65f90 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:11, skipping insertion in model container [2024-11-19 14:13:11,831 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 02:13:11" (1/1) ... [2024-11-19 14:13:11,847 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 14:13:12,046 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 14:13:12,052 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 14:13:12,066 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 14:13:12,079 INFO L204 MainTranslator]: Completed translation [2024-11-19 14:13:12,080 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:12 WrapperNode [2024-11-19 14:13:12,080 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 14:13:12,081 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 14:13:12,081 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 14:13:12,081 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 14:13:12,088 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:12" (1/1) ... [2024-11-19 14:13:12,092 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:12" (1/1) ... [2024-11-19 14:13:12,107 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-11-19 14:13:12,109 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 14:13:12,110 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 14:13:12,111 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 14:13:12,111 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 14:13:12,121 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:12" (1/1) ... [2024-11-19 14:13:12,121 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:12" (1/1) ... [2024-11-19 14:13:12,122 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:12" (1/1) ... [2024-11-19 14:13:12,127 INFO L175 MemorySlicer]: No memory access in input program. [2024-11-19 14:13:12,127 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:12" (1/1) ... [2024-11-19 14:13:12,127 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:12" (1/1) ... [2024-11-19 14:13:12,129 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:12" (1/1) ... [2024-11-19 14:13:12,131 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:12" (1/1) ... [2024-11-19 14:13:12,131 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:12" (1/1) ... [2024-11-19 14:13:12,132 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:12" (1/1) ... [2024-11-19 14:13:12,133 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 14:13:12,134 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 14:13:12,134 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 14:13:12,134 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 14:13:12,135 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:12" (1/1) ... [2024-11-19 14:13:12,141 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:12,155 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:12,172 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:12,178 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:12,223 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2024-11-19 14:13:12,224 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2024-11-19 14:13:12,225 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2024-11-19 14:13:12,225 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2024-11-19 14:13:12,225 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 14:13:12,225 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 14:13:12,281 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 14:13:12,283 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 14:13:12,388 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-19 14:13:12,389 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 14:13:12,409 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 14:13:12,409 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-19 14:13:12,410 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:13:12 BoogieIcfgContainer [2024-11-19 14:13:12,410 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 14:13:12,411 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-19 14:13:12,411 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-19 14:13:12,415 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-19 14:13:12,416 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 14:13:12,416 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 19.11 02:13:11" (1/3) ... [2024-11-19 14:13:12,417 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@12e53b4c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 02:13:12, skipping insertion in model container [2024-11-19 14:13:12,417 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 14:13:12,417 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 02:13:12" (2/3) ... [2024-11-19 14:13:12,417 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@12e53b4c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 02:13:12, skipping insertion in model container [2024-11-19 14:13:12,417 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 14:13:12,418 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 02:13:12" (3/3) ... [2024-11-19 14:13:12,419 INFO L332 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2024-11-19 14:13:12,477 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-19 14:13:12,477 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-19 14:13:12,478 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-19 14:13:12,478 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-19 14:13:12,478 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-19 14:13:12,478 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-19 14:13:12,478 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-19 14:13:12,478 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-19 14:13:12,481 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 22 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 13 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-19 14:13:12,497 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:12,497 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:12,497 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:12,502 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 14:13:12,502 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:12,503 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-19 14:13:12,503 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 22 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 13 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-19 14:13:12,505 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:12,505 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:12,505 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:12,506 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 14:13:12,506 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:12,512 INFO L745 eck$LassoCheckResult]: Stem: 21#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true; 14#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 10#L25true call main_#t~ret6#1 := rec2(main_~x~0#1);< 7#$Ultimate##0true [2024-11-19 14:13:12,513 INFO L747 eck$LassoCheckResult]: Loop: 7#$Ultimate##0true ~j := #in~j; 17#L18true assume !(~j <= 0); 20#L20true call #t~ret3 := rec1(~j);< 4#$Ultimate##0true ~i := #in~i; 18#L12true assume ~i <= 0;#res := 0; 15#rec1FINALtrue assume true; 16#rec1EXITtrue >#34#return; 3#L20-1true call #t~ret4 := rec2(#t~ret3 - 1);< 7#$Ultimate##0true [2024-11-19 14:13:12,517 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:12,517 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 1 times [2024-11-19 14:13:12,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:12,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [267317338] [2024-11-19 14:13:12,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:12,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:12,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:12,588 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:12,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:12,606 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:12,609 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:12,609 INFO L85 PathProgramCache]: Analyzing trace with hash -1074209557, now seen corresponding path program 1 times [2024-11-19 14:13:12,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:12,610 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1851094980] [2024-11-19 14:13:12,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:12,610 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:12,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:12,766 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:12,767 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:12,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1851094980] [2024-11-19 14:13:12,767 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1851094980] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 14:13:12,768 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 14:13:12,768 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 14:13:12,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1189170763] [2024-11-19 14:13:12,769 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 14:13:12,771 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 14:13:12,772 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:12,799 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 14:13:12,800 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 14:13:12,801 INFO L87 Difference]: Start difference. First operand has 22 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 13 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 5 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 4 states have internal predecessors, (5), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 14:13:12,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:12,879 INFO L93 Difference]: Finished difference Result 26 states and 34 transitions. [2024-11-19 14:13:12,881 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 34 transitions. [2024-11-19 14:13:12,884 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:12,890 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 17 states and 23 transitions. [2024-11-19 14:13:12,891 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2024-11-19 14:13:12,891 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2024-11-19 14:13:12,891 INFO L73 IsDeterministic]: Start isDeterministic. Operand 17 states and 23 transitions. [2024-11-19 14:13:12,892 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 14:13:12,893 INFO L218 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-19 14:13:12,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states and 23 transitions. [2024-11-19 14:13:12,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-19 14:13:12,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 10 states have internal predecessors, (10), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-19 14:13:12,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2024-11-19 14:13:12,918 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-19 14:13:12,920 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 14:13:12,926 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-19 14:13:12,926 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-19 14:13:12,926 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 23 transitions. [2024-11-19 14:13:12,928 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:12,929 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:12,929 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:12,930 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 14:13:12,931 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:12,931 INFO L745 eck$LassoCheckResult]: Stem: 74#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 71#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 60#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 61#$Ultimate##0 [2024-11-19 14:13:12,931 INFO L747 eck$LassoCheckResult]: Loop: 61#$Ultimate##0 ~j := #in~j; 68#L18 assume !(~j <= 0); 65#L20 call #t~ret3 := rec1(~j);< 62#$Ultimate##0 ~i := #in~i; 67#L12 assume !(~i <= 0); 66#L14 call #t~ret0 := rec1(~i - 2);< 62#$Ultimate##0 ~i := #in~i; 67#L12 assume ~i <= 0;#res := 0; 72#rec1FINAL assume true; 73#rec1EXIT >#28#return; 63#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 62#$Ultimate##0 ~i := #in~i; 67#L12 assume ~i <= 0;#res := 0; 72#rec1FINAL assume true; 73#rec1EXIT >#30#return; 64#L14-2 call #t~ret2 := rec1(#t~ret1);< 62#$Ultimate##0 ~i := #in~i; 67#L12 assume ~i <= 0;#res := 0; 72#rec1FINAL assume true; 73#rec1EXIT >#32#return; 69#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 70#rec1FINAL assume true; 75#rec1EXIT >#34#return; 59#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 61#$Ultimate##0 [2024-11-19 14:13:12,932 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:12,934 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 2 times [2024-11-19 14:13:12,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:12,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1268502636] [2024-11-19 14:13:12,935 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:12,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:12,943 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2024-11-19 14:13:12,945 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:12,946 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:12,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:12,948 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:12,949 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:12,951 INFO L85 PathProgramCache]: Analyzing trace with hash -204878921, now seen corresponding path program 1 times [2024-11-19 14:13:12,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:12,952 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [6065868] [2024-11-19 14:13:12,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:12,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:12,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:12,985 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:13,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:13,013 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:13,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:13,014 INFO L85 PathProgramCache]: Analyzing trace with hash -482494696, now seen corresponding path program 1 times [2024-11-19 14:13:13,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:13,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1053213867] [2024-11-19 14:13:13,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:13,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:13,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:13,036 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:13,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:13,062 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:13,474 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:13,476 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:13,476 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:13,476 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:13,476 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:13,477 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,477 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:13,477 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:13,477 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-11-19 14:13:13,477 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:13,478 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:13,496 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,505 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,507 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,510 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,519 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,557 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:13,558 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:13,560 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,564 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:13,566 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:13,567 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:13,567 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:13,582 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:13,582 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:13,593 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:13,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,594 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,595 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:13,596 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:13,597 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:13,597 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:13,611 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:13,611 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:13,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:13,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,624 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:13,624 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:13,625 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:13,625 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:13,640 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:13,641 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#t~ret4=0} Honda state: {rec2_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:13,656 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:13,656 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,656 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,657 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:13,658 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:13,659 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:13,659 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:13,685 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:13,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,686 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,687 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:13,688 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:13,689 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:13,689 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:13,702 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:13,717 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:13,717 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:13,717 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:13,717 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:13,717 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:13,717 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:13,717 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,718 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:13,718 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:13,718 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-11-19 14:13:13,718 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:13,718 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:13,719 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,726 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,729 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,732 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,741 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:13,772 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:13,775 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:13,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,777 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:13,778 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:13,779 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:13,789 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:13,789 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:13,790 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:13,790 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:13,790 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:13,791 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:13,792 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:13,793 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:13,803 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-19 14:13:13,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,804 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,805 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:13,806 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:13,807 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:13,817 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:13,817 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:13,817 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:13,818 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:13,818 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:13,818 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:13,818 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:13,820 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:13,830 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:13,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,832 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:13,833 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:13,834 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:13,843 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:13,844 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:13,844 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:13,844 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:13,844 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:13,845 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:13,845 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:13,846 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:13,856 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:13,857 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,857 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,858 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:13,859 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:13,860 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:13,869 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:13,869 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:13,870 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:13,870 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:13,870 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:13,871 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:13,871 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:13,874 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:13,878 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-19 14:13:13,878 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-19 14:13:13,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:13,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:13,881 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:13,883 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:13,884 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:13,884 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:13,884 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:13,885 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2024-11-19 14:13:13,899 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:13,932 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:13,949 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-11-19 14:13:13,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:13,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:13,999 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-19 14:13:14,000 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:14,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:14,055 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-19 14:13:14,058 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:14,218 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-19 14:13:14,222 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 8 loop predicates [2024-11-19 14:13:14,223 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 17 states and 23 transitions. cyclomatic complexity: 8 Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:14,567 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 17 states and 23 transitions. cyclomatic complexity: 8. Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Result 102 states and 148 transitions. Complement of second has 42 states. [2024-11-19 14:13:14,569 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 1 stem states 8 non-accepting loop states 1 accepting loop states [2024-11-19 14:13:14,570 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), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:14,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 37 transitions. [2024-11-19 14:13:14,573 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 24 letters. [2024-11-19 14:13:14,574 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:14,574 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 27 letters. Loop has 24 letters. [2024-11-19 14:13:14,575 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:14,575 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 48 letters. [2024-11-19 14:13:14,576 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:14,576 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 102 states and 148 transitions. [2024-11-19 14:13:14,581 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:14,585 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 102 states to 90 states and 136 transitions. [2024-11-19 14:13:14,585 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 39 [2024-11-19 14:13:14,586 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-11-19 14:13:14,586 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 136 transitions. [2024-11-19 14:13:14,587 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:14,587 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 136 transitions. [2024-11-19 14:13:14,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 136 transitions. [2024-11-19 14:13:14,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 63. [2024-11-19 14:13:14,598 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 34 states have (on average 1.1176470588235294) internal successors, (38), 36 states have internal predecessors, (38), 20 states have call successors, (20), 8 states have call predecessors, (20), 9 states have return successors, (41), 18 states have call predecessors, (41), 16 states have call successors, (41) [2024-11-19 14:13:14,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 99 transitions. [2024-11-19 14:13:14,599 INFO L240 hiAutomatonCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-11-19 14:13:14,600 INFO L425 stractBuchiCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-11-19 14:13:14,600 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-19 14:13:14,600 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 63 states and 99 transitions. [2024-11-19 14:13:14,601 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:14,601 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:14,601 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:14,602 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:14,602 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:14,602 INFO L745 eck$LassoCheckResult]: Stem: 380#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 372#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 340#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 349#$Ultimate##0 ~j := #in~j; 351#L18 assume !(~j <= 0); 344#L20 call #t~ret3 := rec1(~j);< 343#$Ultimate##0 ~i := #in~i; 345#L12 assume !(~i <= 0); 355#L14 call #t~ret0 := rec1(~i - 2);< 370#$Ultimate##0 [2024-11-19 14:13:14,602 INFO L747 eck$LassoCheckResult]: Loop: 370#$Ultimate##0 ~i := #in~i; 389#L12 assume !(~i <= 0); 353#L14 call #t~ret0 := rec1(~i - 2);< 370#$Ultimate##0 [2024-11-19 14:13:14,603 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:14,603 INFO L85 PathProgramCache]: Analyzing trace with hash 838970620, now seen corresponding path program 1 times [2024-11-19 14:13:14,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:14,603 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1220011709] [2024-11-19 14:13:14,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:14,603 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:14,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:14,615 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:14,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:14,623 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:14,625 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:14,625 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2024-11-19 14:13:14,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:14,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [934728709] [2024-11-19 14:13:14,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:14,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:14,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:14,629 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:14,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:14,632 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:14,632 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:14,632 INFO L85 PathProgramCache]: Analyzing trace with hash 1359045147, now seen corresponding path program 2 times [2024-11-19 14:13:14,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:14,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1948338409] [2024-11-19 14:13:14,633 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:14,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:14,638 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:14,638 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:14,638 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:14,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:14,643 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:14,674 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:14,674 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:14,674 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:14,675 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:14,675 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:14,675 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,675 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:14,675 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:14,675 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-11-19 14:13:14,675 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:14,675 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:14,676 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,679 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,681 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,683 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,685 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,691 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,724 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:14,725 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:14,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,727 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:14,728 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:14,729 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:14,729 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:14,743 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:14,743 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:14,757 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:14,758 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,760 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:14,763 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:14,764 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:14,764 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:14,781 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:14,781 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:14,795 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:14,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,798 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:14,799 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:14,800 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:14,800 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:14,817 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:14,817 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:14,831 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-19 14:13:14,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,834 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:14,836 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:14,837 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:14,837 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:14,850 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:14,851 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:14,865 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:14,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,866 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,869 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:14,871 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:14,872 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:14,873 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:14,897 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:14,897 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,898 INFO L229 MonitoredProcess]: Starting monitored process 17 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:14,899 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-19 14:13:14,900 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:14,900 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:14,942 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:14,946 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:14,946 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:14,946 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:14,946 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:14,946 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:14,946 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:14,946 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,946 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:14,946 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:14,946 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-11-19 14:13:14,946 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:14,947 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:14,947 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,950 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,951 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,957 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,959 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,963 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:14,994 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:14,994 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:14,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:14,995 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:14,997 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:14,998 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:14,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:15,009 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,009 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,009 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,009 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,009 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,010 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,010 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,013 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:15,023 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:15,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,025 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:15,026 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:15,027 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:15,036 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,036 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,036 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,037 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,037 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,037 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,037 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,038 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:15,048 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-19 14:13:15,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,050 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:15,051 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:15,052 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:15,061 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,061 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,061 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,061 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,061 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,062 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,062 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,064 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:15,076 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:15,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,078 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:15,079 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:15,079 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:15,088 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,089 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,089 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,089 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,089 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,090 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,090 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,091 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:15,102 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:15,102 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,103 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:15,104 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:15,105 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:15,114 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,114 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,114 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,114 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,114 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,115 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,115 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,117 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:15,124 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-19 14:13:15,124 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:15,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,124 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,126 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:15,127 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:15,127 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:15,127 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:15,127 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:15,127 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-19 14:13:15,137 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-11-19 14:13:15,138 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:15,152 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:15,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:15,178 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 14:13:15,179 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:15,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:15,212 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:15,213 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:15,238 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:15,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:15,239 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 63 states and 99 transitions. cyclomatic complexity: 40 Second operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 14:13:15,294 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 63 states and 99 transitions. cyclomatic complexity: 40. Second operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 109 states and 166 transitions. Complement of second has 17 states. [2024-11-19 14:13:15,294 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:15,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 14:13:15,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2024-11-19 14:13:15,296 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 3 letters. [2024-11-19 14:13:15,296 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:15,296 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 12 letters. Loop has 3 letters. [2024-11-19 14:13:15,296 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:15,296 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 6 letters. [2024-11-19 14:13:15,296 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:15,296 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 109 states and 166 transitions. [2024-11-19 14:13:15,300 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:15,307 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 109 states to 97 states and 154 transitions. [2024-11-19 14:13:15,311 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2024-11-19 14:13:15,312 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-19 14:13:15,312 INFO L73 IsDeterministic]: Start isDeterministic. Operand 97 states and 154 transitions. [2024-11-19 14:13:15,312 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:15,312 INFO L218 hiAutomatonCegarLoop]: Abstraction has 97 states and 154 transitions. [2024-11-19 14:13:15,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states and 154 transitions. [2024-11-19 14:13:15,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 93. [2024-11-19 14:13:15,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 54 states have (on average 1.1481481481481481) internal successors, (62), 60 states have internal predecessors, (62), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (56), 18 states have call predecessors, (56), 22 states have call successors, (56) [2024-11-19 14:13:15,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 144 transitions. [2024-11-19 14:13:15,332 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-11-19 14:13:15,332 INFO L425 stractBuchiCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-11-19 14:13:15,332 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-19 14:13:15,332 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 93 states and 144 transitions. [2024-11-19 14:13:15,335 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:15,336 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:15,336 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:15,337 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:15,337 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:15,337 INFO L745 eck$LassoCheckResult]: Stem: 632#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 622#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 583#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 601#$Ultimate##0 ~j := #in~j; 603#L18 assume !(~j <= 0); 627#L20 call #t~ret3 := rec1(~j);< 631#$Ultimate##0 ~i := #in~i; 649#L12 assume !(~i <= 0); 606#L14 call #t~ret0 := rec1(~i - 2);< 647#$Ultimate##0 ~i := #in~i; 652#L12 assume ~i <= 0;#res := 0; 651#rec1FINAL assume true; 646#rec1EXIT >#28#return; 594#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 588#$Ultimate##0 [2024-11-19 14:13:15,338 INFO L747 eck$LassoCheckResult]: Loop: 588#$Ultimate##0 ~i := #in~i; 596#L12 assume !(~i <= 0); 590#L14 call #t~ret0 := rec1(~i - 2);< 588#$Ultimate##0 [2024-11-19 14:13:15,339 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:15,339 INFO L85 PathProgramCache]: Analyzing trace with hash 372282091, now seen corresponding path program 1 times [2024-11-19 14:13:15,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:15,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1272400077] [2024-11-19 14:13:15,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:15,339 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:15,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:15,345 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:15,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:15,350 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:15,351 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:15,351 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2024-11-19 14:13:15,351 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:15,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [118292869] [2024-11-19 14:13:15,351 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:15,351 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:15,354 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2024-11-19 14:13:15,354 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:15,354 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:15,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:15,356 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:15,357 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:15,357 INFO L85 PathProgramCache]: Analyzing trace with hash 1050214860, now seen corresponding path program 2 times [2024-11-19 14:13:15,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:15,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [138562744] [2024-11-19 14:13:15,357 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:15,357 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:15,365 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:15,368 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:15,433 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 14:13:15,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:15,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [138562744] [2024-11-19 14:13:15,434 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [138562744] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 14:13:15,434 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 14:13:15,434 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-19 14:13:15,434 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495995881] [2024-11-19 14:13:15,434 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 14:13:15,474 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:15,474 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:15,474 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:15,474 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:15,474 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:15,474 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,474 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:15,474 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:15,474 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-11-19 14:13:15,474 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:15,474 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:15,475 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,478 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,505 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,507 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,510 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,512 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,521 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2024-11-19 14:13:15,541 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:15,541 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:15,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,543 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:15,545 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:15,545 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:15,546 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:15,561 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:15,561 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:15,576 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2024-11-19 14:13:15,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,578 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:15,579 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:15,580 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:15,580 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:15,610 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:15,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,610 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,612 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:15,614 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:15,615 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:15,615 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:15,666 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:15,670 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:15,671 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:15,671 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:15,671 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:15,671 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:15,671 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:15,671 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,671 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:15,671 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:15,671 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-11-19 14:13:15,671 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:15,671 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:15,672 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,675 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,680 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,682 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,684 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,689 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:15,716 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:15,716 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:15,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,718 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:15,719 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:15,720 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:15,729 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,730 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,730 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,730 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,730 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,730 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,730 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,731 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:15,741 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-11-19 14:13:15,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,743 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:15,744 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:15,745 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:15,754 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:15,755 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:15,755 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:15,755 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:15,755 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:15,756 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:15,756 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:15,758 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:15,760 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-19 14:13:15,760 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:15,760 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:15,760 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:15,762 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:15,763 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:15,764 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:15,764 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:15,764 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:15,764 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-19 14:13:15,778 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-11-19 14:13:15,779 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:15,790 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:15,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:15,814 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-19 14:13:15,815 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:15,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:15,884 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:15,885 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:15,908 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:15,909 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:15,909 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 93 states and 144 transitions. cyclomatic complexity: 57 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 14:13:15,986 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 93 states and 144 transitions. cyclomatic complexity: 57. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 133 states and 208 transitions. Complement of second has 18 states. [2024-11-19 14:13:15,988 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:15,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 14:13:15,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-11-19 14:13:15,990 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 3 letters. [2024-11-19 14:13:15,990 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:15,990 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 17 letters. Loop has 3 letters. [2024-11-19 14:13:15,990 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:15,990 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 6 letters. [2024-11-19 14:13:15,990 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:15,990 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 133 states and 208 transitions. [2024-11-19 14:13:15,996 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:16,003 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 133 states to 121 states and 196 transitions. [2024-11-19 14:13:16,004 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2024-11-19 14:13:16,004 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 52 [2024-11-19 14:13:16,004 INFO L73 IsDeterministic]: Start isDeterministic. Operand 121 states and 196 transitions. [2024-11-19 14:13:16,004 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:16,004 INFO L218 hiAutomatonCegarLoop]: Abstraction has 121 states and 196 transitions. [2024-11-19 14:13:16,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states and 196 transitions. [2024-11-19 14:13:16,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2024-11-19 14:13:16,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 68 states have (on average 1.1764705882352942) internal successors, (80), 76 states have internal predecessors, (80), 32 states have call successors, (32), 18 states have call predecessors, (32), 17 states have return successors, (74), 22 states have call predecessors, (74), 28 states have call successors, (74) [2024-11-19 14:13:16,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 186 transitions. [2024-11-19 14:13:16,020 INFO L240 hiAutomatonCegarLoop]: Abstraction has 117 states and 186 transitions. [2024-11-19 14:13:16,020 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:16,021 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-19 14:13:16,021 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-19 14:13:16,021 INFO L87 Difference]: Start difference. First operand 117 states and 186 transitions. Second operand has 6 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 14:13:16,059 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:16,062 INFO L93 Difference]: Finished difference Result 130 states and 196 transitions. [2024-11-19 14:13:16,062 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 196 transitions. [2024-11-19 14:13:16,066 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-19 14:13:16,071 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 128 states and 194 transitions. [2024-11-19 14:13:16,071 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2024-11-19 14:13:16,071 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2024-11-19 14:13:16,071 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 194 transitions. [2024-11-19 14:13:16,071 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:16,072 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 194 transitions. [2024-11-19 14:13:16,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 194 transitions. [2024-11-19 14:13:16,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 105. [2024-11-19 14:13:16,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 60 states have (on average 1.1333333333333333) internal successors, (68), 66 states have internal predecessors, (68), 30 states have call successors, (30), 16 states have call predecessors, (30), 15 states have return successors, (60), 22 states have call predecessors, (60), 26 states have call successors, (60) [2024-11-19 14:13:16,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2024-11-19 14:13:16,083 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-11-19 14:13:16,085 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-19 14:13:16,085 INFO L425 stractBuchiCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-11-19 14:13:16,085 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-19 14:13:16,086 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 158 transitions. [2024-11-19 14:13:16,087 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-19 14:13:16,087 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:16,087 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:16,088 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:16,088 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:16,088 INFO L745 eck$LassoCheckResult]: Stem: 1208#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1199#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 1157#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1187#$Ultimate##0 ~j := #in~j; 1223#L18 assume !(~j <= 0); 1214#L20 call #t~ret3 := rec1(~j);< 1222#$Ultimate##0 ~i := #in~i; 1221#L12 assume !(~i <= 0); 1178#L14 call #t~ret0 := rec1(~i - 2);< 1219#$Ultimate##0 ~i := #in~i; 1218#L12 assume !(~i <= 0); 1175#L14 call #t~ret0 := rec1(~i - 2);< 1217#$Ultimate##0 ~i := #in~i; 1205#L12 assume ~i <= 0;#res := 0; 1200#rec1FINAL assume true; 1201#rec1EXIT >#28#return; 1162#L14-1 [2024-11-19 14:13:16,088 INFO L747 eck$LassoCheckResult]: Loop: 1162#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1161#$Ultimate##0 ~i := #in~i; 1164#L12 assume ~i <= 0;#res := 0; 1257#rec1FINAL assume true; 1253#rec1EXIT >#30#return; 1176#L14-2 call #t~ret2 := rec1(#t~ret1);< 1188#$Ultimate##0 ~i := #in~i; 1241#L12 assume !(~i <= 0); 1179#L14 call #t~ret0 := rec1(~i - 2);< 1188#$Ultimate##0 ~i := #in~i; 1241#L12 assume ~i <= 0;#res := 0; 1240#rec1FINAL assume true; 1239#rec1EXIT >#28#return; 1162#L14-1 [2024-11-19 14:13:16,089 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,089 INFO L85 PathProgramCache]: Analyzing trace with hash 1325197585, now seen corresponding path program 1 times [2024-11-19 14:13:16,089 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,089 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1715292600] [2024-11-19 14:13:16,089 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:16,090 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,095 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:16,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,105 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:16,105 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,105 INFO L85 PathProgramCache]: Analyzing trace with hash 949089090, now seen corresponding path program 1 times [2024-11-19 14:13:16,105 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [831229516] [2024-11-19 14:13:16,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:16,106 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:16,166 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 14:13:16,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:16,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [831229516] [2024-11-19 14:13:16,167 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [831229516] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 14:13:16,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1411213388] [2024-11-19 14:13:16,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:16,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 14:13:16,168 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,169 INFO L229 MonitoredProcess]: Starting monitored process 30 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:16,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Waiting until timeout for monitored process [2024-11-19 14:13:16,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:16,206 INFO L255 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-19 14:13:16,207 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:16,222 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 14:13:16,224 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 14:13:16,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1411213388] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 14:13:16,224 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-19 14:13:16,224 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-19 14:13:16,225 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [16136928] [2024-11-19 14:13:16,225 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 14:13:16,225 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 14:13:16,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:16,225 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-19 14:13:16,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-19 14:13:16,226 INFO L87 Difference]: Start difference. First operand 105 states and 158 transitions. cyclomatic complexity: 59 Second operand has 6 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-19 14:13:16,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:16,262 INFO L93 Difference]: Finished difference Result 120 states and 174 transitions. [2024-11-19 14:13:16,262 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 120 states and 174 transitions. [2024-11-19 14:13:16,264 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:16,266 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 120 states to 115 states and 165 transitions. [2024-11-19 14:13:16,266 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2024-11-19 14:13:16,266 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2024-11-19 14:13:16,266 INFO L73 IsDeterministic]: Start isDeterministic. Operand 115 states and 165 transitions. [2024-11-19 14:13:16,266 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:16,266 INFO L218 hiAutomatonCegarLoop]: Abstraction has 115 states and 165 transitions. [2024-11-19 14:13:16,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states and 165 transitions. [2024-11-19 14:13:16,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 112. [2024-11-19 14:13:16,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 64 states have (on average 1.109375) internal successors, (71), 69 states have internal predecessors, (71), 32 states have call successors, (32), 18 states have call predecessors, (32), 16 states have return successors, (59), 24 states have call predecessors, (59), 28 states have call successors, (59) [2024-11-19 14:13:16,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 162 transitions. [2024-11-19 14:13:16,278 INFO L240 hiAutomatonCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-11-19 14:13:16,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-19 14:13:16,280 INFO L425 stractBuchiCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-11-19 14:13:16,280 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-19 14:13:16,280 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 112 states and 162 transitions. [2024-11-19 14:13:16,281 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-19 14:13:16,281 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:16,281 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:16,283 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:16,283 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:16,283 INFO L745 eck$LassoCheckResult]: Stem: 1489#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1475#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 1431#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1459#$Ultimate##0 ~j := #in~j; 1500#L18 assume !(~j <= 0); 1445#L20 call #t~ret3 := rec1(~j);< 1499#$Ultimate##0 ~i := #in~i; 1498#L12 assume !(~i <= 0); 1462#L14 call #t~ret0 := rec1(~i - 2);< 1497#$Ultimate##0 ~i := #in~i; 1495#L12 assume !(~i <= 0); 1468#L14 call #t~ret0 := rec1(~i - 2);< 1494#$Ultimate##0 ~i := #in~i; 1496#L12 assume ~i <= 0;#res := 0; 1476#rec1FINAL assume true; 1477#rec1EXIT >#28#return; 1471#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1472#$Ultimate##0 ~i := #in~i; 1508#L12 assume ~i <= 0;#res := 0; 1507#rec1FINAL assume true; 1505#rec1EXIT >#30#return; 1436#L14-2 call #t~ret2 := rec1(#t~ret1);< 1435#$Ultimate##0 ~i := #in~i; 1437#L12 assume ~i <= 0;#res := 0; 1484#rec1FINAL assume true; 1480#rec1EXIT >#32#return; 1481#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 1510#rec1FINAL assume true; 1509#rec1EXIT >#28#return; 1464#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1486#$Ultimate##0 [2024-11-19 14:13:16,283 INFO L747 eck$LassoCheckResult]: Loop: 1486#$Ultimate##0 ~i := #in~i; 1512#L12 assume !(~i <= 0); 1465#L14 call #t~ret0 := rec1(~i - 2);< 1486#$Ultimate##0 [2024-11-19 14:13:16,284 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,284 INFO L85 PathProgramCache]: Analyzing trace with hash 1060897207, now seen corresponding path program 1 times [2024-11-19 14:13:16,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1943172871] [2024-11-19 14:13:16,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 14:13:16,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,292 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:16,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,299 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:16,300 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,300 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 3 times [2024-11-19 14:13:16,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [773237265] [2024-11-19 14:13:16,300 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 14:13:16,300 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,302 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2024-11-19 14:13:16,303 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:16,303 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:16,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:16,304 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:16,305 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:16,305 INFO L85 PathProgramCache]: Analyzing trace with hash -1475637376, now seen corresponding path program 2 times [2024-11-19 14:13:16,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:16,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [69021913] [2024-11-19 14:13:16,305 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:16,305 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:16,319 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:16,319 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:16,411 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-19 14:13:16,411 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:16,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [69021913] [2024-11-19 14:13:16,412 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [69021913] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 14:13:16,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2060599879] [2024-11-19 14:13:16,412 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:16,412 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 14:13:16,412 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,414 INFO L229 MonitoredProcess]: Starting monitored process 31 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:16,419 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Waiting until timeout for monitored process [2024-11-19 14:13:16,451 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:16,451 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:16,452 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:16,453 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:16,478 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-19 14:13:16,478 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 14:13:16,580 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-19 14:13:16,581 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2060599879] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 14:13:16,581 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 14:13:16,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-11-19 14:13:16,581 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [463638645] [2024-11-19 14:13:16,581 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 14:13:16,614 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:16,614 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:16,615 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:16,615 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:16,615 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:16,615 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,615 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:16,615 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:16,615 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-11-19 14:13:16,615 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:16,615 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:16,616 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,618 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,620 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,621 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,623 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,625 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,651 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:16,652 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:16,652 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,654 INFO L229 MonitoredProcess]: Starting monitored process 32 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,657 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-19 14:13:16,658 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,658 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,671 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:16,672 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:16,687 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,690 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,690 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,692 INFO L229 MonitoredProcess]: Starting monitored process 33 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,693 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-19 14:13:16,695 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,695 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,708 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:16,708 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:16,725 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,728 INFO L229 MonitoredProcess]: Starting monitored process 34 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,729 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-19 14:13:16,730 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,730 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,747 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:16,747 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret2=0} Honda state: {rec1_#t~ret2=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:16,761 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,761 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,761 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,764 INFO L229 MonitoredProcess]: Starting monitored process 35 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,766 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,766 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,771 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-19 14:13:16,784 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:16,784 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:16,797 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,798 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,800 INFO L229 MonitoredProcess]: Starting monitored process 36 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,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-19 14:13:16,802 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,802 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,817 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:16,817 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:16,830 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,831 INFO L229 MonitoredProcess]: Starting monitored process 37 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,845 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-19 14:13:16,847 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:16,847 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,861 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:16,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,872 INFO L229 MonitoredProcess]: Starting monitored process 38 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,873 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:16,873 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:16,874 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-19 14:13:16,918 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:16,922 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,922 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:16,922 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:16,922 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:16,922 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:16,922 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:16,923 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,923 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:16,923 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:16,923 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-11-19 14:13:16,923 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:16,924 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:16,925 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,928 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,931 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,933 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,935 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,937 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:16,971 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:16,971 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:16,971 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,973 INFO L229 MonitoredProcess]: Starting monitored process 39 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,973 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-19 14:13:16,974 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,984 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:16,984 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:16,984 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:16,984 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:16,984 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:16,985 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:16,985 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:16,986 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:16,996 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:16,997 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:16,997 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:16,998 INFO L229 MonitoredProcess]: Starting monitored process 40 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,999 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-11-19 14:13:17,001 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:17,010 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:17,011 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:17,011 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:17,011 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:17,011 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:17,011 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:17,012 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:17,013 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:17,023 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:17,023 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:17,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:17,024 INFO L229 MonitoredProcess]: Starting monitored process 41 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:17,025 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-19 14:13:17,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:17,035 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:17,035 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:17,035 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:17,035 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:17,036 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:17,036 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:17,036 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:17,038 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:17,052 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-11-19 14:13:17,053 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:17,053 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:17,055 INFO L229 MonitoredProcess]: Starting monitored process 42 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:17,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-19 14:13:17,058 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:17,070 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:17,070 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:17,070 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:17,070 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:17,070 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:17,071 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:17,071 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:17,073 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:17,087 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Ended with exit code 0 [2024-11-19 14:13:17,088 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:17,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:17,089 INFO L229 MonitoredProcess]: Starting monitored process 43 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:17,092 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2024-11-19 14:13:17,093 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:17,105 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:17,105 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:17,106 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:17,106 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:17,106 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:17,106 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:17,106 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:17,109 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-19 14:13:17,123 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2024-11-19 14:13:17,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:17,125 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:17,126 INFO L229 MonitoredProcess]: Starting monitored process 44 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:17,130 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2024-11-19 14:13:17,131 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:17,143 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:17,143 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:17,143 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:17,144 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:17,144 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:17,144 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:17,145 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:17,147 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:17,149 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-19 14:13:17,149 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:17,150 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:17,150 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:17,151 INFO L229 MonitoredProcess]: Starting monitored process 45 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:17,152 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2024-11-19 14:13:17,153 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:17,154 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:17,154 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:17,154 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-19 14:13:17,167 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Ended with exit code 0 [2024-11-19 14:13:17,168 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:17,183 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:17,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:17,227 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 14:13:17,229 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:17,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:17,489 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:17,490 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:17,511 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:17,512 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:17,513 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:17,565 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 129 states and 180 transitions. Complement of second has 9 states. [2024-11-19 14:13:17,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2024-11-19 14:13:17,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:17,568 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-19 14:13:17,568 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-19 14:13:17,569 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:17,569 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:17,581 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:17,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:17,625 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 14:13:17,626 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:17,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:17,824 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:17,825 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:17,845 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:17,846 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:17,846 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:17,902 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 129 states and 180 transitions. Complement of second has 9 states. [2024-11-19 14:13:17,905 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2024-11-19 14:13:17,906 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:17,906 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-19 14:13:17,906 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-19 14:13:17,906 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:17,906 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:17,919 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:17,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:17,959 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 14:13:17,961 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:18,156 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:18,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:18,218 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:18,219 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:18,241 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:18,241 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:18,242 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:18,331 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 112 states and 162 transitions. cyclomatic complexity: 56. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 157 states and 219 transitions. Complement of second has 17 states. [2024-11-19 14:13:18,332 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:18,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:18,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-11-19 14:13:18,333 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-19 14:13:18,333 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:18,333 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-11-19 14:13:18,333 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:18,333 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-11-19 14:13:18,334 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:18,334 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 157 states and 219 transitions. [2024-11-19 14:13:18,336 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-19 14:13:18,338 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 157 states to 139 states and 201 transitions. [2024-11-19 14:13:18,338 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 55 [2024-11-19 14:13:18,338 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 58 [2024-11-19 14:13:18,339 INFO L73 IsDeterministic]: Start isDeterministic. Operand 139 states and 201 transitions. [2024-11-19 14:13:18,339 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:18,339 INFO L218 hiAutomatonCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-11-19 14:13:18,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states and 201 transitions. [2024-11-19 14:13:18,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 120. [2024-11-19 14:13:18,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 70 states have (on average 1.1285714285714286) internal successors, (79), 75 states have internal predecessors, (79), 32 states have call successors, (32), 20 states have call predecessors, (32), 18 states have return successors, (59), 24 states have call predecessors, (59), 28 states have call successors, (59) [2024-11-19 14:13:18,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 170 transitions. [2024-11-19 14:13:18,349 INFO L240 hiAutomatonCegarLoop]: Abstraction has 120 states and 170 transitions. [2024-11-19 14:13:18,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:18,350 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 14:13:18,350 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-19 14:13:18,350 INFO L87 Difference]: Start difference. First operand 120 states and 170 transitions. Second operand has 8 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 14:13:18,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:18,393 INFO L93 Difference]: Finished difference Result 98 states and 116 transitions. [2024-11-19 14:13:18,393 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 98 states and 116 transitions. [2024-11-19 14:13:18,394 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-19 14:13:18,395 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 98 states to 63 states and 75 transitions. [2024-11-19 14:13:18,395 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2024-11-19 14:13:18,395 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 12 [2024-11-19 14:13:18,395 INFO L73 IsDeterministic]: Start isDeterministic. Operand 63 states and 75 transitions. [2024-11-19 14:13:18,395 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-19 14:13:18,395 INFO L218 hiAutomatonCegarLoop]: Abstraction has 63 states and 75 transitions. [2024-11-19 14:13:18,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states and 75 transitions. [2024-11-19 14:13:18,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-11-19 14:13:18,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 33 states have (on average 1.121212121212121) internal successors, (37), 36 states have internal predecessors, (37), 14 states have call successors, (14), 10 states have call predecessors, (14), 7 states have return successors, (14), 7 states have call predecessors, (14), 10 states have call successors, (14) [2024-11-19 14:13:18,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2024-11-19 14:13:18,398 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-19 14:13:18,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 14:13:18,399 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-19 14:13:18,400 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-19 14:13:18,400 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 65 transitions. [2024-11-19 14:13:18,400 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-19 14:13:18,400 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 14:13:18,400 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 14:13:18,401 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 14:13:18,401 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-19 14:13:18,401 INFO L745 eck$LassoCheckResult]: Stem: 2776#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 2770#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet5#1, main_#t~ret6#1, main_~x~0#1;havoc main_#t~nondet5#1;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 2746#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 2755#$Ultimate##0 ~j := #in~j; 2756#L18 assume !(~j <= 0); 2768#L20 call #t~ret3 := rec1(~j);< 2794#$Ultimate##0 ~i := #in~i; 2791#L12 assume !(~i <= 0); 2763#L14 call #t~ret0 := rec1(~i - 2);< 2793#$Ultimate##0 ~i := #in~i; 2798#L12 assume ~i <= 0;#res := 0; 2797#rec1FINAL assume true; 2772#rec1EXIT >#28#return; 2767#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 2769#$Ultimate##0 ~i := #in~i; 2790#L12 assume ~i <= 0;#res := 0; 2789#rec1FINAL assume true; 2783#rec1EXIT >#30#return; 2781#L14-2 call #t~ret2 := rec1(#t~ret1);< 2766#$Ultimate##0 ~i := #in~i; 2785#L12 assume ~i <= 0;#res := 0; 2782#rec1FINAL assume true; 2780#rec1EXIT >#32#return; 2779#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 2778#rec1FINAL assume true; 2777#rec1EXIT >#34#return; 2745#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 2747#$Ultimate##0 ~j := #in~j; 2757#L18 assume !(~j <= 0); 2751#L20 call #t~ret3 := rec1(~j);< 2748#$Ultimate##0 [2024-11-19 14:13:18,401 INFO L747 eck$LassoCheckResult]: Loop: 2748#$Ultimate##0 ~i := #in~i; 2750#L12 assume !(~i <= 0); 2749#L14 call #t~ret0 := rec1(~i - 2);< 2748#$Ultimate##0 [2024-11-19 14:13:18,402 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:18,402 INFO L85 PathProgramCache]: Analyzing trace with hash 1256061253, now seen corresponding path program 2 times [2024-11-19 14:13:18,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:18,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2066498653] [2024-11-19 14:13:18,402 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:18,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:18,409 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:18,409 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:18,470 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-19 14:13:18,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 14:13:18,471 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2066498653] [2024-11-19 14:13:18,471 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2066498653] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 14:13:18,471 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1121813719] [2024-11-19 14:13:18,471 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 14:13:18,471 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 14:13:18,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:18,473 INFO L229 MonitoredProcess]: Starting monitored process 46 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:18,475 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Waiting until timeout for monitored process [2024-11-19 14:13:18,512 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 14:13:18,513 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 14:13:18,513 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:18,514 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:18,530 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-19 14:13:18,530 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 14:13:18,623 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-19 14:13:18,624 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1121813719] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 14:13:18,624 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 14:13:18,624 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-11-19 14:13:18,624 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1471769921] [2024-11-19 14:13:18,624 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 14:13:18,624 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-19 14:13:18,625 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:18,625 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 4 times [2024-11-19 14:13:18,625 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 14:13:18,625 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [511803593] [2024-11-19 14:13:18,625 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 14:13:18,625 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 14:13:18,630 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 14:13:18,630 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 14:13:18,630 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 14:13:18,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 14:13:18,632 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 14:13:18,658 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:18,658 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:18,658 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:18,658 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:18,658 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-19 14:13:18,658 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,658 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:18,658 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:18,658 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-11-19 14:13:18,659 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:18,659 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:18,659 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,661 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,665 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,667 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,669 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,671 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,699 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:18,700 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-19 14:13:18,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,700 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:18,702 INFO L229 MonitoredProcess]: Starting monitored process 47 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:18,702 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2024-11-19 14:13:18,704 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:18,704 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:18,718 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-19 14:13:18,718 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-19 14:13:18,732 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:18,732 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,733 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:18,734 INFO L229 MonitoredProcess]: Starting monitored process 48 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:18,737 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Waiting until timeout for monitored process [2024-11-19 14:13:18,738 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-19 14:13:18,738 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:18,765 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Ended with exit code 0 [2024-11-19 14:13:18,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:18,767 INFO L229 MonitoredProcess]: Starting monitored process 49 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:18,768 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Waiting until timeout for monitored process [2024-11-19 14:13:18,769 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-19 14:13:18,769 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-19 14:13:18,824 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-19 14:13:18,829 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:18,830 INFO L204 LassoAnalysis]: Preferences: [2024-11-19 14:13:18,830 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-19 14:13:18,830 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-19 14:13:18,830 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-19 14:13:18,830 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-19 14:13:18,830 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,830 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-19 14:13:18,830 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-19 14:13:18,830 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-11-19 14:13:18,830 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-19 14:13:18,830 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-19 14:13:18,831 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,837 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,839 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,841 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,842 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,844 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-19 14:13:18,868 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-19 14:13:18,868 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-19 14:13:18,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,869 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:18,870 INFO L229 MonitoredProcess]: Starting monitored process 50 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:18,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Waiting until timeout for monitored process [2024-11-19 14:13:18,872 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:18,883 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-19 14:13:18,883 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-19 14:13:18,884 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-19 14:13:18,884 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-19 14:13:18,884 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-19 14:13:18,884 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-19 14:13:18,884 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-19 14:13:18,887 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-19 14:13:18,889 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-19 14:13:18,889 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-19 14:13:18,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 14:13:18,890 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 14:13:18,891 INFO L229 MonitoredProcess]: Starting monitored process 51 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:18,892 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Waiting until timeout for monitored process [2024-11-19 14:13:18,893 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-19 14:13:18,893 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-19 14:13:18,893 INFO L474 LassoAnalysis]: Proved termination. [2024-11-19 14:13:18,893 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-19 14:13:18,907 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Ended with exit code 0 [2024-11-19 14:13:18,907 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-19 14:13:18,918 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:18,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:18,954 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 14:13:18,955 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:19,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:19,148 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:19,149 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:19,172 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:19,173 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:19,173 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:19,237 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 64 states and 76 transitions. Complement of second has 15 states. [2024-11-19 14:13:19,237 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:19,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:19,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-19 14:13:19,238 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-19 14:13:19,239 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:19,239 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:19,250 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:19,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:19,295 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 14:13:19,297 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:19,423 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:19,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:19,525 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:19,526 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:19,547 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:19,548 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:19,548 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:19,606 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 64 states and 76 transitions. Complement of second has 15 states. [2024-11-19 14:13:19,607 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:19,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:19,608 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-19 14:13:19,608 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-19 14:13:19,608 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:19,608 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-19 14:13:19,619 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 14:13:19,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:19,661 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 14:13:19,662 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:19,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 14:13:19,845 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 14:13:19,846 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 14:13:19,867 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:19,868 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:19,868 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15 Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:19,947 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 65 transitions. cyclomatic complexity: 15. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Result 78 states and 90 transitions. Complement of second has 15 states. [2024-11-19 14:13:19,948 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:19,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 14:13:19,949 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-11-19 14:13:19,949 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-19 14:13:19,949 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:19,949 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-11-19 14:13:19,950 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:19,950 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-11-19 14:13:19,950 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-19 14:13:19,950 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 78 states and 90 transitions. [2024-11-19 14:13:19,951 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 14:13:19,951 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 78 states to 0 states and 0 transitions. [2024-11-19 14:13:19,951 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-19 14:13:19,951 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-19 14:13:19,951 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-19 14:13:19,951 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 14:13:19,951 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:19,951 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:19,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 14:13:19,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 14:13:19,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-19 14:13:19,954 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 8 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 14:13:19,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 14:13:19,954 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-11-19 14:13:19,954 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-11-19 14:13:19,954 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 14:13:19,954 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-11-19 14:13:19,954 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-19 14:13:19,954 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-19 14:13:19,954 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-19 14:13:19,955 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 14:13:19,955 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:19,955 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:19,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-19 14:13:19,955 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-19 14:13:19,955 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-19 14:13:19,955 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-19 14:13:19,956 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-19 14:13:19,956 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-19 14:13:19,963 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 19.11 02:13:19 BoogieIcfgContainer [2024-11-19 14:13:19,964 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-19 14:13:19,964 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-19 14:13:19,964 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-19 14:13:19,964 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-19 14:13:19,965 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:12" (3/4) ... [2024-11-19 14:13:19,967 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-19 14:13:19,968 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-19 14:13:19,969 INFO L158 Benchmark]: Toolchain (without parser) took 8147.34ms. Allocated memory was 176.2MB in the beginning and 213.9MB in the end (delta: 37.7MB). Free memory was 116.8MB in the beginning and 116.4MB in the end (delta: 309.4kB). Peak memory consumption was 39.1MB. Max. memory is 16.1GB. [2024-11-19 14:13:19,969 INFO L158 Benchmark]: CDTParser took 0.51ms. Allocated memory is still 96.5MB. Free memory is still 47.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 14:13:19,969 INFO L158 Benchmark]: CACSL2BoogieTranslator took 257.40ms. Allocated memory is still 176.2MB. Free memory was 116.8MB in the beginning and 146.4MB in the end (delta: -29.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-19 14:13:19,969 INFO L158 Benchmark]: Boogie Procedure Inliner took 28.87ms. Allocated memory is still 176.2MB. Free memory was 146.4MB in the beginning and 145.3MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 14:13:19,969 INFO L158 Benchmark]: Boogie Preprocessor took 23.04ms. Allocated memory is still 176.2MB. Free memory was 145.3MB in the beginning and 144.1MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 14:13:19,970 INFO L158 Benchmark]: RCFGBuilder took 276.48ms. Allocated memory is still 176.2MB. Free memory was 144.1MB in the beginning and 132.7MB in the end (delta: 11.4MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-19 14:13:19,970 INFO L158 Benchmark]: BuchiAutomizer took 7552.38ms. Allocated memory was 176.2MB in the beginning and 213.9MB in the end (delta: 37.7MB). Free memory was 132.7MB in the beginning and 117.5MB in the end (delta: 15.2MB). Peak memory consumption was 53.9MB. Max. memory is 16.1GB. [2024-11-19 14:13:19,970 INFO L158 Benchmark]: Witness Printer took 3.91ms. Allocated memory is still 213.9MB. Free memory was 117.5MB in the beginning and 116.4MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 14:13:19,972 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.51ms. Allocated memory is still 96.5MB. Free memory is still 47.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 257.40ms. Allocated memory is still 176.2MB. Free memory was 116.8MB in the beginning and 146.4MB in the end (delta: -29.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 28.87ms. Allocated memory is still 176.2MB. Free memory was 146.4MB in the beginning and 145.3MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 23.04ms. Allocated memory is still 176.2MB. Free memory was 145.3MB in the beginning and 144.1MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 276.48ms. Allocated memory is still 176.2MB. Free memory was 144.1MB in the beginning and 132.7MB in the end (delta: 11.4MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * BuchiAutomizer took 7552.38ms. Allocated memory was 176.2MB in the beginning and 213.9MB in the end (delta: 37.7MB). Free memory was 132.7MB in the beginning and 117.5MB in the end (delta: 15.2MB). Peak memory consumption was 53.9MB. Max. memory is 16.1GB. * Witness Printer took 3.91ms. Allocated memory is still 213.9MB. Free memory was 117.5MB in the beginning and 116.4MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(j) and consists of 10 locations. One deterministic module has affine ranking function \old(i) and consists of 5 locations. One deterministic module has affine ranking function \old(i) and consists of 6 locations. One nondeterministic module has affine ranking function \old(i) and consists of 6 locations. One nondeterministic module has affine ranking function \old(i) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 8 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 7.4s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 3.7s. Construction of modules took 0.3s. Büchi inclusion checks took 3.1s. Highest rank in rank-based complementation 3. Minimization of det autom 3. Minimization of nondet autom 7. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 89 StatesRemovedByMinimization, 7 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 [3, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 22/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 195 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 172 mSDsluCounter, 535 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 336 mSDsCounter, 131 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 334 IncrementalHoareTripleChecker+Invalid, 465 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 131 mSolverCounterUnsat, 199 mSDtfsCounter, 334 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI2 SFLT2 conc0 concLT2 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital11 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq147 hnf94 smp100 dnf100 smp100 tf112 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 17ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 14 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.6s 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:19,996 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Ended with exit code 0 [2024-11-19 14:13:20,195 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Ended with exit code 0 [2024-11-19 14:13:20,396 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Forceful destruction successful, exit code 0 [2024-11-19 14:13:20,596 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