./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 c7c6ca5d 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-?-c7c6ca5-m [2024-11-09 15:18:32,437 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 15:18:32,489 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-09 15:18:32,496 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 15:18:32,497 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 15:18:32,515 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 15:18:32,516 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 15:18:32,516 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 15:18:32,516 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 15:18:32,516 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 15:18:32,517 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 15:18:32,517 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 15:18:32,517 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 15:18:32,517 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 15:18:32,518 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 15:18:32,518 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 15:18:32,518 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 15:18:32,519 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 15:18:32,519 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 15:18:32,519 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 15:18:32,520 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 15:18:32,520 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 15:18:32,520 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 15:18:32,520 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 15:18:32,521 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 15:18:32,521 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 15:18:32,521 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 15:18:32,521 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 15:18:32,522 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 15:18:32,522 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 15:18:32,522 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 15:18:32,522 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 15:18:32,522 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 15:18:32,523 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 15:18:32,523 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 15:18:32,523 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 15:18:32,524 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-09 15:18:32,801 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 15:18:32,832 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 15:18:32,838 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 15:18:32,839 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 15:18:32,842 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 15:18:32,843 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-09 15:18:34,137 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 15:18:34,302 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 15:18:34,302 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-11-09 15:18:34,308 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/76fcda270/dbabc14cd0cd49128c3604bbc71db745/FLAG97aa7f8f8 [2024-11-09 15:18:34,322 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/76fcda270/dbabc14cd0cd49128c3604bbc71db745 [2024-11-09 15:18:34,324 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 15:18:34,325 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 15:18:34,326 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 15:18:34,326 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 15:18:34,331 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 15:18:34,331 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,332 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3ebe421f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34, skipping insertion in model container [2024-11-09 15:18:34,332 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,346 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 15:18:34,473 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 15:18:34,479 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 15:18:34,491 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 15:18:34,505 INFO L204 MainTranslator]: Completed translation [2024-11-09 15:18:34,505 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34 WrapperNode [2024-11-09 15:18:34,505 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 15:18:34,506 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 15:18:34,506 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 15:18:34,507 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 15:18:34,512 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,515 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,528 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-11-09 15:18:34,528 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 15:18:34,529 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 15:18:34,529 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 15:18:34,529 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 15:18:34,537 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,538 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,538 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,542 INFO L175 MemorySlicer]: No memory access in input program. [2024-11-09 15:18:34,542 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,543 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,544 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,545 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,545 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,546 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,547 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 15:18:34,547 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 15:18:34,548 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 15:18:34,548 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 15:18:34,548 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (1/1) ... [2024-11-09 15:18:34,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:34,568 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:34,580 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-09 15:18:34,582 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-09 15:18:34,616 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2024-11-09 15:18:34,616 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2024-11-09 15:18:34,616 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2024-11-09 15:18:34,616 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2024-11-09 15:18:34,616 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 15:18:34,616 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 15:18:34,679 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 15:18:34,681 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 15:18:34,846 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-09 15:18:34,846 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 15:18:34,858 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 15:18:34,858 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 15:18:34,858 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:18:34 BoogieIcfgContainer [2024-11-09 15:18:34,858 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 15:18:34,859 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 15:18:34,859 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 15:18:34,862 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 15:18:34,863 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:18:34,863 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 03:18:34" (1/3) ... [2024-11-09 15:18:34,863 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@389d85c6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 03:18:34, skipping insertion in model container [2024-11-09 15:18:34,863 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:18:34,864 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:34" (2/3) ... [2024-11-09 15:18:34,864 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@389d85c6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 03:18:34, skipping insertion in model container [2024-11-09 15:18:34,864 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:18:34,864 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:18:34" (3/3) ... [2024-11-09 15:18:34,865 INFO L332 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2024-11-09 15:18:34,902 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 15:18:34,903 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 15:18:34,903 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 15:18:34,903 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 15:18:34,903 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 15:18:34,903 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 15:18:34,903 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 15:18:34,903 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 15:18:34,906 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-09 15:18:34,920 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:34,920 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:34,920 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:34,924 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 15:18:34,924 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:34,924 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 15:18:34,925 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-09 15:18:34,926 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:34,926 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:34,926 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:34,927 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 15:18:34,927 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:34,932 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-09 15:18:34,932 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-09 15:18:34,936 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:34,936 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 1 times [2024-11-09 15:18:34,943 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:34,943 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1797546154] [2024-11-09 15:18:34,943 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:34,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:34,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:34,995 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:34,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,009 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:35,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:35,011 INFO L85 PathProgramCache]: Analyzing trace with hash -1074209557, now seen corresponding path program 1 times [2024-11-09 15:18:35,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:35,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [698764280] [2024-11-09 15:18:35,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:35,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:35,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:35,077 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 15:18:35,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:35,120 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-09 15:18:35,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 15:18:35,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [698764280] [2024-11-09 15:18:35,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [698764280] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 15:18:35,121 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 15:18:35,121 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 15:18:35,122 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1157533441] [2024-11-09 15:18:35,122 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 15:18:35,125 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 15:18:35,126 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 15:18:35,151 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 15:18:35,152 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 15:18:35,154 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-09 15:18:35,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 15:18:35,229 INFO L93 Difference]: Finished difference Result 26 states and 34 transitions. [2024-11-09 15:18:35,230 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 34 transitions. [2024-11-09 15:18:35,232 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:35,239 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 17 states and 23 transitions. [2024-11-09 15:18:35,239 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2024-11-09 15:18:35,240 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2024-11-09 15:18:35,240 INFO L73 IsDeterministic]: Start isDeterministic. Operand 17 states and 23 transitions. [2024-11-09 15:18:35,241 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 15:18:35,241 INFO L218 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-09 15:18:35,252 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states and 23 transitions. [2024-11-09 15:18:35,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-09 15:18:35,262 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-09 15:18:35,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2024-11-09 15:18:35,263 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-09 15:18:35,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 15:18:35,267 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-11-09 15:18:35,267 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 15:18:35,267 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 23 transitions. [2024-11-09 15:18:35,268 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:35,268 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:35,268 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:35,269 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 15:18:35,269 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:35,269 INFO L745 eck$LassoCheckResult]: Stem: 78#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 75#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; 64#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 65#$Ultimate##0 [2024-11-09 15:18:35,270 INFO L747 eck$LassoCheckResult]: Loop: 65#$Ultimate##0 ~j := #in~j; 72#L18 assume !(~j <= 0); 70#L20 call #t~ret3 := rec1(~j);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume !(~i <= 0); 67#L14 call #t~ret0 := rec1(~i - 2);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume ~i <= 0;#res := 0; 76#rec1FINAL assume true; 77#rec1EXIT >#28#return; 68#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume ~i <= 0;#res := 0; 76#rec1FINAL assume true; 77#rec1EXIT >#30#return; 69#L14-2 call #t~ret2 := rec1(#t~ret1);< 66#$Ultimate##0 ~i := #in~i; 71#L12 assume ~i <= 0;#res := 0; 76#rec1FINAL assume true; 77#rec1EXIT >#32#return; 73#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 74#rec1FINAL assume true; 79#rec1EXIT >#34#return; 63#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 65#$Ultimate##0 [2024-11-09 15:18:35,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:35,270 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 2 times [2024-11-09 15:18:35,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:35,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1953484081] [2024-11-09 15:18:35,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:35,271 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:35,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,274 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:35,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,276 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:35,277 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:35,277 INFO L85 PathProgramCache]: Analyzing trace with hash -204878921, now seen corresponding path program 1 times [2024-11-09 15:18:35,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:35,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1349387598] [2024-11-09 15:18:35,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:35,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:35,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,291 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:35,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,303 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:35,304 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:35,304 INFO L85 PathProgramCache]: Analyzing trace with hash -482494696, now seen corresponding path program 1 times [2024-11-09 15:18:35,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:35,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [744939906] [2024-11-09 15:18:35,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:35,305 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:35,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,317 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:35,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:35,328 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:35,645 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:35,645 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:35,646 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:35,646 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:35,646 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:35,646 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,646 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:35,646 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:35,646 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-11-09 15:18:35,646 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:35,647 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:35,657 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,663 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,665 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,667 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,673 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,701 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:35,702 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:35,703 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,705 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-09 15:18:35,707 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-09 15:18:35,707 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:35,712 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:35,727 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:35,727 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:35,738 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-09 15:18:35,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,742 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-09 15:18:35,750 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-09 15:18:35,751 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:35,751 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:35,763 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:35,763 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:35,774 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-09 15:18:35,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,776 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-09 15:18:35,778 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-09 15:18:35,778 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:35,778 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:35,789 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:35,790 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-09 15:18:35,800 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-09 15:18:35,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,802 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-09 15:18:35,803 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-09 15:18:35,804 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:35,804 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:35,826 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-09 15:18:35,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,828 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-09 15:18:35,829 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-09 15:18:35,831 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:35,831 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:35,843 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:35,855 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:35,856 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:35,856 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:35,856 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:35,856 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:35,856 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:35,856 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,856 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:35,856 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:35,856 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-11-09 15:18:35,856 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:35,856 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:35,857 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,860 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,862 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,864 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,869 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:35,892 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:35,895 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:35,896 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,898 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-09 15:18:35,899 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-09 15:18:35,900 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-09 15:18:35,910 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:35,910 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:35,911 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:35,911 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:35,911 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:35,912 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:35,913 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:35,917 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:35,927 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-09 15:18:35,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,929 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 15:18:35,930 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-09 15:18:35,931 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-09 15:18:35,941 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:35,941 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:35,941 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:35,941 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:35,941 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:35,942 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:35,942 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:35,943 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:35,953 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-09 15:18:35,954 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,954 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,955 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-09 15:18:35,956 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-09 15:18:35,957 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-09 15:18:35,967 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:35,967 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:35,967 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:35,967 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:35,968 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:35,968 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:35,968 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:35,970 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:35,980 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-09 15:18:35,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:35,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:35,982 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 15:18:35,986 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 15:18:35,986 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-09 15:18:35,996 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:35,996 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:35,996 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:35,996 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:35,997 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:35,997 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:35,998 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:35,999 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:36,003 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 15:18:36,003 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 15:18:36,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,029 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-09 15:18:36,030 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-09 15:18:36,031 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:36,031 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:36,031 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:36,032 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2024-11-09 15:18:36,042 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-09 15:18:36,045 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:36,068 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:36,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:36,087 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 15:18:36,088 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:36,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:36,140 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 15:18:36,142 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:36,297 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-09 15:18:36,300 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-09 15:18:36,302 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-09 15:18:36,492 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:36,579 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-09 15:18:36,581 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-09 15:18:36,582 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-09 15:18:36,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 37 transitions. [2024-11-09 15:18:36,587 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 24 letters. [2024-11-09 15:18:36,588 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:36,588 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 27 letters. Loop has 24 letters. [2024-11-09 15:18:36,588 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:36,589 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 48 letters. [2024-11-09 15:18:36,589 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:36,589 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 102 states and 148 transitions. [2024-11-09 15:18:36,593 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:36,596 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 102 states to 90 states and 136 transitions. [2024-11-09 15:18:36,596 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 39 [2024-11-09 15:18:36,596 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-11-09 15:18:36,596 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 136 transitions. [2024-11-09 15:18:36,597 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:36,597 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 136 transitions. [2024-11-09 15:18:36,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 136 transitions. [2024-11-09 15:18:36,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 63. [2024-11-09 15:18:36,606 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-09 15:18:36,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 99 transitions. [2024-11-09 15:18:36,608 INFO L240 hiAutomatonCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-11-09 15:18:36,608 INFO L425 stractBuchiCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-11-09 15:18:36,608 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 15:18:36,608 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 63 states and 99 transitions. [2024-11-09 15:18:36,609 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:36,609 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:36,609 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:36,609 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:36,610 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:36,610 INFO L745 eck$LassoCheckResult]: Stem: 384#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 376#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; 344#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 353#$Ultimate##0 ~j := #in~j; 355#L18 assume !(~j <= 0); 348#L20 call #t~ret3 := rec1(~j);< 347#$Ultimate##0 ~i := #in~i; 349#L12 assume !(~i <= 0); 360#L14 call #t~ret0 := rec1(~i - 2);< 374#$Ultimate##0 [2024-11-09 15:18:36,610 INFO L747 eck$LassoCheckResult]: Loop: 374#$Ultimate##0 ~i := #in~i; 393#L12 assume !(~i <= 0); 357#L14 call #t~ret0 := rec1(~i - 2);< 374#$Ultimate##0 [2024-11-09 15:18:36,610 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:36,611 INFO L85 PathProgramCache]: Analyzing trace with hash 838970620, now seen corresponding path program 1 times [2024-11-09 15:18:36,611 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:36,611 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [858478198] [2024-11-09 15:18:36,611 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:36,611 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:36,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:36,617 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:36,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:36,625 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:36,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:36,626 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2024-11-09 15:18:36,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:36,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1849815382] [2024-11-09 15:18:36,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:36,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:36,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:36,632 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:36,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:36,634 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:36,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:36,638 INFO L85 PathProgramCache]: Analyzing trace with hash 1359045147, now seen corresponding path program 2 times [2024-11-09 15:18:36,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:36,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [997593473] [2024-11-09 15:18:36,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:36,638 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:36,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:36,646 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:36,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:36,651 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:36,683 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:36,683 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:36,683 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:36,683 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:36,683 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:36,684 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,684 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:36,684 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:36,684 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-11-09 15:18:36,684 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:36,684 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:36,685 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,687 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,689 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,693 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,698 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,727 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:36,730 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:36,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,734 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-09 15:18:36,739 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-09 15:18:36,742 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:36,742 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:36,756 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:36,757 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:36,772 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:36,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,774 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-09 15:18:36,776 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-09 15:18:36,777 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:36,777 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:36,788 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:36,788 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-09 15:18:36,798 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-09 15:18:36,799 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,799 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,800 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-09 15:18:36,801 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-09 15:18:36,802 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:36,802 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:36,813 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:36,813 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-09 15:18:36,828 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:36,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,830 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-09 15:18:36,831 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-09 15:18:36,832 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:36,832 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:36,844 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:36,844 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:36,854 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:36,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,855 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-09 15:18:36,856 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-09 15:18:36,858 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:36,858 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:36,879 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-09 15:18:36,880 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,881 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-09 15:18:36,884 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-09 15:18:36,885 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:36,885 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:36,933 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:36,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-09 15:18:36,937 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:36,937 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:36,937 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:36,937 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:36,938 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:36,938 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,938 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:36,938 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:36,938 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-11-09 15:18:36,938 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:36,938 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:36,939 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,945 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,947 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,948 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,950 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,955 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:36,987 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:36,988 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:36,988 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:36,988 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:36,989 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-09 15:18:36,991 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-09 15:18:36,991 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-09 15:18:37,003 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,004 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,005 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,005 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,005 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,005 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,005 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,007 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:37,017 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-09 15:18:37,018 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,019 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-09 15:18:37,020 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-09 15:18:37,021 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 15:18:37,030 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,031 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,031 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,031 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,031 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,035 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,035 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,036 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:37,047 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-09 15:18:37,047 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,047 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,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-09 15:18:37,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-09 15:18:37,051 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-09 15:18:37,061 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,061 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,061 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,061 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,061 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,063 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,063 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,064 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:37,075 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-09 15:18:37,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,076 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,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-09 15:18:37,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-09 15:18:37,080 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-09 15:18:37,089 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,090 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,090 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,090 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,090 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,090 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,091 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,092 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:37,106 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-11-09 15:18:37,106 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,107 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,108 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-09 15:18:37,109 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-09 15:18:37,109 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-09 15:18:37,119 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,120 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,120 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,120 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,120 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,122 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,122 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,123 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:37,125 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 15:18:37,125 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 15:18:37,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,126 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,127 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-09 15:18:37,128 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-09 15:18:37,128 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:37,128 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:37,128 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:37,129 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-09 15:18:37,139 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:37,140 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:37,149 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,163 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 15:18:37,164 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:37,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,182 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:37,182 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:37,198 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-09 15:18:37,199 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-09 15:18:37,199 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-09 15:18:37,235 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-09 15:18:37,236 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-09 15:18:37,236 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-09 15:18:37,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2024-11-09 15:18:37,236 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 3 letters. [2024-11-09 15:18:37,237 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:37,237 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 12 letters. Loop has 3 letters. [2024-11-09 15:18:37,240 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:37,240 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 6 letters. [2024-11-09 15:18:37,240 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:37,241 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 109 states and 166 transitions. [2024-11-09 15:18:37,243 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:37,249 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 109 states to 97 states and 154 transitions. [2024-11-09 15:18:37,249 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2024-11-09 15:18:37,249 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-09 15:18:37,249 INFO L73 IsDeterministic]: Start isDeterministic. Operand 97 states and 154 transitions. [2024-11-09 15:18:37,250 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:37,250 INFO L218 hiAutomatonCegarLoop]: Abstraction has 97 states and 154 transitions. [2024-11-09 15:18:37,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states and 154 transitions. [2024-11-09 15:18:37,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 93. [2024-11-09 15:18:37,263 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-09 15:18:37,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 144 transitions. [2024-11-09 15:18:37,268 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-11-09 15:18:37,268 INFO L425 stractBuchiCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-11-09 15:18:37,268 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 15:18:37,268 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 93 states and 144 transitions. [2024-11-09 15:18:37,269 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:37,270 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:37,270 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:37,270 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:37,270 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:37,270 INFO L745 eck$LassoCheckResult]: Stem: 636#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 626#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; 587#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 605#$Ultimate##0 ~j := #in~j; 607#L18 assume !(~j <= 0); 631#L20 call #t~ret3 := rec1(~j);< 635#$Ultimate##0 ~i := #in~i; 653#L12 assume !(~i <= 0); 610#L14 call #t~ret0 := rec1(~i - 2);< 651#$Ultimate##0 ~i := #in~i; 656#L12 assume ~i <= 0;#res := 0; 655#rec1FINAL assume true; 650#rec1EXIT >#28#return; 593#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 592#$Ultimate##0 [2024-11-09 15:18:37,270 INFO L747 eck$LassoCheckResult]: Loop: 592#$Ultimate##0 ~i := #in~i; 600#L12 assume !(~i <= 0); 596#L14 call #t~ret0 := rec1(~i - 2);< 592#$Ultimate##0 [2024-11-09 15:18:37,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,270 INFO L85 PathProgramCache]: Analyzing trace with hash 372282091, now seen corresponding path program 1 times [2024-11-09 15:18:37,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:37,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1915999487] [2024-11-09 15:18:37,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:37,271 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:37,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:37,282 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:37,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:37,290 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:37,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,294 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2024-11-09 15:18:37,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:37,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [42613741] [2024-11-09 15:18:37,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:37,295 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:37,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:37,297 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:37,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:37,303 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:37,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,303 INFO L85 PathProgramCache]: Analyzing trace with hash 1050214860, now seen corresponding path program 2 times [2024-11-09 15:18:37,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:37,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2034297232] [2024-11-09 15:18:37,303 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:37,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:37,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,365 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 15:18:37,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,388 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-09 15:18:37,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 15:18:37,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2034297232] [2024-11-09 15:18:37,388 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2034297232] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 15:18:37,388 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 15:18:37,388 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 15:18:37,388 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1434902450] [2024-11-09 15:18:37,388 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 15:18:37,419 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:37,419 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:37,419 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:37,419 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:37,419 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:37,419 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,419 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:37,420 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:37,420 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-11-09 15:18:37,420 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:37,420 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:37,420 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,422 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,427 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,429 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,430 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,432 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,452 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:37,454 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:37,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,455 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,456 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-09 15:18:37,457 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-09 15:18:37,458 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:37,458 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:37,469 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:37,469 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:37,479 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:37,479 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,480 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-09 15:18:37,481 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-09 15:18:37,482 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:37,482 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:37,502 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-09 15:18:37,503 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,503 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,504 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-09 15:18:37,505 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-09 15:18:37,506 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:37,506 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:37,549 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:37,553 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-09 15:18:37,553 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:37,553 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:37,553 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:37,553 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:37,553 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:37,553 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,554 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:37,554 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:37,554 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-11-09 15:18:37,554 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:37,554 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:37,554 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,557 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,562 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,564 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,565 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,566 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:37,590 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:37,591 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:37,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,591 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,592 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-09 15:18:37,593 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-09 15:18:37,594 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-09 15:18:37,603 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,603 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,604 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,604 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,604 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,604 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,604 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,605 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:37,615 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-09 15:18:37,616 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,617 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-09 15:18:37,620 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-09 15:18:37,621 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-09 15:18:37,631 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:37,631 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:37,631 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:37,631 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:37,631 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:37,632 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:37,632 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:37,634 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:37,635 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 15:18:37,635 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 15:18:37,636 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:37,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:37,637 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-09 15:18:37,652 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-09 15:18:37,653 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:37,653 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:37,653 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:37,653 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-09 15:18:37,663 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:37,663 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:37,672 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,689 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 15:18:37,690 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:37,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,745 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:37,745 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:37,765 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-09 15:18:37,765 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-09 15:18:37,766 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-09 15:18:37,840 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-09 15:18:37,840 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-09 15:18:37,841 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-09 15:18:37,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-11-09 15:18:37,841 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 3 letters. [2024-11-09 15:18:37,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:37,842 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 17 letters. Loop has 3 letters. [2024-11-09 15:18:37,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:37,842 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 6 letters. [2024-11-09 15:18:37,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:37,842 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 133 states and 208 transitions. [2024-11-09 15:18:37,844 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:37,846 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 133 states to 121 states and 196 transitions. [2024-11-09 15:18:37,846 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2024-11-09 15:18:37,847 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 52 [2024-11-09 15:18:37,847 INFO L73 IsDeterministic]: Start isDeterministic. Operand 121 states and 196 transitions. [2024-11-09 15:18:37,847 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:37,847 INFO L218 hiAutomatonCegarLoop]: Abstraction has 121 states and 196 transitions. [2024-11-09 15:18:37,847 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states and 196 transitions. [2024-11-09 15:18:37,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2024-11-09 15:18:37,853 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-09 15:18:37,854 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 186 transitions. [2024-11-09 15:18:37,854 INFO L240 hiAutomatonCegarLoop]: Abstraction has 117 states and 186 transitions. [2024-11-09 15:18:37,854 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 15:18:37,855 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 15:18:37,855 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 15:18:37,855 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-09 15:18:37,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 15:18:37,900 INFO L93 Difference]: Finished difference Result 130 states and 196 transitions. [2024-11-09 15:18:37,902 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 196 transitions. [2024-11-09 15:18:37,904 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-09 15:18:37,906 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 128 states and 194 transitions. [2024-11-09 15:18:37,906 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2024-11-09 15:18:37,907 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2024-11-09 15:18:37,907 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 194 transitions. [2024-11-09 15:18:37,907 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:37,907 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 194 transitions. [2024-11-09 15:18:37,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 194 transitions. [2024-11-09 15:18:37,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 105. [2024-11-09 15:18:37,919 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-09 15:18:37,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2024-11-09 15:18:37,920 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-11-09 15:18:37,921 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 15:18:37,921 INFO L425 stractBuchiCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-11-09 15:18:37,921 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 15:18:37,921 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 158 transitions. [2024-11-09 15:18:37,922 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-11-09 15:18:37,922 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:37,922 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:37,923 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:37,923 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:37,923 INFO L745 eck$LassoCheckResult]: Stem: 1218#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1207#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; 1165#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1200#$Ultimate##0 ~j := #in~j; 1231#L18 assume !(~j <= 0); 1201#L20 call #t~ret3 := rec1(~j);< 1230#$Ultimate##0 ~i := #in~i; 1229#L12 assume !(~i <= 0); 1183#L14 call #t~ret0 := rec1(~i - 2);< 1227#$Ultimate##0 ~i := #in~i; 1226#L12 assume !(~i <= 0); 1187#L14 call #t~ret0 := rec1(~i - 2);< 1225#$Ultimate##0 ~i := #in~i; 1228#L12 assume ~i <= 0;#res := 0; 1208#rec1FINAL assume true; 1209#rec1EXIT >#28#return; 1171#L14-1 [2024-11-09 15:18:37,923 INFO L747 eck$LassoCheckResult]: Loop: 1171#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1169#$Ultimate##0 ~i := #in~i; 1172#L12 assume ~i <= 0;#res := 0; 1266#rec1FINAL assume true; 1254#rec1EXIT >#30#return; 1179#L14-2 call #t~ret2 := rec1(#t~ret1);< 1203#$Ultimate##0 ~i := #in~i; 1245#L12 assume !(~i <= 0); 1181#L14 call #t~ret0 := rec1(~i - 2);< 1203#$Ultimate##0 ~i := #in~i; 1245#L12 assume ~i <= 0;#res := 0; 1244#rec1FINAL assume true; 1243#rec1EXIT >#28#return; 1171#L14-1 [2024-11-09 15:18:37,924 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,924 INFO L85 PathProgramCache]: Analyzing trace with hash 1325197585, now seen corresponding path program 1 times [2024-11-09 15:18:37,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:37,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1549299682] [2024-11-09 15:18:37,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:37,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:37,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:37,928 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:37,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:37,932 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:37,932 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:37,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:37,934 INFO L85 PathProgramCache]: Analyzing trace with hash 949089090, now seen corresponding path program 1 times [2024-11-09 15:18:37,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:37,938 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [930351075] [2024-11-09 15:18:37,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:37,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:37,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:37,949 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-09 15:18:37,983 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 15:18:37,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,001 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 15:18:38,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,004 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-09 15:18:38,004 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 15:18:38,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [930351075] [2024-11-09 15:18:38,005 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [930351075] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 15:18:38,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1914911352] [2024-11-09 15:18:38,005 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:38,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 15:18:38,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,009 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-09 15:18:38,013 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-09 15:18:38,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,040 INFO L255 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-09 15:18:38,041 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:38,052 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-09 15:18:38,052 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 15:18:38,052 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1914911352] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 15:18:38,053 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 15:18:38,053 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-09 15:18:38,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [190290209] [2024-11-09 15:18:38,053 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 15:18:38,053 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-09 15:18:38,053 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 15:18:38,054 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 15:18:38,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 15:18:38,054 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-09 15:18:38,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 15:18:38,083 INFO L93 Difference]: Finished difference Result 120 states and 174 transitions. [2024-11-09 15:18:38,083 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 120 states and 174 transitions. [2024-11-09 15:18:38,085 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:38,087 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 120 states to 115 states and 165 transitions. [2024-11-09 15:18:38,087 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2024-11-09 15:18:38,087 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2024-11-09 15:18:38,087 INFO L73 IsDeterministic]: Start isDeterministic. Operand 115 states and 165 transitions. [2024-11-09 15:18:38,087 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:38,087 INFO L218 hiAutomatonCegarLoop]: Abstraction has 115 states and 165 transitions. [2024-11-09 15:18:38,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states and 165 transitions. [2024-11-09 15:18:38,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 112. [2024-11-09 15:18:38,093 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-09 15:18:38,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 162 transitions. [2024-11-09 15:18:38,094 INFO L240 hiAutomatonCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-11-09 15:18:38,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 15:18:38,095 INFO L425 stractBuchiCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-11-09 15:18:38,095 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 15:18:38,095 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 112 states and 162 transitions. [2024-11-09 15:18:38,096 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-11-09 15:18:38,096 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:38,096 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:38,097 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-09 15:18:38,097 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:38,097 INFO L745 eck$LassoCheckResult]: Stem: 1505#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1491#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; 1447#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1475#$Ultimate##0 ~j := #in~j; 1516#L18 assume !(~j <= 0); 1461#L20 call #t~ret3 := rec1(~j);< 1515#$Ultimate##0 ~i := #in~i; 1514#L12 assume !(~i <= 0); 1478#L14 call #t~ret0 := rec1(~i - 2);< 1513#$Ultimate##0 ~i := #in~i; 1511#L12 assume !(~i <= 0); 1484#L14 call #t~ret0 := rec1(~i - 2);< 1510#$Ultimate##0 ~i := #in~i; 1512#L12 assume ~i <= 0;#res := 0; 1492#rec1FINAL assume true; 1493#rec1EXIT >#28#return; 1487#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1488#$Ultimate##0 ~i := #in~i; 1524#L12 assume ~i <= 0;#res := 0; 1523#rec1FINAL assume true; 1521#rec1EXIT >#30#return; 1452#L14-2 call #t~ret2 := rec1(#t~ret1);< 1451#$Ultimate##0 ~i := #in~i; 1453#L12 assume ~i <= 0;#res := 0; 1500#rec1FINAL assume true; 1496#rec1EXIT >#32#return; 1497#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 1526#rec1FINAL assume true; 1525#rec1EXIT >#28#return; 1480#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1502#$Ultimate##0 [2024-11-09 15:18:38,097 INFO L747 eck$LassoCheckResult]: Loop: 1502#$Ultimate##0 ~i := #in~i; 1528#L12 assume !(~i <= 0); 1481#L14 call #t~ret0 := rec1(~i - 2);< 1502#$Ultimate##0 [2024-11-09 15:18:38,098 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:38,098 INFO L85 PathProgramCache]: Analyzing trace with hash 1060897207, now seen corresponding path program 1 times [2024-11-09 15:18:38,098 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:38,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [62759567] [2024-11-09 15:18:38,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:38,098 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:38,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:38,104 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:38,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:38,109 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:38,109 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:38,110 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 3 times [2024-11-09 15:18:38,110 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:38,110 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [223879645] [2024-11-09 15:18:38,110 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:38,110 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:38,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:38,112 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:38,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:38,113 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:38,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:38,114 INFO L85 PathProgramCache]: Analyzing trace with hash -1475637376, now seen corresponding path program 2 times [2024-11-09 15:18:38,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:38,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1585235904] [2024-11-09 15:18:38,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:38,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:38,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,151 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 15:18:38,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,174 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 15:18:38,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,177 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 15:18:38,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,179 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-09 15:18:38,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,190 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-09 15:18:38,190 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 15:18:38,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1585235904] [2024-11-09 15:18:38,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1585235904] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 15:18:38,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [718840243] [2024-11-09 15:18:38,190 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 15:18:38,191 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 15:18:38,191 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,192 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-09 15:18:38,193 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-09 15:18:38,224 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 15:18:38,224 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 15:18:38,225 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:38,226 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:38,245 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-09 15:18:38,245 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 15:18:38,337 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-09 15:18:38,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [718840243] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 15:18:38,337 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 15:18:38,338 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-11-09 15:18:38,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [392646871] [2024-11-09 15:18:38,338 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 15:18:38,389 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:38,389 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:38,389 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:38,389 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:38,389 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:38,389 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,389 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:38,389 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:38,389 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-11-09 15:18:38,389 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:38,389 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:38,391 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,399 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,401 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,406 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,407 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,411 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,457 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:38,457 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:38,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,460 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-09 15:18:38,471 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-09 15:18:38,472 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:38,472 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,484 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:38,484 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:38,494 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-09 15:18:38,494 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,494 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,496 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-09 15:18:38,497 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-09 15:18:38,497 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:38,497 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,508 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:38,508 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-09 15:18:38,526 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-09 15:18:38,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,528 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-09 15:18:38,529 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-09 15:18:38,530 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:38,530 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,541 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:38,541 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-09 15:18:38,552 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-09 15:18:38,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,554 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-09 15:18:38,555 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-09 15:18:38,555 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:38,555 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,567 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:38,567 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:38,577 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-09 15:18:38,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,579 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-09 15:18:38,580 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-09 15:18:38,582 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:38,582 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,593 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:38,593 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-09 15:18:38,604 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-09 15:18:38,604 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,605 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-09 15:18:38,606 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-09 15:18:38,607 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:38,607 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,628 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-09 15:18:38,628 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,628 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,630 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-09 15:18:38,631 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-09 15:18:38,632 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:38,632 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:38,675 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:38,679 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2024-11-09 15:18:38,679 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:38,679 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:38,679 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:38,679 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:38,680 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:38,680 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,680 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:38,680 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:38,680 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-11-09 15:18:38,680 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:38,680 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:38,680 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,684 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,685 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,687 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,688 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:38,713 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:38,714 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:38,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,716 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-09 15:18:38,717 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-09 15:18:38,719 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-09 15:18:38,728 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:38,728 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:38,728 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:38,728 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:38,729 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:38,730 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:38,730 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:38,731 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:38,741 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Ended with exit code 0 [2024-11-09 15:18:38,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,743 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-09 15:18:38,745 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-09 15:18:38,746 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-09 15:18:38,755 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:38,756 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:38,756 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:38,756 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:38,756 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:38,756 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:38,756 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:38,757 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:38,768 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-09 15:18:38,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,770 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-09 15:18:38,771 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-09 15:18:38,771 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-09 15:18:38,781 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:38,781 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:38,781 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:38,781 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:38,782 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:38,782 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:38,782 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:38,783 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:38,793 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:38,794 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,794 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,795 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-09 15:18:38,796 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-09 15:18:38,797 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-09 15:18:38,807 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:38,807 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:38,807 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:38,807 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:38,807 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:38,807 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:38,808 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:38,809 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:38,819 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:38,819 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,820 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,822 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-09 15:18:38,825 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-09 15:18:38,827 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-09 15:18:38,836 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:38,836 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:38,836 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:38,836 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:38,836 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:38,837 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:38,837 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:38,838 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:38,848 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:38,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,849 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,850 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-09 15:18:38,853 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-09 15:18:38,853 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-09 15:18:38,863 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:38,863 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:38,863 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:38,863 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:38,863 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:38,864 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:38,864 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:38,866 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:38,867 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 15:18:38,867 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 15:18:38,867 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:38,867 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:38,869 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-09 15:18:38,870 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-09 15:18:38,870 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:38,870 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:38,870 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:38,870 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-09 15:18:38,884 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-09 15:18:38,884 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:38,895 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:38,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:38,938 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 15:18:38,939 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,140 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:39,141 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,158 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-09 15:18:39,159 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-09 15:18:39,160 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-09 15:18:39,200 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-09 15:18:39,200 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-09 15:18:39,201 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-09 15:18:39,201 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-09 15:18:39,201 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-09 15:18:39,201 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:39,202 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:18:39,209 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:39,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,240 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 15:18:39,241 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,281 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-09 15:18:39,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,428 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:39,429 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,445 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-09 15:18:39,445 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-09 15:18:39,445 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-09 15:18:39,484 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-09 15:18:39,485 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-09 15:18:39,485 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-09 15:18:39,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-09 15:18:39,486 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-09 15:18:39,486 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:39,486 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:18:39,493 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:39,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,525 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 15:18:39,526 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,663 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:39,664 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,679 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-09 15:18:39,680 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-09 15:18:39,680 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-09 15:18:39,744 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-09 15:18:39,745 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-09 15:18:39,745 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-09 15:18:39,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-11-09 15:18:39,746 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-09 15:18:39,746 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:39,746 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-11-09 15:18:39,746 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:39,746 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-11-09 15:18:39,746 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:39,746 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 157 states and 219 transitions. [2024-11-09 15:18:39,748 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-09 15:18:39,750 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 157 states to 139 states and 201 transitions. [2024-11-09 15:18:39,750 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 55 [2024-11-09 15:18:39,750 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 58 [2024-11-09 15:18:39,750 INFO L73 IsDeterministic]: Start isDeterministic. Operand 139 states and 201 transitions. [2024-11-09 15:18:39,750 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:39,750 INFO L218 hiAutomatonCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-11-09 15:18:39,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states and 201 transitions. [2024-11-09 15:18:39,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 120. [2024-11-09 15:18:39,760 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-09 15:18:39,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 170 transitions. [2024-11-09 15:18:39,761 INFO L240 hiAutomatonCegarLoop]: Abstraction has 120 states and 170 transitions. [2024-11-09 15:18:39,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 15:18:39,765 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 15:18:39,765 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-09 15:18:39,765 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-09 15:18:39,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 15:18:39,810 INFO L93 Difference]: Finished difference Result 98 states and 116 transitions. [2024-11-09 15:18:39,810 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 98 states and 116 transitions. [2024-11-09 15:18:39,811 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-09 15:18:39,816 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 98 states to 63 states and 75 transitions. [2024-11-09 15:18:39,816 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2024-11-09 15:18:39,816 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 12 [2024-11-09 15:18:39,816 INFO L73 IsDeterministic]: Start isDeterministic. Operand 63 states and 75 transitions. [2024-11-09 15:18:39,816 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:39,816 INFO L218 hiAutomatonCegarLoop]: Abstraction has 63 states and 75 transitions. [2024-11-09 15:18:39,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states and 75 transitions. [2024-11-09 15:18:39,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-11-09 15:18:39,818 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-09 15:18:39,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2024-11-09 15:18:39,819 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-09 15:18:39,820 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 15:18:39,821 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-09 15:18:39,821 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-09 15:18:39,821 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 65 transitions. [2024-11-09 15:18:39,821 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-09 15:18:39,821 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:39,821 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:39,822 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-09 15:18:39,822 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:39,822 INFO L745 eck$LassoCheckResult]: Stem: 2824#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 2818#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; 2794#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 2803#$Ultimate##0 ~j := #in~j; 2804#L18 assume !(~j <= 0); 2816#L20 call #t~ret3 := rec1(~j);< 2842#$Ultimate##0 ~i := #in~i; 2839#L12 assume !(~i <= 0); 2811#L14 call #t~ret0 := rec1(~i - 2);< 2841#$Ultimate##0 ~i := #in~i; 2846#L12 assume ~i <= 0;#res := 0; 2845#rec1FINAL assume true; 2820#rec1EXIT >#28#return; 2815#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 2817#$Ultimate##0 ~i := #in~i; 2838#L12 assume ~i <= 0;#res := 0; 2837#rec1FINAL assume true; 2831#rec1EXIT >#30#return; 2829#L14-2 call #t~ret2 := rec1(#t~ret1);< 2814#$Ultimate##0 ~i := #in~i; 2833#L12 assume ~i <= 0;#res := 0; 2830#rec1FINAL assume true; 2828#rec1EXIT >#32#return; 2827#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 2826#rec1FINAL assume true; 2825#rec1EXIT >#34#return; 2793#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 2795#$Ultimate##0 ~j := #in~j; 2805#L18 assume !(~j <= 0); 2799#L20 call #t~ret3 := rec1(~j);< 2796#$Ultimate##0 [2024-11-09 15:18:39,822 INFO L747 eck$LassoCheckResult]: Loop: 2796#$Ultimate##0 ~i := #in~i; 2798#L12 assume !(~i <= 0); 2797#L14 call #t~ret0 := rec1(~i - 2);< 2796#$Ultimate##0 [2024-11-09 15:18:39,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:39,822 INFO L85 PathProgramCache]: Analyzing trace with hash 1256061253, now seen corresponding path program 2 times [2024-11-09 15:18:39,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:39,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [402172830] [2024-11-09 15:18:39,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:39,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:39,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,866 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-09 15:18:39,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,902 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 15:18:39,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,905 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 15:18:39,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,908 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-09 15:18:39,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:39,921 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-09 15:18:39,921 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 15:18:39,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [402172830] [2024-11-09 15:18:39,921 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [402172830] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 15:18:39,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1690613967] [2024-11-09 15:18:39,921 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 15:18:39,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 15:18:39,922 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:39,923 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-09 15:18:39,924 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-09 15:18:39,950 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 15:18:39,950 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 15:18:39,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:39,952 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:39,963 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-09 15:18:39,963 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 15:18:40,029 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-09 15:18:40,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1690613967] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 15:18:40,029 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 15:18:40,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-11-09 15:18:40,030 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1136730932] [2024-11-09 15:18:40,030 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 15:18:40,030 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 15:18:40,030 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:40,030 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 4 times [2024-11-09 15:18:40,030 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:40,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [143679546] [2024-11-09 15:18:40,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:40,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:40,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:40,032 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:40,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:40,034 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:40,053 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:40,053 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:40,053 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:40,053 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:40,053 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:40,053 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,053 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:40,053 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:40,053 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-11-09 15:18:40,053 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:40,054 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:40,054 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,056 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,059 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,061 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,062 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,064 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,082 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:40,082 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:40,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:40,087 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-09 15:18:40,088 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-09 15:18:40,089 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:40,089 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:40,100 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:40,100 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-09 15:18:40,110 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2024-11-09 15:18:40,110 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,111 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:40,113 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-09 15:18:40,114 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-09 15:18:40,115 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:40,115 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:40,137 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-09 15:18:40,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:40,138 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-09 15:18:40,143 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-09 15:18:40,143 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:40,143 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:40,186 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:40,190 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-09 15:18:40,190 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:40,190 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:40,190 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:40,190 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:40,190 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:40,190 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,190 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:40,190 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:40,190 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-11-09 15:18:40,190 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:40,190 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:40,191 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,196 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,198 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,199 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,200 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:40,234 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:40,234 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:40,234 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,234 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:40,236 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-09 15:18:40,237 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-09 15:18:40,237 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-09 15:18:40,247 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:40,247 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:40,247 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:40,247 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:40,247 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:40,248 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:40,248 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:40,250 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:40,251 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 15:18:40,251 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 15:18:40,251 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:40,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:40,255 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-09 15:18:40,256 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-09 15:18:40,256 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:40,256 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:40,256 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:40,256 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-11-09 15:18:40,266 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-09 15:18:40,266 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:40,280 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:40,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:40,315 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 15:18:40,327 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:40,341 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Ended with exit code 0 [2024-11-09 15:18:40,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:40,502 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:40,503 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:40,519 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-09 15:18:40,519 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-09 15:18:40,519 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-09 15:18:40,569 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-09 15:18:40,570 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-09 15:18:40,571 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-09 15:18:40,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 15:18:40,571 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-09 15:18:40,571 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:40,571 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:18:40,579 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:40,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:40,611 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 15:18:40,612 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:40,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:40,751 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:40,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:40,768 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-09 15:18:40,768 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-09 15:18:40,768 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-09 15:18:40,812 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-09 15:18:40,813 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-09 15:18:40,814 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-09 15:18:40,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 15:18:40,814 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-09 15:18:40,814 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:40,814 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:18:40,820 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:40,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:40,855 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 15:18:40,856 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:40,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:40,995 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:40,995 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:41,008 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-09 15:18:41,008 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-09 15:18:41,008 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-09 15:18:41,077 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-09 15:18:41,081 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-09 15:18:41,082 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-09 15:18:41,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-11-09 15:18:41,082 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-11-09 15:18:41,082 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:41,082 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-11-09 15:18:41,082 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:41,083 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-11-09 15:18:41,083 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:41,083 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 78 states and 90 transitions. [2024-11-09 15:18:41,083 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:18:41,083 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 78 states to 0 states and 0 transitions. [2024-11-09 15:18:41,083 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 15:18:41,083 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 15:18:41,084 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 15:18:41,084 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 15:18:41,084 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 15:18:41,084 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-09 15:18:41,084 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-09 15:18:41,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 15:18:41,084 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:18:41,084 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 15:18:41,084 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 15:18:41,084 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 15:18:41,084 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:41,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 15:18:41,085 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:41,085 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-09 15:18:41,085 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 15:18:41,085 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:18:41,085 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 15:18:41,090 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 03:18:41 BoogieIcfgContainer [2024-11-09 15:18:41,090 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 15:18:41,091 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 15:18:41,091 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 15:18:41,091 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 15:18:41,091 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:18:34" (3/4) ... [2024-11-09 15:18:41,093 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 15:18:41,093 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 15:18:41,094 INFO L158 Benchmark]: Toolchain (without parser) took 6768.32ms. Allocated memory was 186.6MB in the beginning and 230.7MB in the end (delta: 44.0MB). Free memory was 156.4MB in the beginning and 83.2MB in the end (delta: 73.2MB). Peak memory consumption was 115.5MB. Max. memory is 16.1GB. [2024-11-09 15:18:41,094 INFO L158 Benchmark]: CDTParser took 0.35ms. Allocated memory is still 109.1MB. Free memory is still 79.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:18:41,094 INFO L158 Benchmark]: CACSL2BoogieTranslator took 179.47ms. Allocated memory is still 186.6MB. Free memory was 156.4MB in the beginning and 145.2MB in the end (delta: 11.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 15:18:41,094 INFO L158 Benchmark]: Boogie Procedure Inliner took 22.08ms. Allocated memory is still 186.6MB. Free memory was 145.2MB in the beginning and 144.1MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:18:41,094 INFO L158 Benchmark]: Boogie Preprocessor took 17.97ms. Allocated memory is still 186.6MB. Free memory was 144.1MB in the beginning and 142.0MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 15:18:41,094 INFO L158 Benchmark]: RCFGBuilder took 311.17ms. Allocated memory is still 186.6MB. Free memory was 142.0MB in the beginning and 156.0MB in the end (delta: -14.0MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-09 15:18:41,095 INFO L158 Benchmark]: BuchiAutomizer took 6231.16ms. Allocated memory was 186.6MB in the beginning and 230.7MB in the end (delta: 44.0MB). Free memory was 156.0MB in the beginning and 83.2MB in the end (delta: 72.8MB). Peak memory consumption was 117.9MB. Max. memory is 16.1GB. [2024-11-09 15:18:41,095 INFO L158 Benchmark]: Witness Printer took 2.67ms. Allocated memory is still 230.7MB. Free memory is still 83.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:18:41,096 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.35ms. Allocated memory is still 109.1MB. Free memory is still 79.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 179.47ms. Allocated memory is still 186.6MB. Free memory was 156.4MB in the beginning and 145.2MB in the end (delta: 11.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 22.08ms. Allocated memory is still 186.6MB. Free memory was 145.2MB in the beginning and 144.1MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 17.97ms. Allocated memory is still 186.6MB. Free memory was 144.1MB in the beginning and 142.0MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 311.17ms. Allocated memory is still 186.6MB. Free memory was 142.0MB in the beginning and 156.0MB in the end (delta: -14.0MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * BuchiAutomizer took 6231.16ms. Allocated memory was 186.6MB in the beginning and 230.7MB in the end (delta: 44.0MB). Free memory was 156.0MB in the beginning and 83.2MB in the end (delta: 72.8MB). Peak memory consumption was 117.9MB. Max. memory is 16.1GB. * Witness Printer took 2.67ms. Allocated memory is still 230.7MB. Free memory is still 83.2MB. There was no memory consumed. 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 6.1s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 3.2s. Construction of modules took 0.3s. Büchi inclusion checks took 2.4s. 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, 200 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 177 mSDsluCounter, 532 SdHoareTripleChecker+Invalid, 0.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 333 mSDsCounter, 131 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 323 IncrementalHoareTripleChecker+Invalid, 454 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 131 mSolverCounterUnsat, 199 mSDtfsCounter, 323 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: 20ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 14 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.5s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-09 15:18:41,112 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-09 15:18:41,316 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-09 15:18:41,520 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-09 15:18:41,721 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE