./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 61a67961 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-wip.fs.cvc5-61a6796-m [2024-10-15 00:08:45,065 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-15 00:08:45,143 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-10-15 00:08:45,150 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-15 00:08:45,151 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-15 00:08:45,188 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-15 00:08:45,188 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-15 00:08:45,189 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-15 00:08:45,190 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-15 00:08:45,194 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-15 00:08:45,194 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-15 00:08:45,195 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-15 00:08:45,195 INFO L153 SettingsManager]: * Use SBE=true [2024-10-15 00:08:45,195 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-15 00:08:45,195 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-15 00:08:45,195 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-15 00:08:45,196 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-15 00:08:45,196 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-15 00:08:45,196 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-15 00:08:45,196 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-15 00:08:45,197 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-15 00:08:45,201 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-15 00:08:45,201 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-15 00:08:45,201 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-15 00:08:45,201 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-15 00:08:45,202 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-15 00:08:45,202 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-15 00:08:45,202 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-15 00:08:45,202 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-15 00:08:45,203 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-15 00:08:45,203 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-15 00:08:45,203 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-15 00:08:45,203 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-15 00:08:45,204 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-15 00:08:45,204 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-15 00:08:45,204 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-15 00:08:45,205 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-15 00:08:45,542 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-15 00:08:45,568 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-15 00:08:45,571 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-15 00:08:45,573 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-15 00:08:45,573 INFO L274 PluginConnector]: CDTParser initialized [2024-10-15 00:08:45,575 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-10-15 00:08:47,096 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-15 00:08:47,370 INFO L384 CDTParser]: Found 1 translation units. [2024-10-15 00:08:47,371 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2024-10-15 00:08:47,377 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b089a57e5/d498576f0af5405eb265ce81f8fece2b/FLAGc88025e03 [2024-10-15 00:08:47,716 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b089a57e5/d498576f0af5405eb265ce81f8fece2b [2024-10-15 00:08:47,719 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-15 00:08:47,720 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-15 00:08:47,721 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-15 00:08:47,721 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-15 00:08:47,727 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-15 00:08:47,728 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,729 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3c3ef22e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47, skipping insertion in model container [2024-10-15 00:08:47,730 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,750 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-15 00:08:47,900 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-15 00:08:47,909 INFO L200 MainTranslator]: Completed pre-run [2024-10-15 00:08:47,930 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-15 00:08:47,943 INFO L204 MainTranslator]: Completed translation [2024-10-15 00:08:47,944 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47 WrapperNode [2024-10-15 00:08:47,944 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-15 00:08:47,945 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-15 00:08:47,945 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-15 00:08:47,945 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-15 00:08:47,952 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,957 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,970 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 7 [2024-10-15 00:08:47,971 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-15 00:08:47,972 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-15 00:08:47,972 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-15 00:08:47,972 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-15 00:08:47,982 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,983 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,984 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,990 INFO L175 MemorySlicer]: No memory access in input program. [2024-10-15 00:08:47,990 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,991 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,992 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,994 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,995 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,996 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:47,997 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-15 00:08:47,998 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-15 00:08:47,998 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-15 00:08:47,998 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-15 00:08:47,999 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (1/1) ... [2024-10-15 00:08:48,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:48,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:48,036 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-15 00:08:48,038 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-15 00:08:48,086 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2024-10-15 00:08:48,086 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2024-10-15 00:08:48,086 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2024-10-15 00:08:48,086 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2024-10-15 00:08:48,086 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-15 00:08:48,087 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-15 00:08:48,137 INFO L238 CfgBuilder]: Building ICFG [2024-10-15 00:08:48,139 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-15 00:08:48,244 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-10-15 00:08:48,244 INFO L287 CfgBuilder]: Performing block encoding [2024-10-15 00:08:48,264 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-15 00:08:48,265 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-15 00:08:48,266 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 12:08:48 BoogieIcfgContainer [2024-10-15 00:08:48,266 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-15 00:08:48,268 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-15 00:08:48,268 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-15 00:08:48,272 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-15 00:08:48,273 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-15 00:08:48,273 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 15.10 12:08:47" (1/3) ... [2024-10-15 00:08:48,274 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@75597cbf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 15.10 12:08:48, skipping insertion in model container [2024-10-15 00:08:48,274 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-15 00:08:48,276 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.10 12:08:47" (2/3) ... [2024-10-15 00:08:48,277 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@75597cbf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 15.10 12:08:48, skipping insertion in model container [2024-10-15 00:08:48,277 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-15 00:08:48,277 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 12:08:48" (3/3) ... [2024-10-15 00:08:48,278 INFO L332 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2024-10-15 00:08:48,349 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-15 00:08:48,350 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-15 00:08:48,350 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-15 00:08:48,351 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-15 00:08:48,351 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-15 00:08:48,351 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-15 00:08:48,351 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-15 00:08:48,351 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-15 00:08:48,357 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-15 00:08:48,386 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:48,387 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:48,387 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:48,393 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-15 00:08:48,393 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:48,394 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-15 00:08:48,394 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-15 00:08:48,398 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:48,399 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:48,399 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:48,399 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-15 00:08:48,399 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:48,405 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-15 00:08:48,406 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-15 00:08:48,410 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:48,411 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 1 times [2024-10-15 00:08:48,419 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:48,419 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1275992873] [2024-10-15 00:08:48,419 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:48,420 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:48,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:48,496 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:48,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:48,521 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:48,525 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:48,525 INFO L85 PathProgramCache]: Analyzing trace with hash -1074209557, now seen corresponding path program 1 times [2024-10-15 00:08:48,525 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:48,526 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [228566568] [2024-10-15 00:08:48,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:48,527 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:48,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:48,666 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-15 00:08:48,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:48,757 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-15 00:08:48,758 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-15 00:08:48,758 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [228566568] [2024-10-15 00:08:48,759 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [228566568] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-15 00:08:48,759 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-15 00:08:48,759 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-15 00:08:48,760 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1125860759] [2024-10-15 00:08:48,760 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-15 00:08:48,764 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-15 00:08:48,764 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-15 00:08:48,792 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-15 00:08:48,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-15 00:08:48,795 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-15 00:08:48,889 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-15 00:08:48,889 INFO L93 Difference]: Finished difference Result 26 states and 34 transitions. [2024-10-15 00:08:48,890 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 34 transitions. [2024-10-15 00:08:48,894 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:48,903 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 17 states and 23 transitions. [2024-10-15 00:08:48,908 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2024-10-15 00:08:48,909 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2024-10-15 00:08:48,909 INFO L73 IsDeterministic]: Start isDeterministic. Operand 17 states and 23 transitions. [2024-10-15 00:08:48,911 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-15 00:08:48,911 INFO L218 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-10-15 00:08:48,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states and 23 transitions. [2024-10-15 00:08:48,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-10-15 00:08:48,940 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-15 00:08:48,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2024-10-15 00:08:48,942 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-10-15 00:08:48,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-15 00:08:48,947 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 23 transitions. [2024-10-15 00:08:48,947 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-15 00:08:48,948 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 23 transitions. [2024-10-15 00:08:48,949 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:48,949 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:48,949 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:48,950 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-15 00:08:48,951 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:48,951 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-15 00:08:48,951 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-15 00:08:48,952 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:48,952 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 2 times [2024-10-15 00:08:48,952 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:48,952 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1391935685] [2024-10-15 00:08:48,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:48,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:48,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:48,959 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:48,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:48,962 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:48,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:48,963 INFO L85 PathProgramCache]: Analyzing trace with hash -204878921, now seen corresponding path program 1 times [2024-10-15 00:08:48,963 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:48,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509498598] [2024-10-15 00:08:48,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:48,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:48,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:48,989 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:49,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:49,005 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:49,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:49,007 INFO L85 PathProgramCache]: Analyzing trace with hash -482494696, now seen corresponding path program 1 times [2024-10-15 00:08:49,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:49,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1828949186] [2024-10-15 00:08:49,007 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:49,008 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:49,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:49,032 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:49,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:49,052 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:49,486 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:49,487 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:49,487 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:49,487 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:49,488 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-15 00:08:49,488 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,488 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:49,488 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:49,488 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-10-15 00:08:49,488 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:49,489 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:49,504 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,514 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,517 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,518 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,530 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,571 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:49,572 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-15 00:08:49,575 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,580 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-15 00:08:49,581 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-15 00:08:49,582 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:49,583 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:49,599 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:49,599 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:49,611 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-15 00:08:49,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,613 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-15 00:08:49,615 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-15 00:08:49,615 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:49,616 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:49,638 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:49,638 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:49,661 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-10-15 00:08:49,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,668 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-15 00:08:49,705 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-15 00:08:49,708 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:49,708 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:49,722 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:49,722 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-15 00:08:49,733 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-10-15 00:08:49,734 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,734 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,736 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-15 00:08:49,737 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-15 00:08:49,738 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:49,738 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:49,763 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:49,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,764 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-15 00:08:49,765 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-15 00:08:49,766 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-15 00:08:49,766 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:49,781 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-15 00:08:49,799 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:49,799 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:49,799 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:49,799 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:49,799 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:49,799 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-15 00:08:49,799 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,799 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:49,800 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:49,800 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2024-10-15 00:08:49,800 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:49,800 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:49,801 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,809 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,812 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,814 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,822 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:49,850 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:49,855 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-15 00:08:49,857 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,857 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,859 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-15 00:08:49,860 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-15 00:08:49,861 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-15 00:08:49,872 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:49,872 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:49,873 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:49,873 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:49,873 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:49,874 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:49,875 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:49,876 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:49,888 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-15 00:08:49,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,890 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-15 00:08:49,891 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-15 00:08:49,891 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-15 00:08:49,902 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:49,902 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:49,902 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:49,902 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:49,903 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:49,903 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:49,903 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:49,905 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:49,916 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-15 00:08:49,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,918 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-15 00:08:49,919 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-15 00:08:49,920 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-15 00:08:49,932 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:49,932 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:49,932 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:49,932 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:49,932 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:49,933 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:49,933 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:49,934 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:49,945 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-15 00:08:49,946 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,946 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:49,947 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-15 00:08:49,948 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-15 00:08:49,949 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-15 00:08:49,959 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:49,959 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:49,960 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:49,960 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:49,960 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:49,961 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:49,961 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:49,963 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-15 00:08:49,966 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-15 00:08:49,966 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-15 00:08:49,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:49,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:50,010 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-15 00:08:50,012 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-15 00:08:50,013 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-15 00:08:50,013 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-15 00:08:50,013 INFO L474 LassoAnalysis]: Proved termination. [2024-10-15 00:08:50,014 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2024-10-15 00:08:50,025 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-15 00:08:50,028 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-15 00:08:50,055 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:50,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:50,072 INFO L255 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-15 00:08:50,074 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:50,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:50,142 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-15 00:08:50,147 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:50,357 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-15 00:08:50,362 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-15 00:08:50,363 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-15 00:08:50,738 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-15 00:08:50,743 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-15 00:08:50,744 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-15 00:08:50,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 37 transitions. [2024-10-15 00:08:50,750 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 24 letters. [2024-10-15 00:08:50,751 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:50,752 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 27 letters. Loop has 24 letters. [2024-10-15 00:08:50,752 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:50,752 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 48 letters. [2024-10-15 00:08:50,753 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:50,753 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 102 states and 148 transitions. [2024-10-15 00:08:50,762 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:50,767 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 102 states to 90 states and 136 transitions. [2024-10-15 00:08:50,767 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 39 [2024-10-15 00:08:50,768 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-10-15 00:08:50,768 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 136 transitions. [2024-10-15 00:08:50,769 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:50,769 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 136 transitions. [2024-10-15 00:08:50,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 136 transitions. [2024-10-15 00:08:50,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 63. [2024-10-15 00:08:50,783 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-15 00:08:50,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 99 transitions. [2024-10-15 00:08:50,788 INFO L240 hiAutomatonCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-10-15 00:08:50,788 INFO L425 stractBuchiCegarLoop]: Abstraction has 63 states and 99 transitions. [2024-10-15 00:08:50,788 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-15 00:08:50,788 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 63 states and 99 transitions. [2024-10-15 00:08:50,790 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:50,792 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:50,792 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:50,793 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:50,793 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-15 00:08:50,793 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-15 00:08:50,793 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-15 00:08:50,794 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:50,794 INFO L85 PathProgramCache]: Analyzing trace with hash 838970620, now seen corresponding path program 1 times [2024-10-15 00:08:50,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:50,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1275923687] [2024-10-15 00:08:50,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:50,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:50,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:50,803 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:50,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:50,808 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:50,809 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:50,809 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2024-10-15 00:08:50,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:50,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2021264266] [2024-10-15 00:08:50,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:50,810 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:50,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:50,814 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:50,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:50,816 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:50,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:50,817 INFO L85 PathProgramCache]: Analyzing trace with hash 1359045147, now seen corresponding path program 2 times [2024-10-15 00:08:50,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:50,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [557766802] [2024-10-15 00:08:50,817 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:50,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:50,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:50,823 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:50,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:50,828 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:50,865 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:50,865 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:50,865 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:50,865 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:50,865 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-15 00:08:50,865 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:50,866 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:50,866 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:50,866 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-10-15 00:08:50,866 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:50,866 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:50,867 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:50,869 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:50,871 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:50,873 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:50,876 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:50,881 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:50,918 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:50,918 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-15 00:08:50,918 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:50,918 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:50,920 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-15 00:08:50,922 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-15 00:08:50,927 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:50,927 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:50,939 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:50,939 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:50,951 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:50,951 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:50,951 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:50,953 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-15 00:08:50,954 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-15 00:08:50,956 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:50,956 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:50,969 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:50,969 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-15 00:08:50,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:50,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:50,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:50,982 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-15 00:08:50,983 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-15 00:08:50,984 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:50,984 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:50,996 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:50,996 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-15 00:08:51,010 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-15 00:08:51,010 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,011 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,012 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-15 00:08:51,012 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-15 00:08:51,013 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:51,013 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:51,025 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:51,025 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:51,037 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-15 00:08:51,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,038 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-15 00:08:51,039 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-15 00:08:51,040 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:51,040 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:51,062 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-15 00:08:51,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,064 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-15 00:08:51,064 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-15 00:08:51,067 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-15 00:08:51,067 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:51,114 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-15 00:08:51,119 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-15 00:08:51,119 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:51,119 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:51,119 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:51,119 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:51,119 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-15 00:08:51,119 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,119 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:51,119 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:51,119 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2024-10-15 00:08:51,120 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:51,120 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:51,121 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,123 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,127 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,129 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,133 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,164 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:51,165 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-15 00:08:51,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,167 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-15 00:08:51,169 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-15 00:08:51,170 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-15 00:08:51,181 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,181 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,182 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,182 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,182 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,182 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,182 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,184 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:51,195 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-15 00:08:51,195 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,197 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-15 00:08:51,198 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-15 00:08:51,198 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-15 00:08:51,208 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,209 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,209 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,209 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,209 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,209 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,209 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,211 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:51,222 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-15 00:08:51,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,224 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-15 00:08:51,226 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-15 00:08:51,227 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-15 00:08:51,237 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,237 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,237 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,237 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,237 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,238 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,238 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,239 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:51,250 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:51,251 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,252 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-15 00:08:51,253 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-15 00:08:51,254 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-15 00:08:51,264 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,265 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,265 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,265 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,265 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,265 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,265 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,267 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:51,278 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:51,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,279 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-15 00:08:51,280 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-15 00:08:51,281 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-15 00:08:51,291 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,291 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,291 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,291 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,291 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,293 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,293 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,295 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-15 00:08:51,298 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-15 00:08:51,298 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-15 00:08:51,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,300 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-15 00:08:51,301 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-15 00:08:51,301 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-15 00:08:51,301 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-15 00:08:51,301 INFO L474 LassoAnalysis]: Proved termination. [2024-10-15 00:08:51,302 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-15 00:08:51,313 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-10-15 00:08:51,314 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-15 00:08:51,329 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:51,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:51,350 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-15 00:08:51,351 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:51,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:51,380 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:51,380 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:51,398 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-15 00:08:51,399 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-15 00:08:51,399 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-15 00:08:51,438 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:51,470 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-15 00:08:51,482 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-15 00:08:51,483 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-15 00:08:51,483 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-15 00:08:51,484 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2024-10-15 00:08:51,484 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 3 letters. [2024-10-15 00:08:51,484 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:51,484 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 12 letters. Loop has 3 letters. [2024-10-15 00:08:51,484 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:51,484 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 9 letters. Loop has 6 letters. [2024-10-15 00:08:51,485 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:51,485 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 109 states and 166 transitions. [2024-10-15 00:08:51,488 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:51,492 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 109 states to 97 states and 154 transitions. [2024-10-15 00:08:51,494 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2024-10-15 00:08:51,495 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-10-15 00:08:51,495 INFO L73 IsDeterministic]: Start isDeterministic. Operand 97 states and 154 transitions. [2024-10-15 00:08:51,496 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:51,496 INFO L218 hiAutomatonCegarLoop]: Abstraction has 97 states and 154 transitions. [2024-10-15 00:08:51,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states and 154 transitions. [2024-10-15 00:08:51,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 93. [2024-10-15 00:08:51,507 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-15 00:08:51,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 144 transitions. [2024-10-15 00:08:51,509 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-10-15 00:08:51,509 INFO L425 stractBuchiCegarLoop]: Abstraction has 93 states and 144 transitions. [2024-10-15 00:08:51,509 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-15 00:08:51,509 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 93 states and 144 transitions. [2024-10-15 00:08:51,511 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:51,511 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:51,511 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:51,512 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:51,512 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-15 00:08:51,512 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-15 00:08:51,512 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-15 00:08:51,513 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:51,513 INFO L85 PathProgramCache]: Analyzing trace with hash 372282091, now seen corresponding path program 1 times [2024-10-15 00:08:51,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:51,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [454610775] [2024-10-15 00:08:51,513 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:51,513 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:51,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:51,521 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:51,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:51,529 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:51,529 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:51,529 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2024-10-15 00:08:51,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:51,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1060467186] [2024-10-15 00:08:51,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:51,530 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:51,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:51,533 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:51,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:51,536 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:51,536 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:51,536 INFO L85 PathProgramCache]: Analyzing trace with hash 1050214860, now seen corresponding path program 2 times [2024-10-15 00:08:51,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:51,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621863352] [2024-10-15 00:08:51,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:51,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:51,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:51,586 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-15 00:08:51,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:51,603 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-15 00:08:51,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-15 00:08:51,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621863352] [2024-10-15 00:08:51,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [621863352] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-15 00:08:51,604 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-15 00:08:51,604 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-15 00:08:51,604 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1317967026] [2024-10-15 00:08:51,604 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-15 00:08:51,644 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:51,644 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:51,644 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:51,644 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:51,645 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-15 00:08:51,645 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,645 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:51,645 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:51,645 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-10-15 00:08:51,645 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:51,645 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:51,646 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,648 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,654 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,656 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,658 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,660 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,687 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:51,687 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-15 00:08:51,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,688 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,689 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-15 00:08:51,690 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-15 00:08:51,692 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:51,692 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:51,709 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:51,709 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:51,723 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-15 00:08:51,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,726 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-15 00:08:51,727 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-15 00:08:51,728 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:51,728 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:51,758 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-15 00:08:51,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,760 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-15 00:08:51,765 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-15 00:08:51,765 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-15 00:08:51,766 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:51,826 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-15 00:08:51,833 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-15 00:08:51,834 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:51,834 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:51,834 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:51,834 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:51,834 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-15 00:08:51,834 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,834 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:51,834 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:51,834 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2024-10-15 00:08:51,834 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:51,834 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:51,836 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,839 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,845 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,849 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,851 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,853 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:51,888 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:51,888 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-15 00:08:51,888 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,888 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,891 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-15 00:08:51,893 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-15 00:08:51,893 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-15 00:08:51,906 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,907 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,907 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,907 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,907 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,907 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,908 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,910 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:51,924 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-15 00:08:51,925 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,925 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,927 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-15 00:08:51,928 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-15 00:08:51,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-15 00:08:51,942 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:51,942 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:51,942 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:51,942 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:51,942 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:51,943 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:51,943 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:51,948 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-15 00:08:51,950 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-15 00:08:51,950 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-15 00:08:51,951 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:51,951 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:51,952 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-15 00:08:51,954 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-15 00:08:51,954 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-15 00:08:51,954 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-15 00:08:51,955 INFO L474 LassoAnalysis]: Proved termination. [2024-10-15 00:08:51,955 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-15 00:08:51,970 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-15 00:08:51,971 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-15 00:08:51,982 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:52,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,008 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-15 00:08:52,009 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:52,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,098 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:52,099 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:52,126 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-15 00:08:52,127 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-15 00:08:52,127 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-15 00:08:52,213 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-15 00:08:52,214 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-15 00:08:52,215 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-15 00:08:52,215 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-10-15 00:08:52,215 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 3 letters. [2024-10-15 00:08:52,216 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:52,216 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 17 letters. Loop has 3 letters. [2024-10-15 00:08:52,216 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:52,216 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 14 letters. Loop has 6 letters. [2024-10-15 00:08:52,216 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:52,216 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 133 states and 208 transitions. [2024-10-15 00:08:52,220 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:52,224 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 133 states to 121 states and 196 transitions. [2024-10-15 00:08:52,224 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2024-10-15 00:08:52,224 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 52 [2024-10-15 00:08:52,225 INFO L73 IsDeterministic]: Start isDeterministic. Operand 121 states and 196 transitions. [2024-10-15 00:08:52,225 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:52,225 INFO L218 hiAutomatonCegarLoop]: Abstraction has 121 states and 196 transitions. [2024-10-15 00:08:52,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states and 196 transitions. [2024-10-15 00:08:52,236 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2024-10-15 00:08:52,238 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-15 00:08:52,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 186 transitions. [2024-10-15 00:08:52,240 INFO L240 hiAutomatonCegarLoop]: Abstraction has 117 states and 186 transitions. [2024-10-15 00:08:52,240 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-15 00:08:52,241 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-15 00:08:52,241 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-15 00:08:52,241 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-15 00:08:52,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-15 00:08:52,280 INFO L93 Difference]: Finished difference Result 130 states and 196 transitions. [2024-10-15 00:08:52,280 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 196 transitions. [2024-10-15 00:08:52,283 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-10-15 00:08:52,286 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 128 states and 194 transitions. [2024-10-15 00:08:52,286 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2024-10-15 00:08:52,287 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2024-10-15 00:08:52,287 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 194 transitions. [2024-10-15 00:08:52,287 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:52,287 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 194 transitions. [2024-10-15 00:08:52,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 194 transitions. [2024-10-15 00:08:52,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 105. [2024-10-15 00:08:52,296 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-15 00:08:52,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2024-10-15 00:08:52,297 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-10-15 00:08:52,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-15 00:08:52,298 INFO L425 stractBuchiCegarLoop]: Abstraction has 105 states and 158 transitions. [2024-10-15 00:08:52,298 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-15 00:08:52,299 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 158 transitions. [2024-10-15 00:08:52,301 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-15 00:08:52,301 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:52,301 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:52,302 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:52,302 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2024-10-15 00:08:52,302 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-15 00:08:52,302 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-15 00:08:52,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:52,303 INFO L85 PathProgramCache]: Analyzing trace with hash 1325197585, now seen corresponding path program 1 times [2024-10-15 00:08:52,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:52,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [819522821] [2024-10-15 00:08:52,303 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:52,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:52,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:52,310 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:52,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:52,316 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:52,316 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:52,317 INFO L85 PathProgramCache]: Analyzing trace with hash 949089090, now seen corresponding path program 1 times [2024-10-15 00:08:52,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:52,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [880020885] [2024-10-15 00:08:52,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:52,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:52,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-10-15 00:08:52,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-15 00:08:52,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,417 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-15 00:08:52,417 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-15 00:08:52,417 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [880020885] [2024-10-15 00:08:52,418 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [880020885] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-15 00:08:52,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2070610243] [2024-10-15 00:08:52,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:52,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-15 00:08:52,419 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:52,420 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-15 00:08:52,422 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-15 00:08:52,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,452 INFO L255 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-15 00:08:52,453 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:52,464 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-15 00:08:52,465 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-15 00:08:52,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2070610243] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-15 00:08:52,465 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-15 00:08:52,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-10-15 00:08:52,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [550872266] [2024-10-15 00:08:52,466 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-15 00:08:52,466 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-15 00:08:52,466 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-15 00:08:52,466 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-15 00:08:52,467 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-15 00:08:52,467 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-15 00:08:52,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-15 00:08:52,499 INFO L93 Difference]: Finished difference Result 120 states and 174 transitions. [2024-10-15 00:08:52,499 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 120 states and 174 transitions. [2024-10-15 00:08:52,501 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:52,505 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 120 states to 115 states and 165 transitions. [2024-10-15 00:08:52,506 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2024-10-15 00:08:52,506 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2024-10-15 00:08:52,506 INFO L73 IsDeterministic]: Start isDeterministic. Operand 115 states and 165 transitions. [2024-10-15 00:08:52,506 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:52,506 INFO L218 hiAutomatonCegarLoop]: Abstraction has 115 states and 165 transitions. [2024-10-15 00:08:52,506 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states and 165 transitions. [2024-10-15 00:08:52,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 112. [2024-10-15 00:08:52,525 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-15 00:08:52,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 162 transitions. [2024-10-15 00:08:52,529 INFO L240 hiAutomatonCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-10-15 00:08:52,530 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-15 00:08:52,530 INFO L425 stractBuchiCegarLoop]: Abstraction has 112 states and 162 transitions. [2024-10-15 00:08:52,531 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-15 00:08:52,531 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 112 states and 162 transitions. [2024-10-15 00:08:52,532 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2024-10-15 00:08:52,533 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:52,533 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:52,534 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-15 00:08:52,534 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-15 00:08:52,534 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-15 00:08:52,534 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-15 00:08:52,535 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:52,535 INFO L85 PathProgramCache]: Analyzing trace with hash 1060897207, now seen corresponding path program 1 times [2024-10-15 00:08:52,535 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:52,535 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [495822964] [2024-10-15 00:08:52,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:52,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:52,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:52,551 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:52,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:52,567 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:52,571 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:52,572 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 3 times [2024-10-15 00:08:52,572 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:52,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1233348178] [2024-10-15 00:08:52,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:52,572 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:52,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:52,576 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:52,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:52,580 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:52,581 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:52,581 INFO L85 PathProgramCache]: Analyzing trace with hash -1475637376, now seen corresponding path program 2 times [2024-10-15 00:08:52,581 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:52,581 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1783042804] [2024-10-15 00:08:52,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:52,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:52,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,663 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-15 00:08:52,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,753 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-15 00:08:52,756 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-15 00:08:52,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,760 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-15 00:08:52,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,763 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-15 00:08:52,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:52,777 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-15 00:08:52,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-15 00:08:52,778 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1783042804] [2024-10-15 00:08:52,778 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1783042804] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-15 00:08:52,778 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2098573567] [2024-10-15 00:08:52,778 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-15 00:08:52,778 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-15 00:08:52,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:52,780 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-15 00:08:52,782 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-15 00:08:52,825 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-15 00:08:52,826 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-15 00:08:52,827 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:52,828 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:52,855 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-15 00:08:52,855 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-15 00:08:52,963 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-15 00:08:52,963 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2098573567] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-15 00:08:52,963 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-15 00:08:52,963 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-10-15 00:08:52,964 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [855966082] [2024-10-15 00:08:52,964 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-15 00:08:52,994 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:52,995 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:52,995 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:52,995 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:52,995 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-15 00:08:52,995 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:52,995 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:52,995 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:52,995 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-10-15 00:08:52,995 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:52,995 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:52,996 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:52,998 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,001 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,003 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,005 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,007 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,036 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:53,037 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-15 00:08:53,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,039 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-15 00:08:53,041 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-15 00:08:53,043 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:53,044 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,056 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:53,056 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:53,067 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-10-15 00:08:53,067 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,067 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,069 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-15 00:08:53,070 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-15 00:08:53,071 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:53,071 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,088 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:53,089 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-15 00:08:53,105 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2024-10-15 00:08:53,106 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,108 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-15 00:08:53,109 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-15 00:08:53,110 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:53,110 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,128 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:53,128 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-15 00:08:53,143 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-15 00:08:53,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,145 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-15 00:08:53,146 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-15 00:08:53,147 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:53,147 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,158 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:53,159 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-15 00:08:53,169 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-15 00:08:53,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,170 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,172 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-15 00:08:53,175 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:53,175 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,177 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-15 00:08:53,188 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:53,188 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-15 00:08:53,198 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-15 00:08:53,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,200 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-15 00:08:53,201 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-15 00:08:53,202 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:53,202 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,223 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2024-10-15 00:08:53,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,224 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,225 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-15 00:08:53,226 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-15 00:08:53,227 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-15 00:08:53,227 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:53,275 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-15 00:08:53,280 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-15 00:08:53,280 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:53,280 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:53,280 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:53,280 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:53,280 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-15 00:08:53,280 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,280 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:53,280 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:53,280 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2024-10-15 00:08:53,280 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:53,280 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:53,281 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,286 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,289 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,291 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,293 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,295 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:53,325 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:53,325 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-15 00:08:53,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,329 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-15 00:08:53,330 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-15 00:08:53,331 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-15 00:08:53,344 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:53,344 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:53,344 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:53,344 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:53,345 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:53,345 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:53,345 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:53,350 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:53,365 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-15 00:08:53,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,365 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,368 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-15 00:08:53,369 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-15 00:08:53,371 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-15 00:08:53,383 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:53,383 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:53,383 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:53,384 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:53,384 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:53,384 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:53,384 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:53,385 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:53,396 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Ended with exit code 0 [2024-10-15 00:08:53,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,398 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-15 00:08:53,399 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-15 00:08:53,399 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-15 00:08:53,410 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:53,410 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:53,410 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:53,410 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:53,410 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:53,411 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:53,411 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:53,412 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:53,424 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-10-15 00:08:53,424 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,424 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,425 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-15 00:08:53,427 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-15 00:08:53,427 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-15 00:08:53,437 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:53,437 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:53,437 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:53,437 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:53,437 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:53,438 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:53,438 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:53,439 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:53,450 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-15 00:08:53,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,450 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,452 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-15 00:08:53,453 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-15 00:08:53,454 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-15 00:08:53,464 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:53,465 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:53,465 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:53,465 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:53,465 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:53,465 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:53,465 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:53,467 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-15 00:08:53,482 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:53,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,485 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-15 00:08:53,489 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-15 00:08:53,489 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-15 00:08:53,502 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:53,502 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:53,502 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:53,502 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:53,502 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:53,503 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:53,503 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:53,505 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-15 00:08:53,507 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-15 00:08:53,507 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-15 00:08:53,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:53,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:53,509 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-15 00:08:53,511 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-15 00:08:53,511 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-15 00:08:53,511 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-15 00:08:53,511 INFO L474 LassoAnalysis]: Proved termination. [2024-10-15 00:08:53,511 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-15 00:08:53,527 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:53,528 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-15 00:08:53,542 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:53,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:53,588 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-15 00:08:53,590 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:53,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:53,843 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:53,844 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:53,870 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-15 00:08:53,871 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-15 00:08:53,872 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-15 00:08:53,927 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-15 00:08:53,928 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-15 00:08:53,928 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-15 00:08:53,929 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-10-15 00:08:53,929 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-15 00:08:53,929 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:53,929 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-15 00:08:53,945 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:53,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:53,992 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-15 00:08:53,994 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:54,061 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-15 00:08:54,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,265 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:54,265 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:54,289 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-15 00:08:54,290 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-15 00:08:54,290 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-15 00:08:54,345 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-15 00:08:54,346 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-15 00:08:54,346 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-15 00:08:54,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-10-15 00:08:54,347 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-15 00:08:54,347 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:54,347 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-15 00:08:54,359 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:54,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,406 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-15 00:08:54,408 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:54,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,631 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:54,632 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:54,655 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-15 00:08:54,656 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-15 00:08:54,656 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-15 00:08:54,750 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-15 00:08:54,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-15 00:08:54,753 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-15 00:08:54,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-10-15 00:08:54,754 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-15 00:08:54,754 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:54,754 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-10-15 00:08:54,755 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:54,755 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-10-15 00:08:54,755 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:54,755 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 157 states and 219 transitions. [2024-10-15 00:08:54,759 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-15 00:08:54,764 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 157 states to 139 states and 201 transitions. [2024-10-15 00:08:54,765 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 55 [2024-10-15 00:08:54,765 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 58 [2024-10-15 00:08:54,765 INFO L73 IsDeterministic]: Start isDeterministic. Operand 139 states and 201 transitions. [2024-10-15 00:08:54,766 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:54,766 INFO L218 hiAutomatonCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-10-15 00:08:54,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states and 201 transitions. [2024-10-15 00:08:54,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 120. [2024-10-15 00:08:54,781 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-15 00:08:54,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 170 transitions. [2024-10-15 00:08:54,783 INFO L240 hiAutomatonCegarLoop]: Abstraction has 120 states and 170 transitions. [2024-10-15 00:08:54,783 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-15 00:08:54,783 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-15 00:08:54,783 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-15 00:08:54,783 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-15 00:08:54,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-15 00:08:54,831 INFO L93 Difference]: Finished difference Result 98 states and 116 transitions. [2024-10-15 00:08:54,831 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 98 states and 116 transitions. [2024-10-15 00:08:54,832 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-10-15 00:08:54,832 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 98 states to 63 states and 75 transitions. [2024-10-15 00:08:54,832 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2024-10-15 00:08:54,833 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 12 [2024-10-15 00:08:54,833 INFO L73 IsDeterministic]: Start isDeterministic. Operand 63 states and 75 transitions. [2024-10-15 00:08:54,833 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-15 00:08:54,833 INFO L218 hiAutomatonCegarLoop]: Abstraction has 63 states and 75 transitions. [2024-10-15 00:08:54,835 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states and 75 transitions. [2024-10-15 00:08:54,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-10-15 00:08:54,841 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-15 00:08:54,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2024-10-15 00:08:54,842 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-10-15 00:08:54,842 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-15 00:08:54,843 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-10-15 00:08:54,843 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-15 00:08:54,843 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 65 transitions. [2024-10-15 00:08:54,843 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-10-15 00:08:54,844 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-15 00:08:54,844 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-15 00:08:54,844 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-15 00:08:54,844 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-15 00:08:54,845 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-15 00:08:54,845 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-15 00:08:54,845 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:54,845 INFO L85 PathProgramCache]: Analyzing trace with hash 1256061253, now seen corresponding path program 2 times [2024-10-15 00:08:54,845 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:54,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515273293] [2024-10-15 00:08:54,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:54,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:54,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,900 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-15 00:08:54,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,935 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-15 00:08:54,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,942 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-15 00:08:54,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,944 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-15 00:08:54,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:54,963 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-10-15 00:08:54,964 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-15 00:08:54,964 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515273293] [2024-10-15 00:08:54,964 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1515273293] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-15 00:08:54,964 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2003049976] [2024-10-15 00:08:54,964 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-15 00:08:54,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-15 00:08:54,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:54,966 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-15 00:08:54,968 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-15 00:08:55,002 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-15 00:08:55,002 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-15 00:08:55,003 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:55,004 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:55,020 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-15 00:08:55,021 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-15 00:08:55,120 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-15 00:08:55,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2003049976] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-15 00:08:55,120 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-15 00:08:55,120 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2024-10-15 00:08:55,120 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [755982533] [2024-10-15 00:08:55,120 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-15 00:08:55,121 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-15 00:08:55,121 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:55,121 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 4 times [2024-10-15 00:08:55,121 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-15 00:08:55,121 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1368590401] [2024-10-15 00:08:55,121 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-15 00:08:55,122 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-15 00:08:55,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:55,125 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-15 00:08:55,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-15 00:08:55,127 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-15 00:08:55,156 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:55,156 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:55,156 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:55,156 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:55,156 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-15 00:08:55,156 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,156 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:55,156 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:55,156 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-10-15 00:08:55,157 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:55,157 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:55,159 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,166 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,168 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,169 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,171 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,196 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:55,196 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-15 00:08:55,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:55,199 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-15 00:08:55,206 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-15 00:08:55,207 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:55,207 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:55,219 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-15 00:08:55,219 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-15 00:08:55,229 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-15 00:08:55,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:55,231 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-15 00:08:55,232 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-15 00:08:55,232 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-15 00:08:55,232 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:55,254 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-15 00:08:55,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:55,256 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-15 00:08:55,257 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-15 00:08:55,257 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-15 00:08:55,257 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-15 00:08:55,303 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-15 00:08:55,308 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-15 00:08:55,308 INFO L204 LassoAnalysis]: Preferences: [2024-10-15 00:08:55,308 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-15 00:08:55,308 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-15 00:08:55,308 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-15 00:08:55,308 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-15 00:08:55,308 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,308 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-15 00:08:55,308 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-15 00:08:55,309 INFO L132 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2024-10-15 00:08:55,309 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-15 00:08:55,309 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-15 00:08:55,310 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,318 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,319 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,321 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,323 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,324 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-15 00:08:55,352 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-15 00:08:55,352 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-15 00:08:55,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:55,355 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-15 00:08:55,357 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-15 00:08:55,362 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-15 00:08:55,376 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-15 00:08:55,376 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-15 00:08:55,376 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-15 00:08:55,376 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-15 00:08:55,376 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-15 00:08:55,377 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-15 00:08:55,377 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-15 00:08:55,381 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-15 00:08:55,386 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-15 00:08:55,387 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-15 00:08:55,387 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-15 00:08:55,387 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-15 00:08:55,389 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-15 00:08:55,391 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-15 00:08:55,392 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-15 00:08:55,392 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-15 00:08:55,392 INFO L474 LassoAnalysis]: Proved termination. [2024-10-15 00:08:55,392 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2024-10-15 00:08:55,407 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-15 00:08:55,408 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-15 00:08:55,419 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:55,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:55,463 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-15 00:08:55,465 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:55,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:55,655 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:55,655 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:55,676 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-15 00:08:55,677 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-15 00:08:55,677 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-15 00:08:55,731 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-15 00:08:55,732 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-15 00:08:55,732 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-15 00:08:55,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-15 00:08:55,733 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-15 00:08:55,733 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:55,733 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-15 00:08:55,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:55,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:55,787 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-15 00:08:55,789 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:55,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:55,968 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:55,968 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:55,990 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-15 00:08:55,991 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-15 00:08:55,991 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-15 00:08:56,048 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-15 00:08:56,049 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-15 00:08:56,049 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-15 00:08:56,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-15 00:08:56,049 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-15 00:08:56,050 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:56,050 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-15 00:08:56,060 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-15 00:08:56,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:56,102 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-15 00:08:56,104 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:56,295 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (51)] Forceful destruction successful, exit code 0 [2024-10-15 00:08:56,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-15 00:08:56,309 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-15 00:08:56,310 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-15 00:08:56,330 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-15 00:08:56,330 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-15 00:08:56,331 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-15 00:08:56,412 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-15 00:08:56,412 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-15 00:08:56,413 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-15 00:08:56,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 25 transitions. [2024-10-15 00:08:56,413 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2024-10-15 00:08:56,414 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:56,414 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2024-10-15 00:08:56,414 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:56,414 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2024-10-15 00:08:56,414 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-15 00:08:56,414 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 78 states and 90 transitions. [2024-10-15 00:08:56,415 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-15 00:08:56,415 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 78 states to 0 states and 0 transitions. [2024-10-15 00:08:56,415 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-15 00:08:56,415 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-15 00:08:56,415 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-15 00:08:56,416 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-15 00:08:56,416 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-15 00:08:56,416 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-15 00:08:56,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-15 00:08:56,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-15 00:08:56,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-15 00:08:56,417 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-15 00:08:56,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-15 00:08:56,417 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-10-15 00:08:56,417 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-10-15 00:08:56,417 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-15 00:08:56,418 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-10-15 00:08:56,418 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-15 00:08:56,418 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-15 00:08:56,418 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-15 00:08:56,418 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-15 00:08:56,418 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-15 00:08:56,418 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-15 00:08:56,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-15 00:08:56,418 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-15 00:08:56,418 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-10-15 00:08:56,419 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-15 00:08:56,419 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-15 00:08:56,419 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-15 00:08:56,426 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 15.10 12:08:56 BoogieIcfgContainer [2024-10-15 00:08:56,426 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-15 00:08:56,427 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-15 00:08:56,427 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-15 00:08:56,427 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-15 00:08:56,427 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 12:08:48" (3/4) ... [2024-10-15 00:08:56,429 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-15 00:08:56,430 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-15 00:08:56,431 INFO L158 Benchmark]: Toolchain (without parser) took 8710.95ms. Allocated memory was 163.6MB in the beginning and 203.4MB in the end (delta: 39.8MB). Free memory was 131.6MB in the beginning and 158.6MB in the end (delta: -27.0MB). Peak memory consumption was 13.9MB. Max. memory is 16.1GB. [2024-10-15 00:08:56,431 INFO L158 Benchmark]: CDTParser took 0.64ms. Allocated memory is still 117.4MB. Free memory is still 91.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-15 00:08:56,431 INFO L158 Benchmark]: CACSL2BoogieTranslator took 222.75ms. Allocated memory is still 163.6MB. Free memory was 131.6MB in the beginning and 121.5MB in the end (delta: 10.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-15 00:08:56,431 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.22ms. Allocated memory is still 163.6MB. Free memory was 121.5MB in the beginning and 120.1MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-15 00:08:56,432 INFO L158 Benchmark]: Boogie Preprocessor took 25.63ms. Allocated memory is still 163.6MB. Free memory was 120.1MB in the beginning and 118.6MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-15 00:08:56,432 INFO L158 Benchmark]: RCFGBuilder took 268.03ms. Allocated memory is still 163.6MB. Free memory was 118.6MB in the beginning and 107.6MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-15 00:08:56,432 INFO L158 Benchmark]: BuchiAutomizer took 8158.57ms. Allocated memory was 163.6MB in the beginning and 203.4MB in the end (delta: 39.8MB). Free memory was 107.6MB in the beginning and 158.6MB in the end (delta: -51.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-15 00:08:56,432 INFO L158 Benchmark]: Witness Printer took 3.47ms. Allocated memory is still 203.4MB. Free memory is still 158.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-15 00:08:56,433 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.64ms. Allocated memory is still 117.4MB. Free memory is still 91.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 222.75ms. Allocated memory is still 163.6MB. Free memory was 131.6MB in the beginning and 121.5MB in the end (delta: 10.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.22ms. Allocated memory is still 163.6MB. Free memory was 121.5MB in the beginning and 120.1MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 25.63ms. Allocated memory is still 163.6MB. Free memory was 120.1MB in the beginning and 118.6MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 268.03ms. Allocated memory is still 163.6MB. Free memory was 118.6MB in the beginning and 107.6MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 8158.57ms. Allocated memory was 163.6MB in the beginning and 203.4MB in the end (delta: 39.8MB). Free memory was 107.6MB in the beginning and 158.6MB in the end (delta: -51.1MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.47ms. Allocated memory is still 203.4MB. Free memory is still 158.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 8.0s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 4.1s. Construction of modules took 0.4s. Büchi inclusion checks took 3.3s. 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.5s 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: 19ms 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-15 00:08:56,459 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-15 00:08:56,655 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-15 00:08:56,855 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Ended with exit code 0 [2024-10-15 00:08:57,056 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE