./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 4a390ef5 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/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-dev-4a390ef-m [2024-10-24 23:47:38,360 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-24 23:47:38,440 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-10-24 23:47:38,447 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-24 23:47:38,447 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-24 23:47:38,478 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-24 23:47:38,478 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-24 23:47:38,479 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-24 23:47:38,479 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-24 23:47:38,480 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-24 23:47:38,480 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-24 23:47:38,481 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-24 23:47:38,481 INFO L153 SettingsManager]: * Use SBE=true [2024-10-24 23:47:38,481 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-24 23:47:38,482 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-24 23:47:38,482 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-24 23:47:38,482 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-24 23:47:38,483 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-24 23:47:38,483 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-24 23:47:38,483 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-24 23:47:38,484 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-24 23:47:38,484 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-24 23:47:38,485 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-24 23:47:38,485 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-24 23:47:38,485 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-24 23:47:38,486 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-24 23:47:38,486 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-24 23:47:38,486 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-24 23:47:38,487 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-24 23:47:38,487 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-24 23:47:38,487 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-24 23:47:38,487 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-24 23:47:38,488 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-24 23:47:38,488 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-24 23:47:38,488 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-24 23:47:38,489 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-24 23:47:38,489 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-10-24 23:47:38,739 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-24 23:47:38,763 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-24 23:47:38,767 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-24 23:47:38,769 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-24 23:47:38,769 INFO L274 PluginConnector]: CDTParser initialized [2024-10-24 23:47:38,771 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-10-24 23:47:40,324 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-24 23:47:40,529 INFO L384 CDTParser]: Found 1 translation units. [2024-10-24 23:47:40,529 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-10-24 23:47:40,536 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/846820b65/be74923c64b84cae92feb39205c9ee58/FLAGc30e87e1b [2024-10-24 23:47:40,548 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/846820b65/be74923c64b84cae92feb39205c9ee58 [2024-10-24 23:47:40,550 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-24 23:47:40,551 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-24 23:47:40,552 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-24 23:47:40,553 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-24 23:47:40,564 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-24 23:47:40,567 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,568 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7890abfb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40, skipping insertion in model container [2024-10-24 23:47:40,568 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,585 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-24 23:47:40,750 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 23:47:40,757 INFO L200 MainTranslator]: Completed pre-run [2024-10-24 23:47:40,769 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 23:47:40,787 INFO L204 MainTranslator]: Completed translation [2024-10-24 23:47:40,787 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40 WrapperNode [2024-10-24 23:47:40,788 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-24 23:47:40,789 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-24 23:47:40,789 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-24 23:47:40,789 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-24 23:47:40,796 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,800 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,814 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-10-24 23:47:40,815 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-24 23:47:40,816 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-24 23:47:40,816 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-24 23:47:40,816 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-24 23:47:40,825 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,826 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,827 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,833 INFO L175 MemorySlicer]: No memory access in input program. [2024-10-24 23:47:40,834 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,834 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,837 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,839 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,840 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,841 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,841 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-24 23:47:40,846 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-24 23:47:40,846 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-24 23:47:40,846 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-24 23:47:40,847 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (1/1) ... [2024-10-24 23:47:40,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:40,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:40,881 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-10-24 23:47:40,883 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-10-24 23:47:40,934 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2024-10-24 23:47:40,934 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2024-10-24 23:47:40,934 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2024-10-24 23:47:40,935 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2024-10-24 23:47:40,936 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-24 23:47:40,936 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-24 23:47:40,994 INFO L238 CfgBuilder]: Building ICFG [2024-10-24 23:47:40,997 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-24 23:47:41,096 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-10-24 23:47:41,097 INFO L287 CfgBuilder]: Performing block encoding [2024-10-24 23:47:41,109 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-24 23:47:41,109 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-24 23:47:41,109 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 11:47:41 BoogieIcfgContainer [2024-10-24 23:47:41,110 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-24 23:47:41,111 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-24 23:47:41,111 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-24 23:47:41,115 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-24 23:47:41,116 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-24 23:47:41,116 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 24.10 11:47:40" (1/3) ... [2024-10-24 23:47:41,117 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@2d8f8e03 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 24.10 11:47:41, skipping insertion in model container [2024-10-24 23:47:41,117 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-24 23:47:41,118 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 11:47:40" (2/3) ... [2024-10-24 23:47:41,118 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@2d8f8e03 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 24.10 11:47:41, skipping insertion in model container [2024-10-24 23:47:41,118 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-24 23:47:41,118 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 11:47:41" (3/3) ... [2024-10-24 23:47:41,120 INFO L332 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2024-10-24 23:47:41,205 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-24 23:47:41,206 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-24 23:47:41,206 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-24 23:47:41,206 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-24 23:47:41,206 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-24 23:47:41,206 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-24 23:47:41,206 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-24 23:47:41,207 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-24 23:47:41,215 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-10-24 23:47:41,264 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:41,264 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:41,264 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:41,271 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-24 23:47:41,271 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:41,272 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-24 23:47:41,272 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-10-24 23:47:41,274 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:41,276 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:41,276 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:41,276 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-24 23:47:41,276 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:41,286 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-10-24 23:47:41,286 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-10-24 23:47:41,292 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:41,293 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 1 times [2024-10-24 23:47:41,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:41,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [445894730] [2024-10-24 23:47:41,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:41,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:41,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,384 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:41,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,406 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:41,409 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:41,410 INFO L85 PathProgramCache]: Analyzing trace with hash -1074209557, now seen corresponding path program 1 times [2024-10-24 23:47:41,410 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:41,410 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [822999468] [2024-10-24 23:47:41,410 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:41,411 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:41,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:41,530 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 23:47:41,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:41,629 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:41,630 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 23:47:41,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [822999468] [2024-10-24 23:47:41,631 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [822999468] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 23:47:41,631 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 23:47:41,631 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 23:47:41,631 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1645859869] [2024-10-24 23:47:41,632 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 23:47:41,636 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-24 23:47:41,638 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 23:47:41,667 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 23:47:41,668 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 23:47:41,670 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-10-24 23:47:41,762 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 23:47:41,763 INFO L93 Difference]: Finished difference Result 26 states and 34 transitions. [2024-10-24 23:47:41,764 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 34 transitions. [2024-10-24 23:47:41,767 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:41,772 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 17 states and 23 transitions. [2024-10-24 23:47:41,773 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2024-10-24 23:47:41,774 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2024-10-24 23:47:41,774 INFO L73 IsDeterministic]: Start isDeterministic. Operand 17 states and 23 transitions. [2024-10-24 23:47:41,775 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-24 23:47:41,776 INFO L218 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-10-24 23:47:41,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states and 23 transitions. [2024-10-24 23:47:41,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-10-24 23:47:41,800 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-10-24 23:47:41,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2024-10-24 23:47:41,802 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-10-24 23:47:41,804 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 23:47:41,809 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-10-24 23:47:41,809 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-24 23:47:41,809 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 23 transitions. [2024-10-24 23:47:41,810 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:41,810 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:41,810 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:41,811 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-24 23:47:41,811 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:41,812 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-10-24 23:47:41,812 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-10-24 23:47:41,812 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:41,813 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 2 times [2024-10-24 23:47:41,813 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:41,813 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1656126573] [2024-10-24 23:47:41,813 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:41,814 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:41,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,819 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:41,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,822 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:41,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:41,823 INFO L85 PathProgramCache]: Analyzing trace with hash -204878921, now seen corresponding path program 1 times [2024-10-24 23:47:41,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:41,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1099303449] [2024-10-24 23:47:41,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:41,824 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:41,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,850 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:41,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,865 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:41,865 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:41,866 INFO L85 PathProgramCache]: Analyzing trace with hash -482494696, now seen corresponding path program 1 times [2024-10-24 23:47:41,866 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:41,866 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1818990193] [2024-10-24 23:47:41,866 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:41,867 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:41,880 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,881 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:41,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:41,894 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:42,310 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:42,311 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:42,311 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:42,311 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:42,311 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-24 23:47:42,311 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,312 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:42,312 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:42,312 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-10-24 23:47:42,312 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:42,312 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:42,327 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,337 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,340 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,342 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,361 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,401 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:42,402 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-24 23:47:42,404 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,408 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-10-24 23:47:42,409 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-10-24 23:47:42,411 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:42,412 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:42,428 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:42,428 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:42,439 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-10-24 23:47:42,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,441 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-10-24 23:47:42,442 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-10-24 23:47:42,443 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:42,444 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:42,457 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:42,458 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:42,473 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-10-24 23:47:42,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,475 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-10-24 23:47:42,477 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-10-24 23:47:42,477 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:42,477 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:42,493 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:42,493 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-10-24 23:47:42,507 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:42,508 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,508 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,509 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-10-24 23:47:42,510 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-10-24 23:47:42,511 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:42,511 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:42,538 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-10-24 23:47:42,538 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,539 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,540 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-10-24 23:47:42,542 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-10-24 23:47:42,543 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-24 23:47:42,543 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:42,560 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-24 23:47:42,571 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-10-24 23:47:42,572 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:42,572 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:42,572 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:42,572 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:42,572 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-24 23:47:42,572 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,572 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:42,572 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:42,572 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-10-24 23:47:42,573 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:42,573 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:42,573 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,576 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,578 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,583 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,592 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:42,631 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:42,635 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-24 23:47:42,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,639 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-10-24 23:47:42,642 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-10-24 23:47:42,643 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:42,656 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:42,657 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:42,657 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:42,657 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:42,658 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:42,659 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:42,660 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:42,665 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:42,681 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:42,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,682 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,685 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-10-24 23:47:42,686 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-10-24 23:47:42,688 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:42,699 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:42,699 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:42,699 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:42,699 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:42,700 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:42,700 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:42,700 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:42,702 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:42,712 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:42,712 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,714 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-10-24 23:47:42,715 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-10-24 23:47:42,716 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:42,727 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:42,727 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:42,727 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:42,727 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:42,728 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:42,728 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:42,728 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:42,732 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:42,745 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-10-24 23:47:42,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,746 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,747 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-10-24 23:47:42,748 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-10-24 23:47:42,749 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:42,758 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:42,759 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:42,759 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:42,759 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:42,759 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:42,760 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:42,760 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:42,763 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-24 23:47:42,766 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-24 23:47:42,766 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-24 23:47:42,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:42,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:42,778 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-10-24 23:47:42,779 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-10-24 23:47:42,780 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-24 23:47:42,780 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-24 23:47:42,780 INFO L474 LassoAnalysis]: Proved termination. [2024-10-24 23:47:42,781 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2024-10-24 23:47:42,791 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-10-24 23:47:42,794 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-24 23:47:42,814 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:42,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:42,837 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-24 23:47:42,838 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:42,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:42,896 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-24 23:47:42,899 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:42,999 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-10-24 23:47:43,112 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-10-24 23:47:43,116 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-10-24 23:47:43,118 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-10-24 23:47:43,460 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-10-24 23:47:43,463 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-10-24 23:47:43,464 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-10-24 23:47:43,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 37 transitions. [2024-10-24 23:47:43,468 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 24 letters. [2024-10-24 23:47:43,469 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:43,469 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 27 letters. Loop has 24 letters. [2024-10-24 23:47:43,470 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:43,470 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 48 letters. [2024-10-24 23:47:43,470 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:43,470 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 102 states and 148 transitions. [2024-10-24 23:47:43,475 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:43,479 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 102 states to 90 states and 136 transitions. [2024-10-24 23:47:43,480 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 39 [2024-10-24 23:47:43,480 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-10-24 23:47:43,480 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 136 transitions. [2024-10-24 23:47:43,482 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:43,482 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 136 transitions. [2024-10-24 23:47:43,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 136 transitions. [2024-10-24 23:47:43,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 63. [2024-10-24 23:47:43,497 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-10-24 23:47:43,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 99 transitions. [2024-10-24 23:47:43,499 INFO L240 hiAutomatonCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-10-24 23:47:43,499 INFO L425 stractBuchiCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-10-24 23:47:43,499 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-24 23:47:43,501 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 63 states and 99 transitions. [2024-10-24 23:47:43,505 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:43,505 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:43,507 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:43,507 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:43,507 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-24 23:47:43,507 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-10-24 23:47:43,507 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-10-24 23:47:43,508 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:43,508 INFO L85 PathProgramCache]: Analyzing trace with hash 838970620, now seen corresponding path program 1 times [2024-10-24 23:47:43,508 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:43,508 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2093178890] [2024-10-24 23:47:43,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:43,508 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:43,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:43,520 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:43,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:43,525 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:43,525 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:43,526 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2024-10-24 23:47:43,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:43,526 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1388658123] [2024-10-24 23:47:43,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:43,526 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:43,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:43,529 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:43,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:43,532 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:43,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:43,533 INFO L85 PathProgramCache]: Analyzing trace with hash 1359045147, now seen corresponding path program 2 times [2024-10-24 23:47:43,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:43,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1984133883] [2024-10-24 23:47:43,534 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:43,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:43,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:43,539 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:43,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:43,543 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:43,585 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:43,586 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:43,586 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:43,586 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:43,586 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-24 23:47:43,586 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,586 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:43,586 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:43,586 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-10-24 23:47:43,586 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:43,587 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:43,587 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,590 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,592 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,594 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,596 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,601 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,634 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:43,635 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-24 23:47:43,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,637 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-10-24 23:47:43,638 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-10-24 23:47:43,639 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:43,639 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:43,654 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:43,654 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:43,666 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-10-24 23:47:43,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,668 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-10-24 23:47:43,669 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-10-24 23:47:43,671 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:43,671 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:43,681 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:43,682 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-10-24 23:47:43,692 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-10-24 23:47:43,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,693 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-10-24 23:47:43,694 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-10-24 23:47:43,695 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:43,695 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:43,706 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:43,706 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-10-24 23:47:43,716 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-10-24 23:47:43,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,717 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-10-24 23:47:43,719 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-10-24 23:47:43,719 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:43,719 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:43,730 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:43,730 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:43,740 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-10-24 23:47:43,741 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,741 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,743 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-10-24 23:47:43,744 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-10-24 23:47:43,745 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:43,745 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:43,766 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:43,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,767 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-10-24 23:47:43,768 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-10-24 23:47:43,770 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-24 23:47:43,770 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:43,812 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-24 23:47:43,816 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:43,817 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:43,817 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:43,817 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:43,817 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:43,817 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-24 23:47:43,817 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,817 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:43,817 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:43,817 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-10-24 23:47:43,817 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:43,817 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:43,818 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,821 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,822 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,824 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,826 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,832 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:43,861 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:43,861 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-24 23:47:43,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,864 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-10-24 23:47:43,865 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-10-24 23:47:43,866 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:43,877 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:43,877 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:43,877 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:43,877 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:43,877 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:43,878 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:43,878 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:43,879 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:43,889 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:43,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,890 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-10-24 23:47:43,892 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-10-24 23:47:43,892 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:43,902 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:43,902 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:43,902 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:43,902 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:43,902 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:43,903 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:43,903 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:43,904 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:43,914 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-10-24 23:47:43,915 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,915 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,916 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-10-24 23:47:43,917 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-10-24 23:47:43,918 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:43,927 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:43,928 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:43,928 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:43,928 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:43,928 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:43,928 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:43,928 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:43,930 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:43,940 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-10-24 23:47:43,940 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,940 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,941 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-10-24 23:47:43,942 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-10-24 23:47:43,943 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:43,952 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:43,953 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:43,953 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:43,953 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:43,953 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:43,953 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:43,953 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:43,955 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:43,966 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-10-24 23:47:43,967 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,967 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,968 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-10-24 23:47:43,968 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-10-24 23:47:43,969 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:43,979 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:43,979 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:43,979 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:43,979 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:43,979 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:43,980 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:43,980 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:43,984 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-24 23:47:43,986 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-24 23:47:43,986 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-24 23:47:43,986 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:43,986 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:43,987 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-10-24 23:47:43,988 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-10-24 23:47:43,989 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-24 23:47:43,989 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-24 23:47:43,989 INFO L474 LassoAnalysis]: Proved termination. [2024-10-24 23:47:43,989 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-24 23:47:43,999 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-10-24 23:47:44,000 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-24 23:47:44,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,037 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-24 23:47:44,038 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:44,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,078 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:44,079 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:44,103 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:44,104 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-10-24 23:47:44,104 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-10-24 23:47:44,148 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-10-24 23:47:44,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-24 23:47:44,150 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-10-24 23:47:44,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2024-10-24 23:47:44,150 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 3 letters. [2024-10-24 23:47:44,150 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:44,150 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 12 letters. Loop has 3 letters. [2024-10-24 23:47:44,151 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:44,151 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 6 letters. [2024-10-24 23:47:44,151 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:44,151 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 109 states and 166 transitions. [2024-10-24 23:47:44,154 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:44,158 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 109 states to 97 states and 154 transitions. [2024-10-24 23:47:44,158 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2024-10-24 23:47:44,159 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-10-24 23:47:44,159 INFO L73 IsDeterministic]: Start isDeterministic. Operand 97 states and 154 transitions. [2024-10-24 23:47:44,159 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:44,159 INFO L218 hiAutomatonCegarLoop]: Abstraction has 97 states and 154 transitions. [2024-10-24 23:47:44,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states and 154 transitions. [2024-10-24 23:47:44,171 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 93. [2024-10-24 23:47:44,172 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-10-24 23:47:44,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 144 transitions. [2024-10-24 23:47:44,175 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-10-24 23:47:44,175 INFO L425 stractBuchiCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-10-24 23:47:44,176 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-24 23:47:44,176 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 93 states and 144 transitions. [2024-10-24 23:47:44,177 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:44,178 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:44,178 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:44,178 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:44,178 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-24 23:47:44,179 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-10-24 23:47:44,179 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-10-24 23:47:44,179 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,179 INFO L85 PathProgramCache]: Analyzing trace with hash 372282091, now seen corresponding path program 1 times [2024-10-24 23:47:44,180 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:44,180 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [841917747] [2024-10-24 23:47:44,180 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:44,180 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:44,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:44,185 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:44,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:44,191 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:44,191 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,191 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2024-10-24 23:47:44,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:44,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1545262496] [2024-10-24 23:47:44,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:44,192 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:44,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:44,200 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:44,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:44,206 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:44,206 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,207 INFO L85 PathProgramCache]: Analyzing trace with hash 1050214860, now seen corresponding path program 2 times [2024-10-24 23:47:44,207 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:44,207 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [867771979] [2024-10-24 23:47:44,207 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:44,207 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:44,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,287 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 23:47:44,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,303 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-24 23:47:44,304 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 23:47:44,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [867771979] [2024-10-24 23:47:44,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [867771979] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 23:47:44,304 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 23:47:44,304 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-24 23:47:44,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1088643710] [2024-10-24 23:47:44,305 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 23:47:44,340 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:44,341 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:44,341 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:44,341 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:44,341 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-24 23:47:44,341 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,341 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:44,341 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:44,341 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-10-24 23:47:44,341 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:44,341 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:44,342 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,346 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,352 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,354 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,357 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,358 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,410 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-10-24 23:47:44,412 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:44,412 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-24 23:47:44,412 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,412 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,414 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-10-24 23:47:44,415 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-10-24 23:47:44,415 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:44,415 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:44,426 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:44,426 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:44,436 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-10-24 23:47:44,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,438 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-10-24 23:47:44,440 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-10-24 23:47:44,441 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:44,441 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:44,472 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2024-10-24 23:47:44,473 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,473 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,474 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-10-24 23:47:44,476 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-10-24 23:47:44,477 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-24 23:47:44,477 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:44,525 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-24 23:47:44,529 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-10-24 23:47:44,529 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:44,529 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:44,529 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:44,529 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:44,529 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-24 23:47:44,529 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,529 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:44,529 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:44,529 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-10-24 23:47:44,529 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:44,529 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:44,530 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,532 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,536 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,541 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,544 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,545 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:44,570 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:44,570 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-24 23:47:44,570 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,570 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,572 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-10-24 23:47:44,573 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-10-24 23:47:44,573 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:44,583 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:44,583 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:44,583 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:44,583 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:44,583 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:44,584 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:44,584 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:44,585 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:44,595 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:44,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,595 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,596 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-10-24 23:47:44,597 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-10-24 23:47:44,598 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:44,607 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:44,607 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:44,608 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:44,608 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:44,608 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:44,608 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:44,608 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:44,610 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-24 23:47:44,612 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-24 23:47:44,612 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-24 23:47:44,612 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:44,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,615 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-10-24 23:47:44,616 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-10-24 23:47:44,616 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-24 23:47:44,616 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-24 23:47:44,616 INFO L474 LassoAnalysis]: Proved termination. [2024-10-24 23:47:44,616 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-24 23:47:44,627 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-10-24 23:47:44,627 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-24 23:47:44,636 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,663 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-24 23:47:44,665 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:44,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,742 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:44,742 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:44,763 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:44,764 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:44,764 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-10-24 23:47:44,831 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-10-24 23:47:44,832 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-24 23:47:44,832 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-10-24 23:47:44,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-10-24 23:47:44,833 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 3 letters. [2024-10-24 23:47:44,833 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:44,833 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 17 letters. Loop has 3 letters. [2024-10-24 23:47:44,833 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:44,833 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 6 letters. [2024-10-24 23:47:44,834 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:44,834 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 133 states and 208 transitions. [2024-10-24 23:47:44,837 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:44,840 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 133 states to 121 states and 196 transitions. [2024-10-24 23:47:44,840 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2024-10-24 23:47:44,841 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 52 [2024-10-24 23:47:44,841 INFO L73 IsDeterministic]: Start isDeterministic. Operand 121 states and 196 transitions. [2024-10-24 23:47:44,841 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:44,841 INFO L218 hiAutomatonCegarLoop]: Abstraction has 121 states and 196 transitions. [2024-10-24 23:47:44,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states and 196 transitions. [2024-10-24 23:47:44,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2024-10-24 23:47:44,854 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-10-24 23:47:44,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 186 transitions. [2024-10-24 23:47:44,857 INFO L240 hiAutomatonCegarLoop]: Abstraction has 117 states and 186 transitions. [2024-10-24 23:47:44,857 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 23:47:44,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 23:47:44,857 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-24 23:47:44,857 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-10-24 23:47:44,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 23:47:44,898 INFO L93 Difference]: Finished difference Result 130 states and 196 transitions. [2024-10-24 23:47:44,898 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 196 transitions. [2024-10-24 23:47:44,900 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-10-24 23:47:44,903 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 128 states and 194 transitions. [2024-10-24 23:47:44,903 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2024-10-24 23:47:44,904 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2024-10-24 23:47:44,904 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 194 transitions. [2024-10-24 23:47:44,904 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:44,904 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 194 transitions. [2024-10-24 23:47:44,904 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 194 transitions. [2024-10-24 23:47:44,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 105. [2024-10-24 23:47:44,912 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-10-24 23:47:44,914 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2024-10-24 23:47:44,914 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-10-24 23:47:44,914 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 23:47:44,915 INFO L425 stractBuchiCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-10-24 23:47:44,915 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-24 23:47:44,915 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 158 transitions. [2024-10-24 23:47:44,916 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-24 23:47:44,916 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:44,916 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:44,917 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:44,917 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:44,917 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-10-24 23:47:44,917 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-10-24 23:47:44,917 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,918 INFO L85 PathProgramCache]: Analyzing trace with hash 1325197585, now seen corresponding path program 1 times [2024-10-24 23:47:44,918 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:44,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1193456111] [2024-10-24 23:47:44,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:44,918 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:44,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:44,923 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:44,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:44,928 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:44,928 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:44,928 INFO L85 PathProgramCache]: Analyzing trace with hash 949089090, now seen corresponding path program 1 times [2024-10-24 23:47:44,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:44,928 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [405542436] [2024-10-24 23:47:44,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:44,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:44,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,960 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-10-24 23:47:44,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,980 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 23:47:44,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:44,984 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-24 23:47:44,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 23:47:44,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [405542436] [2024-10-24 23:47:44,985 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [405542436] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 23:47:44,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1494490994] [2024-10-24 23:47:44,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:44,985 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 23:47:44,985 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:44,987 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-10-24 23:47:44,989 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-10-24 23:47:45,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:45,019 INFO L255 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-24 23:47:45,019 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:45,030 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:45,030 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 23:47:45,030 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1494490994] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 23:47:45,030 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 23:47:45,030 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-10-24 23:47:45,031 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2045808317] [2024-10-24 23:47:45,031 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 23:47:45,031 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-24 23:47:45,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 23:47:45,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 23:47:45,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-24 23:47:45,032 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-10-24 23:47:45,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 23:47:45,063 INFO L93 Difference]: Finished difference Result 120 states and 174 transitions. [2024-10-24 23:47:45,063 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 120 states and 174 transitions. [2024-10-24 23:47:45,065 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:45,068 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 120 states to 115 states and 165 transitions. [2024-10-24 23:47:45,068 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2024-10-24 23:47:45,068 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2024-10-24 23:47:45,068 INFO L73 IsDeterministic]: Start isDeterministic. Operand 115 states and 165 transitions. [2024-10-24 23:47:45,068 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:45,068 INFO L218 hiAutomatonCegarLoop]: Abstraction has 115 states and 165 transitions. [2024-10-24 23:47:45,068 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states and 165 transitions. [2024-10-24 23:47:45,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 112. [2024-10-24 23:47:45,076 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-10-24 23:47:45,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 162 transitions. [2024-10-24 23:47:45,078 INFO L240 hiAutomatonCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-10-24 23:47:45,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 23:47:45,081 INFO L425 stractBuchiCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-10-24 23:47:45,082 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-24 23:47:45,082 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 112 states and 162 transitions. [2024-10-24 23:47:45,083 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-24 23:47:45,084 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:45,084 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:45,085 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 23:47:45,087 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-24 23:47:45,087 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-10-24 23:47:45,087 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-10-24 23:47:45,088 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:45,088 INFO L85 PathProgramCache]: Analyzing trace with hash 1060897207, now seen corresponding path program 1 times [2024-10-24 23:47:45,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:45,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [722166890] [2024-10-24 23:47:45,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:45,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:45,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:45,105 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:45,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:45,117 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:45,118 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:45,118 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 3 times [2024-10-24 23:47:45,118 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:45,118 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1913696943] [2024-10-24 23:47:45,118 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:45,122 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:45,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:45,129 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:45,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:45,132 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:45,132 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:45,132 INFO L85 PathProgramCache]: Analyzing trace with hash -1475637376, now seen corresponding path program 2 times [2024-10-24 23:47:45,132 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:45,133 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [244375464] [2024-10-24 23:47:45,133 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:45,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:45,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:45,211 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 23:47:45,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:45,245 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 23:47:45,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:45,249 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 23:47:45,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:45,253 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 23:47:45,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:45,272 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-10-24 23:47:45,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 23:47:45,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [244375464] [2024-10-24 23:47:45,273 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [244375464] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 23:47:45,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1876038968] [2024-10-24 23:47:45,273 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 23:47:45,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 23:47:45,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,276 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-10-24 23:47:45,277 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-10-24 23:47:45,316 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 23:47:45,316 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 23:47:45,318 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:45,320 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:45,340 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-10-24 23:47:45,340 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 23:47:45,452 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-10-24 23:47:45,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1876038968] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 23:47:45,452 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 23:47:45,452 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-10-24 23:47:45,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631031298] [2024-10-24 23:47:45,453 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 23:47:45,495 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-10-24 23:47:45,498 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:45,499 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:45,499 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:45,499 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:45,499 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-24 23:47:45,499 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,499 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:45,499 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:45,499 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-10-24 23:47:45,499 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:45,499 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:45,500 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,502 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,507 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,508 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,510 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,511 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,546 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:45,546 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-24 23:47:45,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,547 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,549 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-10-24 23:47:45,550 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-10-24 23:47:45,551 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:45,551 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,566 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:45,566 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:45,581 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-10-24 23:47:45,583 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,583 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,588 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-10-24 23:47:45,589 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-10-24 23:47:45,591 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:45,591 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,605 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:45,605 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-10-24 23:47:45,619 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-10-24 23:47:45,620 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,622 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-10-24 23:47:45,624 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-10-24 23:47:45,625 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:45,626 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,642 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:45,642 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-10-24 23:47:45,655 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-10-24 23:47:45,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,660 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-10-24 23:47:45,661 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-10-24 23:47:45,662 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:45,663 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,678 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:45,679 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-24 23:47:45,692 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-10-24 23:47:45,693 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,693 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,695 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-10-24 23:47:45,696 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-10-24 23:47:45,697 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:45,697 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,714 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:45,714 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-10-24 23:47:45,726 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-10-24 23:47:45,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,727 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-10-24 23:47:45,728 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-10-24 23:47:45,729 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:45,729 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,753 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-10-24 23:47:45,753 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,753 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,754 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-10-24 23:47:45,756 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-10-24 23:47:45,757 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-24 23:47:45,757 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:45,801 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-24 23:47:45,805 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:45,806 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:45,806 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:45,806 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:45,806 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:45,806 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-24 23:47:45,806 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,806 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:45,806 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:45,806 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-10-24 23:47:45,806 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:45,806 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:45,807 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,813 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,816 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,819 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,821 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,823 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:45,854 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:45,855 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-24 23:47:45,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,857 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-10-24 23:47:45,858 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-10-24 23:47:45,859 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:45,871 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:45,871 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:45,872 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:45,872 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:45,872 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:45,873 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:45,873 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:45,875 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:45,889 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-10-24 23:47:45,891 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,891 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,892 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-10-24 23:47:45,895 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-10-24 23:47:45,895 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:45,908 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:45,908 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:45,909 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:45,909 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:45,909 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:45,911 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:45,911 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:45,914 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:45,925 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-10-24 23:47:45,925 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,927 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-10-24 23:47:45,929 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-10-24 23:47:45,929 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:45,940 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:45,941 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:45,941 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:45,941 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:45,941 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:45,942 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:45,942 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:45,945 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:45,955 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-10-24 23:47:45,956 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,956 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,957 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-10-24 23:47:45,958 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-10-24 23:47:45,959 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:45,968 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:45,969 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:45,969 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:45,969 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:45,969 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:45,969 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:45,969 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:45,971 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:45,981 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-10-24 23:47:45,982 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:45,982 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:45,984 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-10-24 23:47:45,985 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:45,985 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-10-24 23:47:45,996 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:45,996 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:45,996 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:45,997 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:45,997 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:45,997 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:45,997 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:45,998 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-24 23:47:46,009 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2024-10-24 23:47:46,009 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:46,009 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:46,010 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-10-24 23:47:46,012 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-10-24 23:47:46,012 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:46,024 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:46,024 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:46,024 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:46,024 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:46,024 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:46,025 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:46,025 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:46,027 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-24 23:47:46,029 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-24 23:47:46,029 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-24 23:47:46,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:46,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:46,031 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-10-24 23:47:46,031 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-10-24 23:47:46,032 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-24 23:47:46,032 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-24 23:47:46,032 INFO L474 LassoAnalysis]: Proved termination. [2024-10-24 23:47:46,032 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-24 23:47:46,042 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-10-24 23:47:46,043 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-24 23:47:46,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:46,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:46,108 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 23:47:46,111 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:46,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:46,375 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:46,376 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:46,399 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:46,399 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:46,400 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-10-24 23:47:46,457 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-10-24 23:47:46,461 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-10-24 23:47:46,461 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-10-24 23:47:46,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-10-24 23:47:46,462 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-24 23:47:46,462 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:46,462 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-24 23:47:46,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:46,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:46,521 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 23:47:46,523 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:46,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:46,728 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:46,729 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:46,753 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:46,754 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:46,754 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-10-24 23:47:46,801 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-10-24 23:47:46,802 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-10-24 23:47:46,803 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-10-24 23:47:46,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-10-24 23:47:46,803 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-24 23:47:46,803 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:46,803 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-24 23:47:46,813 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:46,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:46,854 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 23:47:46,856 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:46,944 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Ended with exit code 0 [2024-10-24 23:47:47,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,106 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:47,106 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:47,133 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:47,133 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:47,134 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-10-24 23:47:47,233 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-10-24 23:47:47,236 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-24 23:47:47,237 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-10-24 23:47:47,237 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-10-24 23:47:47,237 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-24 23:47:47,237 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:47,237 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-10-24 23:47:47,238 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:47,238 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-10-24 23:47:47,238 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:47,238 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 157 states and 219 transitions. [2024-10-24 23:47:47,242 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-24 23:47:47,245 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 157 states to 139 states and 201 transitions. [2024-10-24 23:47:47,249 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 55 [2024-10-24 23:47:47,249 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 58 [2024-10-24 23:47:47,250 INFO L73 IsDeterministic]: Start isDeterministic. Operand 139 states and 201 transitions. [2024-10-24 23:47:47,252 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:47,252 INFO L218 hiAutomatonCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-10-24 23:47:47,252 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states and 201 transitions. [2024-10-24 23:47:47,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 120. [2024-10-24 23:47:47,267 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-10-24 23:47:47,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 170 transitions. [2024-10-24 23:47:47,272 INFO L240 hiAutomatonCegarLoop]: Abstraction has 120 states and 170 transitions. [2024-10-24 23:47:47,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 23:47:47,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 23:47:47,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-24 23:47:47,272 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-10-24 23:47:47,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 23:47:47,319 INFO L93 Difference]: Finished difference Result 98 states and 116 transitions. [2024-10-24 23:47:47,320 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 98 states and 116 transitions. [2024-10-24 23:47:47,321 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-10-24 23:47:47,322 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 98 states to 63 states and 75 transitions. [2024-10-24 23:47:47,322 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2024-10-24 23:47:47,322 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 12 [2024-10-24 23:47:47,322 INFO L73 IsDeterministic]: Start isDeterministic. Operand 63 states and 75 transitions. [2024-10-24 23:47:47,322 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-24 23:47:47,322 INFO L218 hiAutomatonCegarLoop]: Abstraction has 63 states and 75 transitions. [2024-10-24 23:47:47,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states and 75 transitions. [2024-10-24 23:47:47,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-10-24 23:47:47,328 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-10-24 23:47:47,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2024-10-24 23:47:47,329 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-10-24 23:47:47,330 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-24 23:47:47,331 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-10-24 23:47:47,331 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-24 23:47:47,331 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 65 transitions. [2024-10-24 23:47:47,331 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-10-24 23:47:47,332 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-24 23:47:47,332 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-24 23:47:47,333 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-10-24 23:47:47,333 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-24 23:47:47,333 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-10-24 23:47:47,334 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-10-24 23:47:47,334 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:47,334 INFO L85 PathProgramCache]: Analyzing trace with hash 1256061253, now seen corresponding path program 2 times [2024-10-24 23:47:47,335 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:47,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649376020] [2024-10-24 23:47:47,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:47,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:47,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-24 23:47:47,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 23:47:47,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,415 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 23:47:47,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,417 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 23:47:47,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,434 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-10-24 23:47:47,434 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 23:47:47,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1649376020] [2024-10-24 23:47:47,435 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1649376020] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 23:47:47,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [333023920] [2024-10-24 23:47:47,435 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 23:47:47,435 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 23:47:47,435 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:47,437 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-10-24 23:47:47,439 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-10-24 23:47:47,475 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 23:47:47,475 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 23:47:47,476 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:47,477 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:47,493 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-10-24 23:47:47,493 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 23:47:47,584 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-10-24 23:47:47,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [333023920] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 23:47:47,584 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 23:47:47,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-10-24 23:47:47,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2001921832] [2024-10-24 23:47:47,585 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 23:47:47,585 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-24 23:47:47,585 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:47,585 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 4 times [2024-10-24 23:47:47,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 23:47:47,586 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1821932007] [2024-10-24 23:47:47,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 23:47:47,586 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 23:47:47,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:47,588 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-24 23:47:47,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-24 23:47:47,589 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-24 23:47:47,616 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:47,616 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:47,616 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:47,616 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:47,616 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-24 23:47:47,616 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,616 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:47,616 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:47,616 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-10-24 23:47:47,616 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:47,616 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:47,617 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,619 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,624 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,626 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,628 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,629 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,654 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:47,654 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-24 23:47:47,654 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,654 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:47,656 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-10-24 23:47:47,658 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-10-24 23:47:47,659 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:47,659 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:47,674 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-24 23:47:47,674 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-10-24 23:47:47,689 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:47,689 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:47,691 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-10-24 23:47:47,693 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-10-24 23:47:47,694 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-24 23:47:47,694 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:47,724 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:47,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:47,725 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-10-24 23:47:47,726 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-10-24 23:47:47,728 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-24 23:47:47,728 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-24 23:47:47,784 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-24 23:47:47,789 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (49)] Ended with exit code 0 [2024-10-24 23:47:47,790 INFO L204 LassoAnalysis]: Preferences: [2024-10-24 23:47:47,790 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-24 23:47:47,790 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-24 23:47:47,790 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-24 23:47:47,790 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-24 23:47:47,790 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,790 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-24 23:47:47,790 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-24 23:47:47,790 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-10-24 23:47:47,790 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-24 23:47:47,790 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-24 23:47:47,791 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,797 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,799 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,802 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,803 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,805 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-24 23:47:47,829 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-24 23:47:47,829 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-24 23:47:47,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:47,831 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-10-24 23:47:47,832 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-10-24 23:47:47,833 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-24 23:47:47,845 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-24 23:47:47,846 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-24 23:47:47,846 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-24 23:47:47,846 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-24 23:47:47,846 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-24 23:47:47,847 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-24 23:47:47,847 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-24 23:47:47,851 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-24 23:47:47,853 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-24 23:47:47,853 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-24 23:47:47,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-24 23:47:47,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 23:47:47,856 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-10-24 23:47:47,857 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-10-24 23:47:47,858 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-24 23:47:47,858 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-24 23:47:47,858 INFO L474 LassoAnalysis]: Proved termination. [2024-10-24 23:47:47,858 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-24 23:47:47,872 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-10-24 23:47:47,873 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-24 23:47:47,887 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:47,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:47,928 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 23:47:47,932 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:48,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:48,133 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:48,134 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:48,146 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-10-24 23:47:48,163 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:48,164 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:48,164 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-10-24 23:47:48,225 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-10-24 23:47:48,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-24 23:47:48,226 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-10-24 23:47:48,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-24 23:47:48,226 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-24 23:47:48,226 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:48,226 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-24 23:47:48,237 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:48,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:48,275 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 23:47:48,276 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:48,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:48,445 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:48,445 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:48,465 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:48,466 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:48,466 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-10-24 23:47:48,520 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-10-24 23:47:48,522 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-24 23:47:48,523 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-10-24 23:47:48,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-24 23:47:48,523 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-24 23:47:48,523 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:48,523 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-24 23:47:48,535 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 23:47:48,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:48,574 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 23:47:48,575 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:48,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 23:47:48,767 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 23:47:48,768 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 23:47:48,790 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 23:47:48,791 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-24 23:47:48,791 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-10-24 23:47:48,865 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-10-24 23:47:48,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-24 23:47:48,866 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-10-24 23:47:48,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-10-24 23:47:48,866 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-24 23:47:48,867 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:48,867 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-10-24 23:47:48,867 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:48,867 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-10-24 23:47:48,867 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-24 23:47:48,868 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 78 states and 90 transitions. [2024-10-24 23:47:48,868 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-24 23:47:48,868 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 78 states to 0 states and 0 transitions. [2024-10-24 23:47:48,869 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-24 23:47:48,869 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-24 23:47:48,869 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-24 23:47:48,869 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-24 23:47:48,869 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 23:47:48,869 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 23:47:48,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 23:47:48,869 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 23:47:48,869 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-24 23:47:48,869 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-10-24 23:47:48,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 23:47:48,870 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-24 23:47:48,870 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-24 23:47:48,870 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-24 23:47:48,870 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-24 23:47:48,870 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-24 23:47:48,870 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 23:47:48,870 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-10-24 23:47:48,870 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-24 23:47:48,871 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-24 23:47:48,871 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-24 23:47:48,877 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 24.10 11:47:48 BoogieIcfgContainer [2024-10-24 23:47:48,878 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-24 23:47:48,878 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-24 23:47:48,878 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-24 23:47:48,878 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-24 23:47:48,879 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 11:47:41" (3/4) ... [2024-10-24 23:47:48,880 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-24 23:47:48,881 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-24 23:47:48,882 INFO L158 Benchmark]: Toolchain (without parser) took 8330.87ms. Allocated memory was 159.4MB in the beginning and 203.4MB in the end (delta: 44.0MB). Free memory was 90.5MB in the beginning and 84.6MB in the end (delta: 5.9MB). Peak memory consumption was 50.5MB. Max. memory is 16.1GB. [2024-10-24 23:47:48,882 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 113.2MB. Free memory is still 73.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-24 23:47:48,882 INFO L158 Benchmark]: CACSL2BoogieTranslator took 235.51ms. Allocated memory is still 159.4MB. Free memory was 90.5MB in the beginning and 79.3MB in the end (delta: 11.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-24 23:47:48,882 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.44ms. Allocated memory is still 159.4MB. Free memory was 79.3MB in the beginning and 77.9MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-24 23:47:48,883 INFO L158 Benchmark]: Boogie Preprocessor took 29.46ms. Allocated memory is still 159.4MB. Free memory was 77.9MB in the beginning and 76.7MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-24 23:47:48,883 INFO L158 Benchmark]: RCFGBuilder took 264.00ms. Allocated memory is still 159.4MB. Free memory was 76.7MB in the beginning and 65.9MB in the end (delta: 10.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-24 23:47:48,883 INFO L158 Benchmark]: BuchiAutomizer took 7766.87ms. Allocated memory was 159.4MB in the beginning and 203.4MB in the end (delta: 44.0MB). Free memory was 65.6MB in the beginning and 85.6MB in the end (delta: -20.0MB). Peak memory consumption was 25.3MB. Max. memory is 16.1GB. [2024-10-24 23:47:48,883 INFO L158 Benchmark]: Witness Printer took 3.27ms. Allocated memory is still 203.4MB. Free memory is still 84.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-24 23:47:48,884 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.13ms. Allocated memory is still 113.2MB. Free memory is still 73.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 235.51ms. Allocated memory is still 159.4MB. Free memory was 90.5MB in the beginning and 79.3MB in the end (delta: 11.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.44ms. Allocated memory is still 159.4MB. Free memory was 79.3MB in the beginning and 77.9MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 29.46ms. Allocated memory is still 159.4MB. Free memory was 77.9MB in the beginning and 76.7MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 264.00ms. Allocated memory is still 159.4MB. Free memory was 76.7MB in the beginning and 65.9MB in the end (delta: 10.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 7766.87ms. Allocated memory was 159.4MB in the beginning and 203.4MB in the end (delta: 44.0MB). Free memory was 65.6MB in the beginning and 85.6MB in the end (delta: -20.0MB). Peak memory consumption was 25.3MB. Max. memory is 16.1GB. * Witness Printer took 3.27ms. Allocated memory is still 203.4MB. Free memory is still 84.6MB. 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 7.6s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 3.9s. Construction of modules took 0.3s. Büchi inclusion checks took 3.1s. Highest rank in rank-based complementation 3. Minimization of det autom 3. Minimization of nondet autom 7. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 89 StatesRemovedByMinimization, 7 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [3, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 22/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 200 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 177 mSDsluCounter, 532 SdHoareTripleChecker+Invalid, 0.4s 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: 28ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 14 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-24 23:47:48,912 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Forceful destruction successful, exit code 0 [2024-10-24 23:47:49,107 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Ended with exit code 0 [2024-10-24 23:47:49,308 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-10-24 23:47:49,509 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