./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version b5317dae Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --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.2-?-b5317da-m [2023-02-16 04:30:01,124 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-16 04:30:01,127 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-16 04:30:01,166 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-16 04:30:01,166 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-16 04:30:01,169 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-16 04:30:01,171 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-16 04:30:01,173 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-16 04:30:01,175 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-16 04:30:01,180 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-16 04:30:01,181 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-16 04:30:01,183 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-16 04:30:01,183 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-16 04:30:01,185 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-16 04:30:01,187 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-16 04:30:01,188 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-16 04:30:01,189 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-16 04:30:01,190 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-16 04:30:01,191 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-16 04:30:01,196 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-16 04:30:01,198 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-16 04:30:01,199 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-16 04:30:01,200 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-16 04:30:01,201 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-16 04:30:01,209 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-16 04:30:01,209 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-16 04:30:01,210 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-16 04:30:01,211 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-16 04:30:01,212 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-16 04:30:01,212 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-16 04:30:01,213 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-16 04:30:01,213 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-16 04:30:01,215 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-16 04:30:01,216 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-16 04:30:01,226 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-16 04:30:01,226 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-16 04:30:01,227 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-16 04:30:01,227 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-16 04:30:01,227 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-16 04:30:01,228 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-16 04:30:01,228 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-16 04:30:01,229 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2023-02-16 04:30:01,254 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-16 04:30:01,257 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-16 04:30:01,257 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-16 04:30:01,258 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-16 04:30:01,259 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-16 04:30:01,259 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-16 04:30:01,259 INFO L138 SettingsManager]: * Use SBE=true [2023-02-16 04:30:01,259 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2023-02-16 04:30:01,259 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2023-02-16 04:30:01,260 INFO L138 SettingsManager]: * Use old map elimination=false [2023-02-16 04:30:01,260 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2023-02-16 04:30:01,261 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2023-02-16 04:30:01,261 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2023-02-16 04:30:01,261 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-16 04:30:01,261 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2023-02-16 04:30:01,261 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-16 04:30:01,261 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-16 04:30:01,262 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2023-02-16 04:30:01,262 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2023-02-16 04:30:01,262 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2023-02-16 04:30:01,262 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-16 04:30:01,262 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2023-02-16 04:30:01,262 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-16 04:30:01,263 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2023-02-16 04:30:01,263 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-16 04:30:01,263 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-16 04:30:01,264 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-16 04:30:01,264 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-16 04:30:01,265 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2023-02-16 04:30:01,265 INFO L138 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.graphml 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 [2023-02-16 04:30:01,523 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-16 04:30:01,554 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-16 04:30:01,557 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-16 04:30:01,559 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-16 04:30:01,559 INFO L275 PluginConnector]: CDTParser initialized [2023-02-16 04:30:01,561 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2023-02-16 04:30:02,812 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-16 04:30:03,015 INFO L351 CDTParser]: Found 1 translation units. [2023-02-16 04:30:03,016 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/NestedRecursion_1d.c [2023-02-16 04:30:03,021 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d1552dcfd/203dbab8828a4884a354ef3bb48a6d04/FLAG29522482f [2023-02-16 04:30:03,042 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d1552dcfd/203dbab8828a4884a354ef3bb48a6d04 [2023-02-16 04:30:03,045 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-16 04:30:03,046 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-16 04:30:03,048 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-16 04:30:03,048 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-16 04:30:03,051 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-16 04:30:03,051 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,052 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2a99768b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03, skipping insertion in model container [2023-02-16 04:30:03,052 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,058 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-16 04:30:03,071 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-16 04:30:03,185 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-16 04:30:03,193 INFO L203 MainTranslator]: Completed pre-run [2023-02-16 04:30:03,208 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-16 04:30:03,219 INFO L208 MainTranslator]: Completed translation [2023-02-16 04:30:03,220 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03 WrapperNode [2023-02-16 04:30:03,220 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-16 04:30:03,222 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-16 04:30:03,222 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-16 04:30:03,222 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-16 04:30:03,229 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,235 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,245 INFO L138 Inliner]: procedures = 6, calls = 8, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 6 [2023-02-16 04:30:03,246 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-16 04:30:03,247 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-16 04:30:03,247 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-16 04:30:03,247 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-16 04:30:03,252 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,253 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,253 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,253 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,255 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,256 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,256 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,257 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,258 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-16 04:30:03,261 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-16 04:30:03,261 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-16 04:30:03,261 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-16 04:30:03,262 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (1/1) ... [2023-02-16 04:30:03,269 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:03,280 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:03,299 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) [2023-02-16 04:30:03,301 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 [2023-02-16 04:30:03,336 INFO L130 BoogieDeclarations]: Found specification of procedure rec1 [2023-02-16 04:30:03,336 INFO L138 BoogieDeclarations]: Found implementation of procedure rec1 [2023-02-16 04:30:03,336 INFO L130 BoogieDeclarations]: Found specification of procedure rec2 [2023-02-16 04:30:03,336 INFO L138 BoogieDeclarations]: Found implementation of procedure rec2 [2023-02-16 04:30:03,337 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-16 04:30:03,337 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-16 04:30:03,379 INFO L235 CfgBuilder]: Building ICFG [2023-02-16 04:30:03,381 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-16 04:30:03,451 INFO L276 CfgBuilder]: Performing block encoding [2023-02-16 04:30:03,458 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-16 04:30:03,459 INFO L300 CfgBuilder]: Removed 0 assume(true) statements. [2023-02-16 04:30:03,460 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 04:30:03 BoogieIcfgContainer [2023-02-16 04:30:03,461 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-16 04:30:03,461 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2023-02-16 04:30:03,462 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2023-02-16 04:30:03,465 INFO L275 PluginConnector]: BuchiAutomizer initialized [2023-02-16 04:30:03,465 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2023-02-16 04:30:03,466 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 16.02 04:30:03" (1/3) ... [2023-02-16 04:30:03,467 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@4d1be4da and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 16.02 04:30:03, skipping insertion in model container [2023-02-16 04:30:03,467 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2023-02-16 04:30:03,467 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 04:30:03" (2/3) ... [2023-02-16 04:30:03,467 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@4d1be4da and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 16.02 04:30:03, skipping insertion in model container [2023-02-16 04:30:03,467 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2023-02-16 04:30:03,468 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 04:30:03" (3/3) ... [2023-02-16 04:30:03,469 INFO L332 chiAutomizerObserver]: Analyzing ICFG NestedRecursion_1d.c [2023-02-16 04:30:03,518 INFO L303 stractBuchiCegarLoop]: Interprodecural is true [2023-02-16 04:30:03,519 INFO L304 stractBuchiCegarLoop]: Hoare is false [2023-02-16 04:30:03,519 INFO L305 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2023-02-16 04:30:03,519 INFO L306 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2023-02-16 04:30:03,519 INFO L307 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2023-02-16 04:30:03,519 INFO L308 stractBuchiCegarLoop]: Difference is false [2023-02-16 04:30:03,519 INFO L309 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2023-02-16 04:30:03,519 INFO L313 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2023-02-16 04:30:03,522 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) [2023-02-16 04:30:03,540 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:03,540 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:03,540 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:03,545 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2023-02-16 04:30:03,545 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:03,545 INFO L335 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2023-02-16 04:30:03,546 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) [2023-02-16 04:30:03,548 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:03,548 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:03,548 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:03,549 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2023-02-16 04:30:03,549 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:03,555 INFO L748 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;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 [2023-02-16 04:30:03,556 INFO L750 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 [2023-02-16 04:30:03,560 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:03,560 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 1 times [2023-02-16 04:30:03,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:03,567 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [508497596] [2023-02-16 04:30:03,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:03,568 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:03,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:03,637 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:03,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:03,664 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:03,667 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:03,668 INFO L85 PathProgramCache]: Analyzing trace with hash -1074209557, now seen corresponding path program 1 times [2023-02-16 04:30:03,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:03,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1770129477] [2023-02-16 04:30:03,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:03,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:03,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:03,827 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2023-02-16 04:30:03,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:03,903 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:03,903 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 04:30:03,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1770129477] [2023-02-16 04:30:03,904 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1770129477] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 04:30:03,904 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 04:30:03,904 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-16 04:30:03,904 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1783439260] [2023-02-16 04:30:03,905 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 04:30:03,909 INFO L765 eck$LassoCheckResult]: loop already infeasible [2023-02-16 04:30:03,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 04:30:03,950 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 04:30:03,965 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-16 04:30:03,967 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) [2023-02-16 04:30:04,088 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 04:30:04,093 INFO L93 Difference]: Finished difference Result 26 states and 34 transitions. [2023-02-16 04:30:04,095 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 34 transitions. [2023-02-16 04:30:04,098 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:04,102 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 17 states and 23 transitions. [2023-02-16 04:30:04,105 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2023-02-16 04:30:04,106 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2023-02-16 04:30:04,106 INFO L73 IsDeterministic]: Start isDeterministic. Operand 17 states and 23 transitions. [2023-02-16 04:30:04,108 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-02-16 04:30:04,108 INFO L218 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2023-02-16 04:30:04,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states and 23 transitions. [2023-02-16 04:30:04,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2023-02-16 04:30:04,142 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) [2023-02-16 04:30:04,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2023-02-16 04:30:04,144 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 23 transitions. [2023-02-16 04:30:04,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-02-16 04:30:04,154 INFO L428 stractBuchiCegarLoop]: Abstraction has 17 states and 23 transitions. [2023-02-16 04:30:04,154 INFO L335 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2023-02-16 04:30:04,154 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 23 transitions. [2023-02-16 04:30:04,155 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:04,155 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:04,155 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:04,158 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2023-02-16 04:30:04,158 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:04,159 INFO L748 eck$LassoCheckResult]: Stem: 80#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 77#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;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 66#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 67#$Ultimate##0 [2023-02-16 04:30:04,159 INFO L750 eck$LassoCheckResult]: Loop: 67#$Ultimate##0 ~j := #in~j; 74#L18 assume !(~j <= 0); 72#L20 call #t~ret3 := rec1(~j);< 68#$Ultimate##0 ~i := #in~i; 73#L12 assume !(~i <= 0); 69#L14 call #t~ret0 := rec1(~i - 2);< 68#$Ultimate##0 ~i := #in~i; 73#L12 assume ~i <= 0;#res := 0; 78#rec1FINAL assume true; 79#rec1EXIT >#28#return; 70#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 68#$Ultimate##0 ~i := #in~i; 73#L12 assume ~i <= 0;#res := 0; 78#rec1FINAL assume true; 79#rec1EXIT >#30#return; 71#L14-2 call #t~ret2 := rec1(#t~ret1);< 68#$Ultimate##0 ~i := #in~i; 73#L12 assume ~i <= 0;#res := 0; 78#rec1FINAL assume true; 79#rec1EXIT >#32#return; 75#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 76#rec1FINAL assume true; 81#rec1EXIT >#34#return; 65#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 67#$Ultimate##0 [2023-02-16 04:30:04,160 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:04,160 INFO L85 PathProgramCache]: Analyzing trace with hash 48738, now seen corresponding path program 2 times [2023-02-16 04:30:04,161 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:04,161 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [312594550] [2023-02-16 04:30:04,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:04,162 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:04,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:04,173 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:04,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:04,178 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:04,179 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:04,179 INFO L85 PathProgramCache]: Analyzing trace with hash -204878921, now seen corresponding path program 1 times [2023-02-16 04:30:04,180 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:04,180 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325017376] [2023-02-16 04:30:04,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:04,181 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:04,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:04,218 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:04,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:04,241 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:04,244 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:04,244 INFO L85 PathProgramCache]: Analyzing trace with hash -482494696, now seen corresponding path program 1 times [2023-02-16 04:30:04,245 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:04,245 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1831249570] [2023-02-16 04:30:04,246 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:04,251 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:04,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:04,267 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:04,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:04,288 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:04,701 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:04,702 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:04,702 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:04,702 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:04,703 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-02-16 04:30:04,703 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,703 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:04,703 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:04,703 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2023-02-16 04:30:04,703 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:04,704 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:04,717 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,727 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,731 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,736 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,748 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,800 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:04,801 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-02-16 04:30:04,803 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,803 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:04,809 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) [2023-02-16 04:30:04,818 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:04,818 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:04,818 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 [2023-02-16 04:30:04,834 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:04,835 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_~j=0} Honda state: {rec2_~j=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:04,842 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:04,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:04,845 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) [2023-02-16 04:30:04,848 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 [2023-02-16 04:30:04,850 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:04,851 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:04,858 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:04,858 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#res=0} Honda state: {rec2_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:04,864 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:04,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:04,869 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) [2023-02-16 04:30:04,880 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:04,880 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:04,890 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 [2023-02-16 04:30:04,901 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:04,901 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec2_#t~ret4=0} Honda state: {rec2_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:04,908 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:04,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,909 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:04,912 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) [2023-02-16 04:30:04,915 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 [2023-02-16 04:30:04,917 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:04,917 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:04,942 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 [2023-02-16 04:30:04,942 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,943 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:04,944 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) [2023-02-16 04:30:04,944 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 [2023-02-16 04:30:04,947 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-02-16 04:30:04,948 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:04,969 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-02-16 04:30:04,976 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 [2023-02-16 04:30:04,976 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:04,977 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:04,977 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:04,977 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:04,977 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-02-16 04:30:04,977 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:04,977 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:04,977 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:04,977 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration2_Loop [2023-02-16 04:30:04,977 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:04,977 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:04,978 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,982 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,985 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,989 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:04,995 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:05,035 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:05,039 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-02-16 04:30:05,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:05,041 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:05,046 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) [2023-02-16 04:30:05,049 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 [2023-02-16 04:30:05,051 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2023-02-16 04:30:05,059 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:05,059 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:05,059 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:05,060 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:05,060 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:05,061 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:05,062 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:05,069 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:05,072 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:05,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:05,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:05,074 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) [2023-02-16 04:30:05,087 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 [2023-02-16 04:30:05,088 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 [2023-02-16 04:30:05,096 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:05,096 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:05,096 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:05,096 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:05,096 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:05,097 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:05,097 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:05,113 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:05,117 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2023-02-16 04:30:05,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:05,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:05,119 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) [2023-02-16 04:30:05,121 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 [2023-02-16 04:30:05,124 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 [2023-02-16 04:30:05,134 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:05,134 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:05,134 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:05,134 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:05,134 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:05,135 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:05,135 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:05,141 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:05,144 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:05,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:05,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:05,146 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) [2023-02-16 04:30:05,149 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 [2023-02-16 04:30:05,152 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 [2023-02-16 04:30:05,158 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:05,158 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:05,158 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:05,158 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:05,158 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:05,159 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:05,159 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:05,165 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-02-16 04:30:05,168 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2023-02-16 04:30:05,168 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2023-02-16 04:30:05,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:05,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:05,314 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) [2023-02-16 04:30:05,315 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 [2023-02-16 04:30:05,317 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-02-16 04:30:05,317 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-02-16 04:30:05,317 INFO L513 LassoAnalysis]: Proved termination. [2023-02-16 04:30:05,317 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec2_#in~j) = 1*rec2_#in~j Supporting invariants [] [2023-02-16 04:30:05,321 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2023-02-16 04:30:05,323 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-02-16 04:30:05,350 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:05,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:05,375 INFO L263 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjunts are in the unsatisfiable core [2023-02-16 04:30:05,376 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:05,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:05,445 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjunts are in the unsatisfiable core [2023-02-16 04:30:05,451 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:05,617 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-02-16 04:30:05,621 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 [2023-02-16 04:30:05,623 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) [2023-02-16 04:30:05,830 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 [2023-02-16 04:30:05,977 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. [2023-02-16 04:30:05,978 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 [2023-02-16 04:30:05,979 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) [2023-02-16 04:30:05,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 37 transitions. [2023-02-16 04:30:05,983 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 24 letters. [2023-02-16 04:30:05,987 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:05,988 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 27 letters. Loop has 24 letters. [2023-02-16 04:30:05,988 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:05,988 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 37 transitions. Stem has 3 letters. Loop has 48 letters. [2023-02-16 04:30:05,989 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:05,989 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 102 states and 148 transitions. [2023-02-16 04:30:05,998 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:06,006 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 102 states to 90 states and 136 transitions. [2023-02-16 04:30:06,007 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 39 [2023-02-16 04:30:06,008 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2023-02-16 04:30:06,008 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 136 transitions. [2023-02-16 04:30:06,009 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:06,009 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 136 transitions. [2023-02-16 04:30:06,009 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 136 transitions. [2023-02-16 04:30:06,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 63. [2023-02-16 04:30:06,028 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) [2023-02-16 04:30:06,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 99 transitions. [2023-02-16 04:30:06,029 INFO L240 hiAutomatonCegarLoop]: Abstraction has 63 states and 99 transitions. [2023-02-16 04:30:06,029 INFO L428 stractBuchiCegarLoop]: Abstraction has 63 states and 99 transitions. [2023-02-16 04:30:06,029 INFO L335 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2023-02-16 04:30:06,030 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 63 states and 99 transitions. [2023-02-16 04:30:06,031 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:06,031 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:06,031 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:06,031 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:06,031 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2023-02-16 04:30:06,032 INFO L748 eck$LassoCheckResult]: Stem: 385#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 378#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;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 346#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 355#$Ultimate##0 ~j := #in~j; 356#L18 assume !(~j <= 0); 350#L20 call #t~ret3 := rec1(~j);< 349#$Ultimate##0 ~i := #in~i; 351#L12 assume !(~i <= 0); 360#L14 call #t~ret0 := rec1(~i - 2);< 376#$Ultimate##0 [2023-02-16 04:30:06,032 INFO L750 eck$LassoCheckResult]: Loop: 376#$Ultimate##0 ~i := #in~i; 393#L12 assume !(~i <= 0); 359#L14 call #t~ret0 := rec1(~i - 2);< 376#$Ultimate##0 [2023-02-16 04:30:06,032 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,032 INFO L85 PathProgramCache]: Analyzing trace with hash 838970620, now seen corresponding path program 1 times [2023-02-16 04:30:06,032 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:06,033 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1122320724] [2023-02-16 04:30:06,033 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:06,033 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:06,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,038 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:06,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,042 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:06,043 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,043 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2023-02-16 04:30:06,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:06,043 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1186753043] [2023-02-16 04:30:06,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:06,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:06,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,047 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:06,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,049 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:06,050 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,050 INFO L85 PathProgramCache]: Analyzing trace with hash 1359045147, now seen corresponding path program 2 times [2023-02-16 04:30:06,050 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:06,050 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1149394603] [2023-02-16 04:30:06,050 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:06,050 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:06,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,056 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:06,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,061 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:06,089 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:06,089 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:06,089 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:06,089 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:06,090 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-02-16 04:30:06,090 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,090 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:06,090 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:06,090 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2023-02-16 04:30:06,090 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:06,090 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:06,092 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,094 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,096 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,098 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,102 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,108 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,134 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:06,134 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-02-16 04:30:06,135 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,136 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) [2023-02-16 04:30:06,140 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 [2023-02-16 04:30:06,141 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:06,142 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:06,163 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:06,163 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:06,170 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 [2023-02-16 04:30:06,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,171 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,172 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) [2023-02-16 04:30:06,175 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 [2023-02-16 04:30:06,176 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:06,176 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:06,197 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:06,197 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:06,200 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 [2023-02-16 04:30:06,201 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,202 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) [2023-02-16 04:30:06,204 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 [2023-02-16 04:30:06,206 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:06,206 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:06,213 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:06,214 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:06,219 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 [2023-02-16 04:30:06,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,220 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,220 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) [2023-02-16 04:30:06,222 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 [2023-02-16 04:30:06,224 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:06,224 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:06,231 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:06,231 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:06,237 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:06,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,237 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,238 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) [2023-02-16 04:30:06,241 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 [2023-02-16 04:30:06,242 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:06,243 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:06,252 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 [2023-02-16 04:30:06,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,253 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) [2023-02-16 04:30:06,255 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 [2023-02-16 04:30:06,258 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-02-16 04:30:06,258 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:06,283 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-02-16 04:30:06,287 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:06,287 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:06,287 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:06,287 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:06,287 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:06,287 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-02-16 04:30:06,287 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,287 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:06,287 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:06,287 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration3_Loop [2023-02-16 04:30:06,287 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:06,287 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:06,288 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,292 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,299 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,302 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,308 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,314 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,345 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:06,345 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-02-16 04:30:06,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,347 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) [2023-02-16 04:30:06,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 [2023-02-16 04:30:06,371 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:06,371 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:06,371 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:06,371 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:06,371 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:06,372 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:06,372 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:06,374 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 [2023-02-16 04:30:06,389 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:06,405 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 [2023-02-16 04:30:06,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,407 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) [2023-02-16 04:30:06,437 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 [2023-02-16 04:30:06,550 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 [2023-02-16 04:30:06,563 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:06,563 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:06,563 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:06,563 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:06,563 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:06,564 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:06,564 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:06,569 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:06,572 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:06,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,574 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) [2023-02-16 04:30:06,577 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 [2023-02-16 04:30:06,578 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 [2023-02-16 04:30:06,584 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:06,585 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:06,585 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:06,585 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:06,585 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:06,586 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:06,586 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:06,587 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:06,593 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 [2023-02-16 04:30:06,594 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,594 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,595 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) [2023-02-16 04:30:06,597 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 [2023-02-16 04:30:06,600 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 [2023-02-16 04:30:06,606 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:06,606 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:06,607 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:06,607 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:06,607 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:06,607 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:06,607 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:06,608 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:06,614 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 [2023-02-16 04:30:06,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,614 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,615 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) [2023-02-16 04:30:06,618 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 [2023-02-16 04:30:06,619 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 [2023-02-16 04:30:06,626 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:06,626 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:06,626 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:06,626 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:06,626 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:06,627 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:06,627 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:06,631 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-02-16 04:30:06,634 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2023-02-16 04:30:06,634 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2023-02-16 04:30:06,634 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,642 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) [2023-02-16 04:30:06,644 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 [2023-02-16 04:30:06,646 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-02-16 04:30:06,646 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-02-16 04:30:06,646 INFO L513 LassoAnalysis]: Proved termination. [2023-02-16 04:30:06,646 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2023-02-16 04:30:06,657 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:06,658 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-02-16 04:30:06,679 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:06,711 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjunts are in the unsatisfiable core [2023-02-16 04:30:06,712 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:06,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:06,738 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:06,739 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:06,761 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:06,762 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 [2023-02-16 04:30:06,762 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) [2023-02-16 04:30:06,805 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 13 states. [2023-02-16 04:30:06,806 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 1 stem states 2 non-accepting loop states 1 accepting loop states [2023-02-16 04:30:06,807 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) [2023-02-16 04:30:06,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 14 transitions. [2023-02-16 04:30:06,808 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 14 transitions. Stem has 9 letters. Loop has 3 letters. [2023-02-16 04:30:06,808 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:06,808 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 14 transitions. Stem has 12 letters. Loop has 3 letters. [2023-02-16 04:30:06,808 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:06,808 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 14 transitions. Stem has 9 letters. Loop has 6 letters. [2023-02-16 04:30:06,808 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:06,809 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 109 states and 166 transitions. [2023-02-16 04:30:06,811 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:06,814 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 109 states to 97 states and 154 transitions. [2023-02-16 04:30:06,814 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2023-02-16 04:30:06,814 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2023-02-16 04:30:06,815 INFO L73 IsDeterministic]: Start isDeterministic. Operand 97 states and 154 transitions. [2023-02-16 04:30:06,815 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:06,816 INFO L218 hiAutomatonCegarLoop]: Abstraction has 97 states and 154 transitions. [2023-02-16 04:30:06,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states and 154 transitions. [2023-02-16 04:30:06,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 93. [2023-02-16 04:30:06,823 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) [2023-02-16 04:30:06,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 144 transitions. [2023-02-16 04:30:06,825 INFO L240 hiAutomatonCegarLoop]: Abstraction has 93 states and 144 transitions. [2023-02-16 04:30:06,825 INFO L428 stractBuchiCegarLoop]: Abstraction has 93 states and 144 transitions. [2023-02-16 04:30:06,825 INFO L335 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2023-02-16 04:30:06,825 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 93 states and 144 transitions. [2023-02-16 04:30:06,826 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:06,827 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:06,827 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:06,827 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:06,827 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2023-02-16 04:30:06,828 INFO L748 eck$LassoCheckResult]: Stem: 633#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 623#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;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 585#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 602#$Ultimate##0 ~j := #in~j; 603#L18 assume !(~j <= 0); 628#L20 call #t~ret3 := rec1(~j);< 632#$Ultimate##0 ~i := #in~i; 650#L12 assume !(~i <= 0); 608#L14 call #t~ret0 := rec1(~i - 2);< 648#$Ultimate##0 ~i := #in~i; 653#L12 assume ~i <= 0;#res := 0; 652#rec1FINAL assume true; 647#rec1EXIT >#28#return; 595#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 589#$Ultimate##0 [2023-02-16 04:30:06,828 INFO L750 eck$LassoCheckResult]: Loop: 589#$Ultimate##0 ~i := #in~i; 597#L12 assume !(~i <= 0); 591#L14 call #t~ret0 := rec1(~i - 2);< 589#$Ultimate##0 [2023-02-16 04:30:06,828 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,828 INFO L85 PathProgramCache]: Analyzing trace with hash 372282091, now seen corresponding path program 1 times [2023-02-16 04:30:06,829 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:06,829 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [590473959] [2023-02-16 04:30:06,829 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:06,829 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:06,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,834 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:06,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,839 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:06,840 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,840 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2023-02-16 04:30:06,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:06,840 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1958465535] [2023-02-16 04:30:06,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:06,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:06,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,843 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:06,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:06,846 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:06,846 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:06,846 INFO L85 PathProgramCache]: Analyzing trace with hash 1050214860, now seen corresponding path program 2 times [2023-02-16 04:30:06,846 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:06,847 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1362500073] [2023-02-16 04:30:06,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:06,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:06,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:06,901 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2023-02-16 04:30:06,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:06,921 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-02-16 04:30:06,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 04:30:06,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1362500073] [2023-02-16 04:30:06,922 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1362500073] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 04:30:06,922 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 04:30:06,922 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-02-16 04:30:06,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [834409330] [2023-02-16 04:30:06,923 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 04:30:06,945 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:06,945 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:06,945 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:06,945 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:06,946 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-02-16 04:30:06,946 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,946 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:06,946 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:06,946 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2023-02-16 04:30:06,946 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:06,946 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:06,947 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,949 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,953 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,955 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,957 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,959 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:06,982 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:06,982 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-02-16 04:30:06,983 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:06,983 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:06,984 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) [2023-02-16 04:30:06,993 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:06,994 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:07,002 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 [2023-02-16 04:30:07,010 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:07,011 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:07,017 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 [2023-02-16 04:30:07,018 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:07,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,019 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) [2023-02-16 04:30:07,022 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 [2023-02-16 04:30:07,023 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:07,023 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:07,050 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 [2023-02-16 04:30:07,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:07,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,052 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) [2023-02-16 04:30:07,054 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 [2023-02-16 04:30:07,056 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-02-16 04:30:07,056 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:07,102 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-02-16 04:30:07,106 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 [2023-02-16 04:30:07,106 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:07,106 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:07,106 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:07,106 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:07,106 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-02-16 04:30:07,106 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:07,106 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:07,106 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:07,107 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration4_Loop [2023-02-16 04:30:07,107 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:07,107 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:07,107 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:07,110 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:07,114 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:07,116 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:07,126 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:07,127 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:07,157 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:07,157 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-02-16 04:30:07,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:07,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,159 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) [2023-02-16 04:30:07,168 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 [2023-02-16 04:30:07,169 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 [2023-02-16 04:30:07,175 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:07,175 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:07,175 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:07,175 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:07,175 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:07,176 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:07,176 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:07,177 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:07,181 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 [2023-02-16 04:30:07,182 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:07,182 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,183 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) [2023-02-16 04:30:07,185 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 [2023-02-16 04:30:07,187 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 [2023-02-16 04:30:07,193 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:07,193 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:07,193 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:07,193 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:07,193 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:07,194 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:07,194 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:07,216 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-02-16 04:30:07,229 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2023-02-16 04:30:07,229 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2023-02-16 04:30:07,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:07,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,241 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) [2023-02-16 04:30:07,242 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-02-16 04:30:07,242 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-02-16 04:30:07,242 INFO L513 LassoAnalysis]: Proved termination. [2023-02-16 04:30:07,242 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2023-02-16 04:30:07,245 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 [2023-02-16 04:30:07,248 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 [2023-02-16 04:30:07,249 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-02-16 04:30:07,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:07,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,284 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjunts are in the unsatisfiable core [2023-02-16 04:30:07,286 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:07,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,360 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:07,360 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:07,383 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:07,384 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 [2023-02-16 04:30:07,384 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) [2023-02-16 04:30:07,451 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 [2023-02-16 04:30:07,454 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 [2023-02-16 04:30:07,476 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 14 states. [2023-02-16 04:30:07,476 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 [2023-02-16 04:30:07,477 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) [2023-02-16 04:30:07,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 18 transitions. [2023-02-16 04:30:07,478 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 18 transitions. Stem has 14 letters. Loop has 3 letters. [2023-02-16 04:30:07,478 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:07,478 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 18 transitions. Stem has 17 letters. Loop has 3 letters. [2023-02-16 04:30:07,478 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:07,478 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 18 transitions. Stem has 14 letters. Loop has 6 letters. [2023-02-16 04:30:07,478 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:07,478 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 133 states and 208 transitions. [2023-02-16 04:30:07,481 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:07,484 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 133 states to 121 states and 196 transitions. [2023-02-16 04:30:07,484 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 50 [2023-02-16 04:30:07,485 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 52 [2023-02-16 04:30:07,485 INFO L73 IsDeterministic]: Start isDeterministic. Operand 121 states and 196 transitions. [2023-02-16 04:30:07,485 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:07,485 INFO L218 hiAutomatonCegarLoop]: Abstraction has 121 states and 196 transitions. [2023-02-16 04:30:07,485 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states and 196 transitions. [2023-02-16 04:30:07,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2023-02-16 04:30:07,494 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) [2023-02-16 04:30:07,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 186 transitions. [2023-02-16 04:30:07,496 INFO L240 hiAutomatonCegarLoop]: Abstraction has 117 states and 186 transitions. [2023-02-16 04:30:07,496 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 04:30:07,497 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-02-16 04:30:07,497 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-02-16 04:30:07,497 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) [2023-02-16 04:30:07,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 04:30:07,554 INFO L93 Difference]: Finished difference Result 130 states and 196 transitions. [2023-02-16 04:30:07,555 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 196 transitions. [2023-02-16 04:30:07,563 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2023-02-16 04:30:07,574 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 128 states and 194 transitions. [2023-02-16 04:30:07,575 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2023-02-16 04:30:07,576 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2023-02-16 04:30:07,577 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 194 transitions. [2023-02-16 04:30:07,577 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:07,577 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 194 transitions. [2023-02-16 04:30:07,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 194 transitions. [2023-02-16 04:30:07,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 105. [2023-02-16 04:30:07,597 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) [2023-02-16 04:30:07,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2023-02-16 04:30:07,602 INFO L240 hiAutomatonCegarLoop]: Abstraction has 105 states and 158 transitions. [2023-02-16 04:30:07,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-02-16 04:30:07,603 INFO L428 stractBuchiCegarLoop]: Abstraction has 105 states and 158 transitions. [2023-02-16 04:30:07,604 INFO L335 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2023-02-16 04:30:07,604 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 105 states and 158 transitions. [2023-02-16 04:30:07,606 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2023-02-16 04:30:07,607 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:07,607 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:07,607 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:07,608 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [3, 2, 2, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:07,608 INFO L748 eck$LassoCheckResult]: Stem: 1209#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1197#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;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 1157#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1194#$Ultimate##0 ~j := #in~j; 1225#L18 assume !(~j <= 0); 1217#L20 call #t~ret3 := rec1(~j);< 1224#$Ultimate##0 ~i := #in~i; 1223#L12 assume !(~i <= 0); 1178#L14 call #t~ret0 := rec1(~i - 2);< 1221#$Ultimate##0 ~i := #in~i; 1220#L12 assume !(~i <= 0); 1174#L14 call #t~ret0 := rec1(~i - 2);< 1219#$Ultimate##0 ~i := #in~i; 1206#L12 assume ~i <= 0;#res := 0; 1198#rec1FINAL assume true; 1199#rec1EXIT >#28#return; 1162#L14-1 [2023-02-16 04:30:07,609 INFO L750 eck$LassoCheckResult]: Loop: 1162#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1161#$Ultimate##0 ~i := #in~i; 1164#L12 assume ~i <= 0;#res := 0; 1253#rec1FINAL assume true; 1248#rec1EXIT >#30#return; 1175#L14-2 call #t~ret2 := rec1(#t~ret1);< 1195#$Ultimate##0 ~i := #in~i; 1251#L12 assume !(~i <= 0); 1177#L14 call #t~ret0 := rec1(~i - 2);< 1195#$Ultimate##0 ~i := #in~i; 1251#L12 assume ~i <= 0;#res := 0; 1250#rec1FINAL assume true; 1249#rec1EXIT >#28#return; 1162#L14-1 [2023-02-16 04:30:07,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:07,609 INFO L85 PathProgramCache]: Analyzing trace with hash 1325197585, now seen corresponding path program 1 times [2023-02-16 04:30:07,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:07,610 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [942249596] [2023-02-16 04:30:07,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:07,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:07,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:07,617 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:07,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:07,621 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:07,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:07,628 INFO L85 PathProgramCache]: Analyzing trace with hash 949089090, now seen corresponding path program 1 times [2023-02-16 04:30:07,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:07,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1423077555] [2023-02-16 04:30:07,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:07,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:07,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,664 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2023-02-16 04:30:07,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,677 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2023-02-16 04:30:07,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,681 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-02-16 04:30:07,682 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 04:30:07,682 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1423077555] [2023-02-16 04:30:07,682 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1423077555] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 04:30:07,682 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1807863982] [2023-02-16 04:30:07,682 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:07,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 04:30:07,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,684 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) [2023-02-16 04:30:07,686 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Waiting until timeout for monitored process [2023-02-16 04:30:07,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,710 INFO L263 TraceCheckSpWp]: Trace formula consists of 33 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-16 04:30:07,710 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:07,720 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:07,720 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 04:30:07,721 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1807863982] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 04:30:07,721 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-16 04:30:07,721 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2023-02-16 04:30:07,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1061566612] [2023-02-16 04:30:07,721 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 04:30:07,722 INFO L765 eck$LassoCheckResult]: loop already infeasible [2023-02-16 04:30:07,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 04:30:07,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-02-16 04:30:07,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-02-16 04:30:07,723 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) [2023-02-16 04:30:07,778 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 04:30:07,778 INFO L93 Difference]: Finished difference Result 120 states and 174 transitions. [2023-02-16 04:30:07,778 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 120 states and 174 transitions. [2023-02-16 04:30:07,782 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:07,783 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 120 states to 115 states and 165 transitions. [2023-02-16 04:30:07,783 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2023-02-16 04:30:07,783 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 51 [2023-02-16 04:30:07,784 INFO L73 IsDeterministic]: Start isDeterministic. Operand 115 states and 165 transitions. [2023-02-16 04:30:07,784 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:07,784 INFO L218 hiAutomatonCegarLoop]: Abstraction has 115 states and 165 transitions. [2023-02-16 04:30:07,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states and 165 transitions. [2023-02-16 04:30:07,791 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 112. [2023-02-16 04:30:07,791 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) [2023-02-16 04:30:07,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 162 transitions. [2023-02-16 04:30:07,793 INFO L240 hiAutomatonCegarLoop]: Abstraction has 112 states and 162 transitions. [2023-02-16 04:30:07,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-02-16 04:30:07,794 INFO L428 stractBuchiCegarLoop]: Abstraction has 112 states and 162 transitions. [2023-02-16 04:30:07,794 INFO L335 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2023-02-16 04:30:07,794 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 112 states and 162 transitions. [2023-02-16 04:30:07,795 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 9 [2023-02-16 04:30:07,795 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:07,795 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:07,796 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 04:30:07,796 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2023-02-16 04:30:07,796 INFO L748 eck$LassoCheckResult]: Stem: 1499#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 1485#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;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 1441#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 1469#$Ultimate##0 ~j := #in~j; 1510#L18 assume !(~j <= 0); 1455#L20 call #t~ret3 := rec1(~j);< 1509#$Ultimate##0 ~i := #in~i; 1508#L12 assume !(~i <= 0); 1475#L14 call #t~ret0 := rec1(~i - 2);< 1507#$Ultimate##0 ~i := #in~i; 1505#L12 assume !(~i <= 0); 1472#L14 call #t~ret0 := rec1(~i - 2);< 1504#$Ultimate##0 ~i := #in~i; 1506#L12 assume ~i <= 0;#res := 0; 1486#rec1FINAL assume true; 1487#rec1EXIT >#28#return; 1479#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1480#$Ultimate##0 ~i := #in~i; 1517#L12 assume ~i <= 0;#res := 0; 1516#rec1FINAL assume true; 1514#rec1EXIT >#30#return; 1446#L14-2 call #t~ret2 := rec1(#t~ret1);< 1445#$Ultimate##0 ~i := #in~i; 1447#L12 assume ~i <= 0;#res := 0; 1493#rec1FINAL assume true; 1490#rec1EXIT >#32#return; 1491#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 1519#rec1FINAL assume true; 1518#rec1EXIT >#28#return; 1476#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 1496#$Ultimate##0 [2023-02-16 04:30:07,796 INFO L750 eck$LassoCheckResult]: Loop: 1496#$Ultimate##0 ~i := #in~i; 1521#L12 assume !(~i <= 0); 1473#L14 call #t~ret0 := rec1(~i - 2);< 1496#$Ultimate##0 [2023-02-16 04:30:07,796 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:07,796 INFO L85 PathProgramCache]: Analyzing trace with hash 1060897207, now seen corresponding path program 1 times [2023-02-16 04:30:07,797 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:07,797 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1534196839] [2023-02-16 04:30:07,797 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:07,797 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:07,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:07,810 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:07,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:07,817 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:07,818 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:07,818 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 3 times [2023-02-16 04:30:07,818 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:07,818 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [648035393] [2023-02-16 04:30:07,819 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:07,819 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:07,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:07,821 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:07,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:07,823 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:07,824 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:07,824 INFO L85 PathProgramCache]: Analyzing trace with hash -1475637376, now seen corresponding path program 2 times [2023-02-16 04:30:07,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:07,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [810428519] [2023-02-16 04:30:07,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:07,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:07,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,873 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2023-02-16 04:30:07,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,903 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2023-02-16 04:30:07,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,906 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-02-16 04:30:07,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,909 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-02-16 04:30:07,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:07,922 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-02-16 04:30:07,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 04:30:07,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [810428519] [2023-02-16 04:30:07,922 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [810428519] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 04:30:07,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1713130426] [2023-02-16 04:30:07,922 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 04:30:07,923 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 04:30:07,923 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:07,924 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) [2023-02-16 04:30:07,954 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Waiting until timeout for monitored process [2023-02-16 04:30:07,973 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 04:30:07,974 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 04:30:07,974 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:07,976 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:08,002 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-02-16 04:30:08,002 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 04:30:08,092 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-02-16 04:30:08,092 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1713130426] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 04:30:08,092 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-02-16 04:30:08,093 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2023-02-16 04:30:08,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [658867188] [2023-02-16 04:30:08,093 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-02-16 04:30:08,116 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:08,117 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:08,117 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:08,117 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:08,117 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-02-16 04:30:08,117 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,117 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:08,117 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:08,117 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2023-02-16 04:30:08,117 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:08,118 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:08,118 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,120 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,122 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,123 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,125 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,126 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,153 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:08,153 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-02-16 04:30:08,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,155 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) [2023-02-16 04:30:08,165 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:08,165 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,174 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 [2023-02-16 04:30:08,185 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:08,185 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#res=0} Honda state: {rec1_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:08,192 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:08,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,193 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,194 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) [2023-02-16 04:30:08,197 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 [2023-02-16 04:30:08,200 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:08,200 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,217 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:08,217 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:08,220 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 [2023-02-16 04:30:08,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,222 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) [2023-02-16 04:30:08,223 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 [2023-02-16 04:30:08,225 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:08,225 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,233 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:08,233 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret2=0} Honda state: {rec1_#t~ret2=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:08,236 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2023-02-16 04:30:08,236 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,237 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) [2023-02-16 04:30:08,239 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 [2023-02-16 04:30:08,241 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:08,241 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,249 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:08,249 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_~i=0} Honda state: {rec1_~i=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:08,253 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:08,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,254 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) [2023-02-16 04:30:08,256 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 [2023-02-16 04:30:08,258 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:08,258 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,265 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:08,265 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret1=0} Honda state: {rec1_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:08,271 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 [2023-02-16 04:30:08,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,271 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,272 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) [2023-02-16 04:30:08,274 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 [2023-02-16 04:30:08,275 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:08,275 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,286 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:08,287 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,287 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,288 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) [2023-02-16 04:30:08,289 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 [2023-02-16 04:30:08,292 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-02-16 04:30:08,292 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:08,340 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-02-16 04:30:08,343 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2023-02-16 04:30:08,344 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:08,344 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:08,344 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:08,344 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:08,344 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-02-16 04:30:08,344 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,344 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:08,344 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:08,344 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration6_Loop [2023-02-16 04:30:08,344 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:08,344 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:08,345 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,347 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,349 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,351 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,352 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,354 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:08,381 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:08,382 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-02-16 04:30:08,382 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,382 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,383 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) [2023-02-16 04:30:08,393 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 [2023-02-16 04:30:08,550 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 [2023-02-16 04:30:08,557 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:08,557 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:08,557 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:08,557 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:08,557 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:08,558 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:08,558 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:08,572 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:08,575 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 [2023-02-16 04:30:08,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,577 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) [2023-02-16 04:30:08,579 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 [2023-02-16 04:30:08,582 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 [2023-02-16 04:30:08,588 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:08,588 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:08,589 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:08,589 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:08,589 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:08,589 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:08,589 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:08,592 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:08,596 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 [2023-02-16 04:30:08,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,598 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) [2023-02-16 04:30:08,599 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 [2023-02-16 04:30:08,601 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 [2023-02-16 04:30:08,607 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:08,608 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:08,608 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:08,608 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:08,608 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:08,608 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:08,608 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:08,609 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:08,612 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 [2023-02-16 04:30:08,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,614 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) [2023-02-16 04:30:08,616 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 [2023-02-16 04:30:08,618 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 [2023-02-16 04:30:08,624 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:08,624 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:08,624 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:08,624 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:08,625 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:08,625 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:08,625 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:08,626 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:08,631 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 [2023-02-16 04:30:08,632 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,632 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,633 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) [2023-02-16 04:30:08,634 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 [2023-02-16 04:30:08,636 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 [2023-02-16 04:30:08,643 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:08,643 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:08,643 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:08,643 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:08,643 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:08,644 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:08,644 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:08,645 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-02-16 04:30:08,648 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2023-02-16 04:30:08,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,650 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) [2023-02-16 04:30:08,652 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 [2023-02-16 04:30:08,653 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 [2023-02-16 04:30:08,659 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:08,659 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:08,659 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:08,659 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:08,659 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:08,660 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:08,660 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:08,662 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-02-16 04:30:08,663 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2023-02-16 04:30:08,663 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2023-02-16 04:30:08,663 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:08,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:08,667 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) [2023-02-16 04:30:08,667 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 [2023-02-16 04:30:08,668 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-02-16 04:30:08,668 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-02-16 04:30:08,668 INFO L513 LassoAnalysis]: Proved termination. [2023-02-16 04:30:08,668 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2023-02-16 04:30:08,671 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 [2023-02-16 04:30:08,672 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-02-16 04:30:08,680 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:08,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:08,733 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 04:30:08,736 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:08,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:08,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:08,938 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:08,939 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:08,955 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:08,957 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 [2023-02-16 04:30:08,958 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) [2023-02-16 04:30:09,014 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 7 states. [2023-02-16 04:30:09,015 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 2 stem states 1 non-accepting loop states 1 accepting loop states [2023-02-16 04:30:09,015 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) [2023-02-16 04:30:09,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 16 transitions. [2023-02-16 04:30:09,016 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2023-02-16 04:30:09,016 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:09,016 INFO L681 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2023-02-16 04:30:09,023 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:09,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,068 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 04:30:09,070 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:09,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,238 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:09,238 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:09,254 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:09,257 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 [2023-02-16 04:30:09,257 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) [2023-02-16 04:30:09,298 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 7 states. [2023-02-16 04:30:09,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 2 stem states 1 non-accepting loop states 1 accepting loop states [2023-02-16 04:30:09,305 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) [2023-02-16 04:30:09,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 16 transitions. [2023-02-16 04:30:09,305 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 16 transitions. Stem has 30 letters. Loop has 3 letters. [2023-02-16 04:30:09,306 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:09,306 INFO L681 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2023-02-16 04:30:09,313 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:09,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,349 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 04:30:09,351 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:09,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,506 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:09,507 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:09,524 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:09,525 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 [2023-02-16 04:30:09,525 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) [2023-02-16 04:30:09,594 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 13 states. [2023-02-16 04:30:09,595 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 [2023-02-16 04:30:09,596 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) [2023-02-16 04:30:09,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 25 transitions. [2023-02-16 04:30:09,596 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2023-02-16 04:30:09,596 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:09,596 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2023-02-16 04:30:09,596 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:09,597 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2023-02-16 04:30:09,597 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:09,597 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 157 states and 219 transitions. [2023-02-16 04:30:09,599 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2023-02-16 04:30:09,601 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 157 states to 139 states and 201 transitions. [2023-02-16 04:30:09,601 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 55 [2023-02-16 04:30:09,601 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 58 [2023-02-16 04:30:09,602 INFO L73 IsDeterministic]: Start isDeterministic. Operand 139 states and 201 transitions. [2023-02-16 04:30:09,602 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:09,602 INFO L218 hiAutomatonCegarLoop]: Abstraction has 139 states and 201 transitions. [2023-02-16 04:30:09,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states and 201 transitions. [2023-02-16 04:30:09,609 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 120. [2023-02-16 04:30:09,609 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) [2023-02-16 04:30:09,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 170 transitions. [2023-02-16 04:30:09,611 INFO L240 hiAutomatonCegarLoop]: Abstraction has 120 states and 170 transitions. [2023-02-16 04:30:09,611 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 04:30:09,611 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-02-16 04:30:09,611 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2023-02-16 04:30:09,611 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) [2023-02-16 04:30:09,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 04:30:09,665 INFO L93 Difference]: Finished difference Result 98 states and 116 transitions. [2023-02-16 04:30:09,665 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 98 states and 116 transitions. [2023-02-16 04:30:09,666 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2023-02-16 04:30:09,666 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 98 states to 63 states and 75 transitions. [2023-02-16 04:30:09,666 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2023-02-16 04:30:09,667 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 12 [2023-02-16 04:30:09,667 INFO L73 IsDeterministic]: Start isDeterministic. Operand 63 states and 75 transitions. [2023-02-16 04:30:09,667 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-02-16 04:30:09,667 INFO L218 hiAutomatonCegarLoop]: Abstraction has 63 states and 75 transitions. [2023-02-16 04:30:09,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states and 75 transitions. [2023-02-16 04:30:09,674 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2023-02-16 04:30:09,675 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) [2023-02-16 04:30:09,675 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2023-02-16 04:30:09,675 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 65 transitions. [2023-02-16 04:30:09,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-02-16 04:30:09,676 INFO L428 stractBuchiCegarLoop]: Abstraction has 54 states and 65 transitions. [2023-02-16 04:30:09,676 INFO L335 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2023-02-16 04:30:09,677 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 65 transitions. [2023-02-16 04:30:09,677 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2023-02-16 04:30:09,677 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-02-16 04:30:09,677 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-02-16 04:30:09,678 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] [2023-02-16 04:30:09,678 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2023-02-16 04:30:09,678 INFO L748 eck$LassoCheckResult]: Stem: 2809#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 2803#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;main_~x~0#1 := main_#t~nondet5#1;havoc main_#t~nondet5#1; 2779#L25 call main_#t~ret6#1 := rec2(main_~x~0#1);< 2788#$Ultimate##0 ~j := #in~j; 2789#L18 assume !(~j <= 0); 2801#L20 call #t~ret3 := rec1(~j);< 2827#$Ultimate##0 ~i := #in~i; 2824#L12 assume !(~i <= 0); 2796#L14 call #t~ret0 := rec1(~i - 2);< 2826#$Ultimate##0 ~i := #in~i; 2831#L12 assume ~i <= 0;#res := 0; 2830#rec1FINAL assume true; 2805#rec1EXIT >#28#return; 2800#L14-1 call #t~ret1 := rec1(#t~ret0 - 1);< 2802#$Ultimate##0 ~i := #in~i; 2823#L12 assume ~i <= 0;#res := 0; 2822#rec1FINAL assume true; 2816#rec1EXIT >#30#return; 2814#L14-2 call #t~ret2 := rec1(#t~ret1);< 2799#$Ultimate##0 ~i := #in~i; 2818#L12 assume ~i <= 0;#res := 0; 2815#rec1FINAL assume true; 2813#rec1EXIT >#32#return; 2812#L14-3 #res := 1 + #t~ret2;havoc #t~ret0;havoc #t~ret1;havoc #t~ret2; 2811#rec1FINAL assume true; 2810#rec1EXIT >#34#return; 2778#L20-1 call #t~ret4 := rec2(#t~ret3 - 1);< 2780#$Ultimate##0 ~j := #in~j; 2791#L18 assume !(~j <= 0); 2784#L20 call #t~ret3 := rec1(~j);< 2781#$Ultimate##0 [2023-02-16 04:30:09,679 INFO L750 eck$LassoCheckResult]: Loop: 2781#$Ultimate##0 ~i := #in~i; 2783#L12 assume !(~i <= 0); 2782#L14 call #t~ret0 := rec1(~i - 2);< 2781#$Ultimate##0 [2023-02-16 04:30:09,679 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:09,679 INFO L85 PathProgramCache]: Analyzing trace with hash 1256061253, now seen corresponding path program 2 times [2023-02-16 04:30:09,679 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:09,679 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [651237653] [2023-02-16 04:30:09,679 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:09,679 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:09,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,729 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-02-16 04:30:09,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,764 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2023-02-16 04:30:09,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,767 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-02-16 04:30:09,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,769 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-02-16 04:30:09,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:09,780 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-02-16 04:30:09,780 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 04:30:09,780 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [651237653] [2023-02-16 04:30:09,780 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [651237653] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 04:30:09,780 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1061281607] [2023-02-16 04:30:09,780 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 04:30:09,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 04:30:09,781 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:09,782 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) [2023-02-16 04:30:09,784 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Waiting until timeout for monitored process [2023-02-16 04:30:09,813 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 04:30:09,813 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 04:30:09,814 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:09,815 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:09,827 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-02-16 04:30:09,828 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 04:30:09,909 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-02-16 04:30:09,909 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1061281607] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 04:30:09,909 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-02-16 04:30:09,909 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 8 [2023-02-16 04:30:09,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [327450822] [2023-02-16 04:30:09,909 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-02-16 04:30:09,910 INFO L753 eck$LassoCheckResult]: stem already infeasible [2023-02-16 04:30:09,910 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:09,910 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 4 times [2023-02-16 04:30:09,910 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 04:30:09,910 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1489285942] [2023-02-16 04:30:09,910 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 04:30:09,911 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 04:30:09,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:09,913 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-02-16 04:30:09,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-02-16 04:30:09,914 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-02-16 04:30:09,933 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:09,933 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:09,933 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:09,933 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:09,933 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-02-16 04:30:09,933 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:09,933 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:09,933 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:09,934 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2023-02-16 04:30:09,934 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:09,934 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:09,934 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:09,937 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:09,942 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:09,944 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:09,945 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:09,947 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:09,967 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:09,967 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-02-16 04:30:09,967 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:09,967 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:09,969 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) [2023-02-16 04:30:09,977 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:09,977 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:09,986 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 [2023-02-16 04:30:09,999 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-02-16 04:30:09,999 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {rec1_#t~ret0=0} Honda state: {rec1_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-02-16 04:30:10,002 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Ended with exit code 0 [2023-02-16 04:30:10,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:10,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:10,003 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) [2023-02-16 04:30:10,005 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 [2023-02-16 04:30:10,007 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-02-16 04:30:10,007 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:10,016 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 [2023-02-16 04:30:10,016 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:10,016 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:10,017 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) [2023-02-16 04:30:10,019 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 [2023-02-16 04:30:10,021 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-02-16 04:30:10,021 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-02-16 04:30:10,035 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-02-16 04:30:10,039 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 [2023-02-16 04:30:10,039 INFO L210 LassoAnalysis]: Preferences: [2023-02-16 04:30:10,039 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-02-16 04:30:10,039 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-02-16 04:30:10,039 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-02-16 04:30:10,039 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-02-16 04:30:10,039 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:10,039 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-02-16 04:30:10,040 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-02-16 04:30:10,040 INFO L133 ssoRankerPreferences]: Filename of dumped script: NestedRecursion_1d.c_Iteration7_Loop [2023-02-16 04:30:10,040 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-02-16 04:30:10,040 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-02-16 04:30:10,040 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:10,049 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:10,052 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:10,054 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:10,056 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:10,058 INFO L117 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-02-16 04:30:10,079 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-02-16 04:30:10,079 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-02-16 04:30:10,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:10,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:10,080 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) [2023-02-16 04:30:10,082 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 [2023-02-16 04:30:10,083 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 [2023-02-16 04:30:10,090 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-02-16 04:30:10,090 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-02-16 04:30:10,090 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-02-16 04:30:10,090 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-02-16 04:30:10,090 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-02-16 04:30:10,091 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-02-16 04:30:10,091 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-02-16 04:30:10,120 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-02-16 04:30:10,122 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2023-02-16 04:30:10,122 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2023-02-16 04:30:10,123 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-02-16 04:30:10,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 04:30:10,129 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) [2023-02-16 04:30:10,133 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 [2023-02-16 04:30:10,133 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-02-16 04:30:10,133 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-02-16 04:30:10,133 INFO L513 LassoAnalysis]: Proved termination. [2023-02-16 04:30:10,133 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(rec1_#in~i) = 1*rec1_#in~i Supporting invariants [] [2023-02-16 04:30:10,136 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (50)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:10,137 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-02-16 04:30:10,152 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:10,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:10,189 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 04:30:10,191 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:10,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:10,384 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:10,385 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:10,400 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:10,401 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 [2023-02-16 04:30:10,401 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) [2023-02-16 04:30:10,454 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 13 states. [2023-02-16 04:30:10,455 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 [2023-02-16 04:30:10,455 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) [2023-02-16 04:30:10,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 11 transitions. [2023-02-16 04:30:10,456 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2023-02-16 04:30:10,456 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:10,456 INFO L681 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2023-02-16 04:30:10,465 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:10,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:10,500 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 04:30:10,501 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:10,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:10,658 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:10,659 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:10,675 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:10,676 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 [2023-02-16 04:30:10,676 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) [2023-02-16 04:30:10,719 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 13 states. [2023-02-16 04:30:10,725 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 [2023-02-16 04:30:10,727 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) [2023-02-16 04:30:10,727 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 11 transitions. [2023-02-16 04:30:10,727 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 11 transitions. Stem has 30 letters. Loop has 3 letters. [2023-02-16 04:30:10,728 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:10,728 INFO L681 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2023-02-16 04:30:10,736 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 04:30:10,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:10,771 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 04:30:10,773 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:10,839 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 [2023-02-16 04:30:10,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 04:30:10,918 INFO L263 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 04:30:10,919 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 04:30:10,934 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-16 04:30:10,935 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 [2023-02-16 04:30:10,935 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) [2023-02-16 04:30:10,997 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 13 states. [2023-02-16 04:30:10,998 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 [2023-02-16 04:30:10,999 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) [2023-02-16 04:30:11,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 25 transitions. [2023-02-16 04:30:11,000 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 25 transitions. Stem has 30 letters. Loop has 3 letters. [2023-02-16 04:30:11,000 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:11,000 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 25 transitions. Stem has 33 letters. Loop has 3 letters. [2023-02-16 04:30:11,002 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:11,002 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 25 transitions. Stem has 30 letters. Loop has 6 letters. [2023-02-16 04:30:11,003 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-02-16 04:30:11,003 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 78 states and 90 transitions. [2023-02-16 04:30:11,004 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2023-02-16 04:30:11,004 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 78 states to 0 states and 0 transitions. [2023-02-16 04:30:11,004 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2023-02-16 04:30:11,004 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2023-02-16 04:30:11,005 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2023-02-16 04:30:11,005 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-02-16 04:30:11,005 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-02-16 04:30:11,005 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-02-16 04:30:11,005 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 04:30:11,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-02-16 04:30:11,006 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2023-02-16 04:30:11,006 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) [2023-02-16 04:30:11,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 04:30:11,006 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2023-02-16 04:30:11,006 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2023-02-16 04:30:11,006 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2023-02-16 04:30:11,006 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2023-02-16 04:30:11,007 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2023-02-16 04:30:11,007 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2023-02-16 04:30:11,007 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2023-02-16 04:30:11,007 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-02-16 04:30:11,007 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-02-16 04:30:11,007 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-02-16 04:30:11,007 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-16 04:30:11,008 INFO L428 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-02-16 04:30:11,008 INFO L335 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2023-02-16 04:30:11,008 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2023-02-16 04:30:11,008 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2023-02-16 04:30:11,008 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2023-02-16 04:30:11,016 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 16.02 04:30:11 BoogieIcfgContainer [2023-02-16 04:30:11,016 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2023-02-16 04:30:11,017 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-02-16 04:30:11,017 INFO L271 PluginConnector]: Initializing Witness Printer... [2023-02-16 04:30:11,017 INFO L275 PluginConnector]: Witness Printer initialized [2023-02-16 04:30:11,017 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 04:30:03" (3/4) ... [2023-02-16 04:30:11,020 INFO L140 WitnessPrinter]: No result that supports witness generation found [2023-02-16 04:30:11,020 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-02-16 04:30:11,020 INFO L158 Benchmark]: Toolchain (without parser) took 7974.61ms. Allocated memory was 138.4MB in the beginning and 174.1MB in the end (delta: 35.7MB). Free memory was 92.9MB in the beginning and 120.8MB in the end (delta: -28.0MB). Peak memory consumption was 9.2MB. Max. memory is 16.1GB. [2023-02-16 04:30:11,021 INFO L158 Benchmark]: CDTParser took 0.20ms. Allocated memory is still 138.4MB. Free memory is still 103.5MB. There was no memory consumed. Max. memory is 16.1GB. [2023-02-16 04:30:11,021 INFO L158 Benchmark]: CACSL2BoogieTranslator took 173.02ms. Allocated memory is still 138.4MB. Free memory was 92.4MB in the beginning and 83.6MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2023-02-16 04:30:11,022 INFO L158 Benchmark]: Boogie Procedure Inliner took 24.50ms. Allocated memory is still 138.4MB. Free memory was 83.6MB in the beginning and 81.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-02-16 04:30:11,023 INFO L158 Benchmark]: Boogie Preprocessor took 11.53ms. Allocated memory is still 138.4MB. Free memory was 81.9MB in the beginning and 81.0MB in the end (delta: 918.7kB). There was no memory consumed. Max. memory is 16.1GB. [2023-02-16 04:30:11,023 INFO L158 Benchmark]: RCFGBuilder took 200.16ms. Allocated memory is still 138.4MB. Free memory was 81.0MB in the beginning and 72.4MB in the end (delta: 8.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2023-02-16 04:30:11,024 INFO L158 Benchmark]: BuchiAutomizer took 7554.69ms. Allocated memory was 138.4MB in the beginning and 174.1MB in the end (delta: 35.7MB). Free memory was 71.9MB in the beginning and 120.8MB in the end (delta: -48.9MB). There was no memory consumed. Max. memory is 16.1GB. [2023-02-16 04:30:11,024 INFO L158 Benchmark]: Witness Printer took 3.35ms. Allocated memory is still 174.1MB. Free memory is still 120.8MB. There was no memory consumed. Max. memory is 16.1GB. [2023-02-16 04:30:11,025 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.20ms. Allocated memory is still 138.4MB. Free memory is still 103.5MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 173.02ms. Allocated memory is still 138.4MB. Free memory was 92.4MB in the beginning and 83.6MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 24.50ms. Allocated memory is still 138.4MB. Free memory was 83.6MB in the beginning and 81.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 11.53ms. Allocated memory is still 138.4MB. Free memory was 81.9MB in the beginning and 81.0MB in the end (delta: 918.7kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 200.16ms. Allocated memory is still 138.4MB. Free memory was 81.0MB in the beginning and 72.4MB in the end (delta: 8.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 7554.69ms. Allocated memory was 138.4MB in the beginning and 174.1MB in the end (delta: 35.7MB). Free memory was 71.9MB in the beginning and 120.8MB in the end (delta: -48.9MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.35ms. Allocated memory is still 174.1MB. Free memory is still 120.8MB. 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 4 locations. One deterministic module has affine ranking function \old(i) and consists of 5 locations. One nondeterministic module has affine ranking function \old(i) and consists of 5 locations. One nondeterministic module has affine ranking function \old(i) and consists of 5 locations. 5 modules have a trivial ranking function, the largest among these consists of 8 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 7.5s and 8 iterations. TraceHistogramMax:5. Analysis of lassos took 4.0s. Construction of modules took 0.3s. Büchi inclusion checks took 2.9s. 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, 221 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 198 mSDsluCounter, 504 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 305 mSDsCounter, 133 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 353 IncrementalHoareTripleChecker+Invalid, 486 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 133 mSolverCounterUnsat, 199 mSDtfsCounter, 353 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI2 SFLT2 conc0 concLT2 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital12 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq146 hnf94 smp100 dnf100 smp100 tf112 neg94 sie111 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 28ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 14 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2023-02-16 04:30:11,037 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (46)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:11,242 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:11,442 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Forceful destruction successful, exit code 0 [2023-02-16 04:30:11,643 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE