./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/McCarthy91-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive/McCarthy91-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a7241ade69e14c61e98aa837796de568ecf31fbd07f5084e15c262d93cdb3376 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 16:04:47,353 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 16:04:47,403 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-09 16:04:47,407 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 16:04:47,408 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 16:04:47,435 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 16:04:47,435 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 16:04:47,436 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 16:04:47,436 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 16:04:47,437 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 16:04:47,437 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 16:04:47,438 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 16:04:47,438 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 16:04:47,438 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 16:04:47,439 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 16:04:47,439 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 16:04:47,439 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 16:04:47,440 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 16:04:47,440 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 16:04:47,440 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 16:04:47,441 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 16:04:47,442 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 16:04:47,442 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 16:04:47,443 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 16:04:47,443 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 16:04:47,443 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 16:04:47,444 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 16:04:47,444 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 16:04:47,444 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 16:04:47,444 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 16:04:47,445 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 16:04:47,445 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 16:04:47,446 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 16:04:47,446 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 16:04:47,447 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 16:04:47,447 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 16:04:47,447 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 16:04:47,448 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 16:04:47,448 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 16:04:47,449 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> a7241ade69e14c61e98aa837796de568ecf31fbd07f5084e15c262d93cdb3376 [2024-11-09 16:04:47,783 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 16:04:47,810 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 16:04:47,813 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 16:04:47,815 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 16:04:47,815 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 16:04:47,817 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/McCarthy91-1.c [2024-11-09 16:04:49,330 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 16:04:49,520 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 16:04:49,521 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-1.c [2024-11-09 16:04:49,527 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/81ed417e1/5701859eff1346b09334eafddac9dd84/FLAG98eddd12a [2024-11-09 16:04:49,904 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/81ed417e1/5701859eff1346b09334eafddac9dd84 [2024-11-09 16:04:49,908 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 16:04:49,909 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 16:04:49,910 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 16:04:49,911 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 16:04:49,916 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 16:04:49,918 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:04:49" (1/1) ... [2024-11-09 16:04:49,921 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@325fa952 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:49, skipping insertion in model container [2024-11-09 16:04:49,921 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:04:49" (1/1) ... [2024-11-09 16:04:49,940 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 16:04:50,130 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:04:50,142 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 16:04:50,155 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:04:50,169 INFO L204 MainTranslator]: Completed translation [2024-11-09 16:04:50,169 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50 WrapperNode [2024-11-09 16:04:50,169 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 16:04:50,170 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 16:04:50,170 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 16:04:50,171 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 16:04:50,176 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,181 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,197 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2024-11-09 16:04:50,198 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 16:04:50,198 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 16:04:50,199 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 16:04:50,199 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 16:04:50,208 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,208 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,209 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,220 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 16:04:50,220 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,221 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,223 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,227 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,228 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,229 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,230 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 16:04:50,231 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 16:04:50,231 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 16:04:50,231 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 16:04:50,232 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:50,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:50,262 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:50,267 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-09 16:04:50,306 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 16:04:50,306 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 16:04:50,306 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 16:04:50,306 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 16:04:50,306 INFO L130 BoogieDeclarations]: Found specification of procedure f91 [2024-11-09 16:04:50,307 INFO L138 BoogieDeclarations]: Found implementation of procedure f91 [2024-11-09 16:04:50,359 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 16:04:50,362 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 16:04:50,463 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 16:04:50,463 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 16:04:50,488 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 16:04:50,489 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 16:04:50,489 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:04:50 BoogieIcfgContainer [2024-11-09 16:04:50,489 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 16:04:50,490 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 16:04:50,494 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 16:04:50,501 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 16:04:50,502 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:50,503 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 04:04:49" (1/3) ... [2024-11-09 16:04:50,504 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@52edadb7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:04:50, skipping insertion in model container [2024-11-09 16:04:50,504 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:50,504 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50" (2/3) ... [2024-11-09 16:04:50,504 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@52edadb7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 04:04:50, skipping insertion in model container [2024-11-09 16:04:50,505 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:50,505 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:04:50" (3/3) ... [2024-11-09 16:04:50,506 INFO L332 chiAutomizerObserver]: Analyzing ICFG McCarthy91-1.c [2024-11-09 16:04:50,549 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 16:04:50,549 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 16:04:50,549 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 16:04:50,549 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 16:04:50,549 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 16:04:50,550 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 16:04:50,550 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 16:04:50,550 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 16:04:50,553 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 16:04:50,569 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:50,570 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:50,570 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:50,574 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:04:50,574 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 16:04:50,574 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 16:04:50,574 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 16:04:50,576 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:50,576 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:50,576 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:50,576 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:04:50,577 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 16:04:50,582 INFO L745 eck$LassoCheckResult]: Stem: 15#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3); 6#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 14#L28true call main_#t~ret7#1 := f91(main_~x~0#1);< 12#$Ultimate##0true [2024-11-09 16:04:50,583 INFO L747 eck$LassoCheckResult]: Loop: 12#$Ultimate##0true ~x := #in~x; 8#L18true assume !(~x > 100); 10#L21true call #t~ret4 := f91(11 + ~x);< 12#$Ultimate##0true [2024-11-09 16:04:50,588 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:50,588 INFO L85 PathProgramCache]: Analyzing trace with hash 29879, now seen corresponding path program 1 times [2024-11-09 16:04:50,596 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:50,597 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001297718] [2024-11-09 16:04:50,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:50,597 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:50,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:50,668 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:50,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:50,699 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:50,702 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:50,703 INFO L85 PathProgramCache]: Analyzing trace with hash 46807, now seen corresponding path program 1 times [2024-11-09 16:04:50,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:50,703 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1635707390] [2024-11-09 16:04:50,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:50,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:50,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:50,718 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:50,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:50,724 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:50,727 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:50,727 INFO L85 PathProgramCache]: Analyzing trace with hash 890142305, now seen corresponding path program 1 times [2024-11-09 16:04:50,727 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:50,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524270156] [2024-11-09 16:04:50,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:50,727 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:50,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:50,738 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:50,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:50,752 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:50,873 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:50,873 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:50,873 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:50,873 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:50,874 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:50,874 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:50,874 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:50,874 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:50,874 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration1_Loop [2024-11-09 16:04:50,874 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:50,875 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:50,888 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:50,901 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:50,916 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:50,921 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:50,924 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:50,980 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:50,981 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:50,982 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:50,983 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,008 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:51,011 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-09 16:04:51,012 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,012 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,028 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:51,028 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:51,039 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-09 16:04:51,040 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,041 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,042 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:51,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-09 16:04:51,043 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,043 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,075 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-09 16:04:51,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,076 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,079 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:51,081 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-09 16:04:51,082 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:51,082 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,454 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:51,460 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:51,460 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:51,460 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:51,461 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:51,461 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:51,461 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:51,461 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,461 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:51,461 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:51,461 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration1_Loop [2024-11-09 16:04:51,461 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:51,461 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:51,463 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,467 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,475 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,479 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,485 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,525 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:51,530 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:51,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,533 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:51,536 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-09 16:04:51,538 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:04:51,552 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:51,553 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:51,553 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:51,553 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:51,554 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:51,556 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:51,556 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:51,563 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:51,577 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:51,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,580 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:51,581 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-09 16:04:51,581 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:04:51,592 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:51,592 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:51,592 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:51,592 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:51,593 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:51,595 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:51,595 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:51,598 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:51,601 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:04:51,601 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:04:51,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,630 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:51,632 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-09 16:04:51,632 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:51,633 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:51,633 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:51,633 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -2*f91_#in~x + 211 Supporting invariants [] [2024-11-09 16:04:51,648 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-11-09 16:04:51,655 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:51,684 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:51,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:51,717 INFO L255 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 16:04:51,718 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:51,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:51,741 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:51,744 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:51,787 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:04:51,817 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-09 16:04:51,819 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:04:51,919 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 35 states and 43 transitions. Complement of second has 16 states. [2024-11-09 16:04:51,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:04:51,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 16:04:51,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2024-11-09 16:04:51,933 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2024-11-09 16:04:51,934 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:51,934 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2024-11-09 16:04:51,935 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:51,936 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2024-11-09 16:04:51,936 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:51,937 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 35 states and 43 transitions. [2024-11-09 16:04:51,940 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:51,950 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 35 states to 19 states and 25 transitions. [2024-11-09 16:04:51,951 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2024-11-09 16:04:51,952 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2024-11-09 16:04:51,952 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2024-11-09 16:04:51,954 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:51,954 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2024-11-09 16:04:51,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2024-11-09 16:04:51,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-11-09 16:04:51,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:04:51,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-11-09 16:04:51,985 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-09 16:04:51,986 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-09 16:04:51,986 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 16:04:51,986 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2024-11-09 16:04:51,987 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:51,987 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:51,987 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:51,988 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:51,988 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:51,989 INFO L745 eck$LassoCheckResult]: Stem: 119#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3); 120#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 113#L28 call main_#t~ret7#1 := f91(main_~x~0#1);< 112#$Ultimate##0 ~x := #in~x; 114#L18 assume !(~x > 100); 110#L21 call #t~ret4 := f91(11 + ~x);< 115#$Ultimate##0 ~x := #in~x; 116#L18 assume ~x > 100;#res := ~x - 10; 123#f91FINAL assume true; 109#f91EXIT >#29#return; 111#L21-1 [2024-11-09 16:04:51,989 INFO L747 eck$LassoCheckResult]: Loop: 111#L21-1 call #t~ret5 := f91(#t~ret4);< 118#$Ultimate##0 ~x := #in~x; 125#L18 assume !(~x > 100); 117#L21 call #t~ret4 := f91(11 + ~x);< 118#$Ultimate##0 ~x := #in~x; 125#L18 assume ~x > 100;#res := ~x - 10; 122#f91FINAL assume true; 124#f91EXIT >#29#return; 111#L21-1 [2024-11-09 16:04:51,989 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:51,989 INFO L85 PathProgramCache]: Analyzing trace with hash -218206616, now seen corresponding path program 1 times [2024-11-09 16:04:51,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:51,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [726621874] [2024-11-09 16:04:51,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:51,990 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:52,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,001 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:52,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,020 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:52,021 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,021 INFO L85 PathProgramCache]: Analyzing trace with hash 1767505954, now seen corresponding path program 1 times [2024-11-09 16:04:52,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:52,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [93134225] [2024-11-09 16:04:52,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:52,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:52,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,032 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:52,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,044 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:52,045 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,045 INFO L85 PathProgramCache]: Analyzing trace with hash -1919740023, now seen corresponding path program 1 times [2024-11-09 16:04:52,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:52,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [487724482] [2024-11-09 16:04:52,046 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:52,046 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:52,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,077 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:52,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,104 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:52,291 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:52,291 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:52,291 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:52,291 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:52,292 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:52,292 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,292 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:52,292 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:52,292 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration2_Loop [2024-11-09 16:04:52,292 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:52,292 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:52,293 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:52,300 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:52,302 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:52,350 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:52,351 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:52,351 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,353 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:52,355 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-09 16:04:52,357 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:52,357 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,372 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:52,372 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#t~ret5=0} Honda state: {f91_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:52,389 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-09 16:04:52,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,389 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,391 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:52,393 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-09 16:04:52,394 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:52,395 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,409 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:52,409 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:04:52,425 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:52,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,426 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,427 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:52,428 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-09 16:04:52,429 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:52,429 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,465 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:52,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,466 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,478 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:04:52,486 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-09 16:04:52,487 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:52,488 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,501 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-09 16:05:04,550 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-09 16:05:04,562 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:04,563 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:04,563 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:04,563 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:04,563 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:04,563 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:04,563 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:04,563 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:04,563 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:04,563 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration2_Loop [2024-11-09 16:05:04,563 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:04,563 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:04,565 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:04,567 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:04,570 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:04,619 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:04,619 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:04,620 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:04,620 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:04,621 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:04,623 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-11-09 16:05:04,624 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:04,636 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:04,636 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:04,636 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:04,636 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:04,636 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:04,637 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:04,637 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:04,639 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:04,654 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-09 16:05:04,654 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:04,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:04,656 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:04,658 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-09 16:05:04,659 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:04,670 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:04,671 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:04,671 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:04,671 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:04,671 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:04,672 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:04,672 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:04,674 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:04,685 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:04,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:04,686 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:04,687 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:04,688 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-09 16:05:04,689 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:04,699 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:04,699 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:04,699 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:04,699 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:04,699 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:04,701 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:04,702 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:04,705 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:04,707 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:04,707 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:04,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:04,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:04,716 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:04,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-09 16:05:04,717 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:04,717 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:04,718 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:04,718 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2024-11-09 16:05:04,728 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:04,729 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:04,731 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2024-11-09 16:05:04,745 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:04,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:04,770 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:04,771 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:04,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:04,877 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:04,878 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:04,988 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:04,989 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:04,989 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 17 states and 21 transitions. cyclomatic complexity: 6 Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:05,180 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 17 states and 21 transitions. cyclomatic complexity: 6. Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 51 states and 73 transitions. Complement of second has 32 states. [2024-11-09 16:05:05,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:05,181 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), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 16:05:05,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-11-09 16:05:05,182 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2024-11-09 16:05:05,183 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:05,183 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2024-11-09 16:05:05,183 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:05,183 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2024-11-09 16:05:05,183 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:05,184 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2024-11-09 16:05:05,187 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-11-09 16:05:05,190 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2024-11-09 16:05:05,190 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-09 16:05:05,190 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2024-11-09 16:05:05,191 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2024-11-09 16:05:05,191 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:05,191 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2024-11-09 16:05:05,191 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2024-11-09 16:05:05,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2024-11-09 16:05:05,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 10 states have call successors, (13), 7 states have call predecessors, (13), 4 states have return successors, (12), 5 states have call predecessors, (12), 7 states have call successors, (12) [2024-11-09 16:05:05,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2024-11-09 16:05:05,197 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-11-09 16:05:05,197 INFO L425 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-11-09 16:05:05,197 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 16:05:05,197 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2024-11-09 16:05:05,198 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-11-09 16:05:05,199 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:05,199 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:05,199 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:05,199 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 16:05:05,199 INFO L745 eck$LassoCheckResult]: Stem: 316#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3); 317#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 311#L28 call main_#t~ret7#1 := f91(main_~x~0#1);< 315#$Ultimate##0 ~x := #in~x; 321#L18 assume !(~x > 100); 306#L21 call #t~ret4 := f91(11 + ~x);< 304#$Ultimate##0 ~x := #in~x; 308#L18 assume ~x > 100;#res := ~x - 10; 326#f91FINAL assume true; 325#f91EXIT >#29#return; 296#L21-1 call #t~ret5 := f91(#t~ret4);< 313#$Ultimate##0 ~x := #in~x; 328#L18 assume !(~x > 100); 302#L21 [2024-11-09 16:05:05,199 INFO L747 eck$LassoCheckResult]: Loop: 302#L21 call #t~ret4 := f91(11 + ~x);< 301#$Ultimate##0 ~x := #in~x; 303#L18 assume !(~x > 100); 302#L21 [2024-11-09 16:05:05,200 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,200 INFO L85 PathProgramCache]: Analyzing trace with hash 1987218266, now seen corresponding path program 2 times [2024-11-09 16:05:05,200 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:05,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [789110444] [2024-11-09 16:05:05,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:05,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:05,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,218 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:05,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,230 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:05,231 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,231 INFO L85 PathProgramCache]: Analyzing trace with hash 57247, now seen corresponding path program 2 times [2024-11-09 16:05:05,231 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:05,231 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1720402331] [2024-11-09 16:05:05,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:05,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:05,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,235 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:05,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,240 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:05,240 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,241 INFO L85 PathProgramCache]: Analyzing trace with hash -609818202, now seen corresponding path program 3 times [2024-11-09 16:05:05,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:05,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [622828126] [2024-11-09 16:05:05,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:05,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:05,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:05,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-09 16:05:05,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:05,446 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 16:05:05,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:05,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [622828126] [2024-11-09 16:05:05,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [622828126] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:05,448 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:05,448 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-09 16:05:05,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1938469308] [2024-11-09 16:05:05,449 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:05,508 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:05,508 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:05,508 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:05,508 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:05,508 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:05,509 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,509 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:05,509 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:05,509 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration3_Loop [2024-11-09 16:05:05,509 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:05,509 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:05,510 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,516 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,520 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,522 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,552 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:05,552 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:05,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,554 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:05,556 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-09 16:05:05,557 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:05,557 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:05,589 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:05,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,591 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:05,591 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-09 16:05:05,593 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:05,593 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:17,630 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-09 16:05:17,639 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,640 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:17,640 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:17,640 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:17,640 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:17,640 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:17,640 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,640 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:17,640 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:17,640 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration3_Loop [2024-11-09 16:05:17,640 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:17,640 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:17,641 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,643 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,649 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,652 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:17,684 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:17,684 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:17,684 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,686 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-11-09 16:05:17,690 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:17,700 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:17,700 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:17,700 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:17,700 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:17,701 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:17,701 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:17,701 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:17,702 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:17,713 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:17,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,715 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,716 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-09 16:05:17,718 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:17,727 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:17,728 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:17,728 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:17,728 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:17,728 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:17,729 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:17,729 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:17,732 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:17,735 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:17,735 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:17,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:17,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:17,737 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:17,738 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-09 16:05:17,739 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:17,739 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:17,739 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:17,739 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_~x) = -2*f91_~x + 189 Supporting invariants [] [2024-11-09 16:05:17,750 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 [2024-11-09 16:05:17,751 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:17,767 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:17,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:17,811 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:17,812 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:17,825 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-09 16:05:17,841 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-09 16:05:17,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:17,907 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:17,908 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:17,932 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:17,933 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 16:05:17,934 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,010 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 43 states and 59 transitions. Complement of second has 13 states. [2024-11-09 16:05:18,011 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:18,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 16:05:18,012 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-11-09 16:05:18,012 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,013 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:18,025 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,049 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,050 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,119 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,120 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,147 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:18,148 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 16:05:18,148 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,209 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 43 states and 59 transitions. Complement of second has 13 states. [2024-11-09 16:05:18,211 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:18,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 16:05:18,213 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-11-09 16:05:18,213 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,213 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:18,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,255 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,256 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,318 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,319 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,343 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:18,344 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 16:05:18,344 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,412 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 71 states and 100 transitions. Complement of second has 16 states. [2024-11-09 16:05:18,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:18,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2024-11-09 16:05:18,414 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2024-11-09 16:05:18,415 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,415 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2024-11-09 16:05:18,415 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,415 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2024-11-09 16:05:18,415 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,416 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2024-11-09 16:05:18,418 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2024-11-09 16:05:18,420 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2024-11-09 16:05:18,420 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-09 16:05:18,421 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-11-09 16:05:18,421 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2024-11-09 16:05:18,421 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:18,421 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2024-11-09 16:05:18,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2024-11-09 16:05:18,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2024-11-09 16:05:18,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 11 states have call successors, (18), 9 states have call predecessors, (18), 5 states have return successors, (15), 6 states have call predecessors, (15), 8 states have call successors, (15) [2024-11-09 16:05:18,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2024-11-09 16:05:18,427 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2024-11-09 16:05:18,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:18,429 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 16:05:18,430 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-09 16:05:18,431 INFO L87 Difference]: Start difference. First operand 42 states and 60 transitions. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 16:05:18,527 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:18,528 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2024-11-09 16:05:18,528 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2024-11-09 16:05:18,530 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-09 16:05:18,532 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2024-11-09 16:05:18,532 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2024-11-09 16:05:18,532 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-11-09 16:05:18,532 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2024-11-09 16:05:18,533 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:18,533 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-11-09 16:05:18,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2024-11-09 16:05:18,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-11-09 16:05:18,537 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.0571428571428572) internal successors, (37), 37 states have internal predecessors, (37), 13 states have call successors, (18), 11 states have call predecessors, (18), 9 states have return successors, (19), 8 states have call predecessors, (19), 11 states have call successors, (19) [2024-11-09 16:05:18,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-11-09 16:05:18,538 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-11-09 16:05:18,538 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 16:05:18,539 INFO L425 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-11-09 16:05:18,539 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 16:05:18,539 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2024-11-09 16:05:18,540 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-09 16:05:18,541 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:18,541 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:18,542 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-09 16:05:18,542 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-09 16:05:18,542 INFO L745 eck$LassoCheckResult]: Stem: 853#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3); 854#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 849#L28 call main_#t~ret7#1 := f91(main_~x~0#1);< 852#$Ultimate##0 ~x := #in~x; 876#L18 assume !(~x > 100); 869#L21 call #t~ret4 := f91(11 + ~x);< 871#$Ultimate##0 ~x := #in~x; 873#L18 assume !(~x > 100); 868#L21 call #t~ret4 := f91(11 + ~x);< 872#$Ultimate##0 ~x := #in~x; 875#L18 assume ~x > 100;#res := ~x - 10; 874#f91FINAL assume true; 870#f91EXIT >#29#return; 843#L21-1 call #t~ret5 := f91(#t~ret4);< 842#$Ultimate##0 ~x := #in~x; 844#L18 assume ~x > 100;#res := ~x - 10; 861#f91FINAL assume true; 891#f91EXIT >#31#return; 838#L21-2 #res := #t~ret5;havoc #t~ret4;havoc #t~ret5; 888#f91FINAL assume true; 887#f91EXIT >#29#return; 836#L21-1 call #t~ret5 := f91(#t~ret4);< 850#$Ultimate##0 [2024-11-09 16:05:18,542 INFO L747 eck$LassoCheckResult]: Loop: 850#$Ultimate##0 ~x := #in~x; 879#L18 assume !(~x > 100); 847#L21 call #t~ret4 := f91(11 + ~x);< 845#$Ultimate##0 ~x := #in~x; 848#L18 assume !(~x > 100); 846#L21 call #t~ret4 := f91(11 + ~x);< 864#$Ultimate##0 ~x := #in~x; 885#L18 assume ~x > 100;#res := ~x - 10; 883#f91FINAL assume true; 881#f91EXIT >#29#return; 857#L21-1 call #t~ret5 := f91(#t~ret4);< 880#$Ultimate##0 ~x := #in~x; 877#L18 assume ~x > 100;#res := ~x - 10; 878#f91FINAL assume true; 889#f91EXIT >#31#return; 838#L21-2 #res := #t~ret5;havoc #t~ret4;havoc #t~ret5; 888#f91FINAL assume true; 887#f91EXIT >#29#return; 837#L21-1 call #t~ret5 := f91(#t~ret4);< 850#$Ultimate##0 [2024-11-09 16:05:18,543 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,543 INFO L85 PathProgramCache]: Analyzing trace with hash -834951989, now seen corresponding path program 1 times [2024-11-09 16:05:18,543 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:18,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1140737273] [2024-11-09 16:05:18,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:18,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:18,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:18,557 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:18,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:18,574 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:18,574 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,574 INFO L85 PathProgramCache]: Analyzing trace with hash -871747263, now seen corresponding path program 1 times [2024-11-09 16:05:18,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:18,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1848820729] [2024-11-09 16:05:18,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:18,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:18,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:18,586 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:18,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:18,596 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:18,600 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,601 INFO L85 PathProgramCache]: Analyzing trace with hash 418853943, now seen corresponding path program 2 times [2024-11-09 16:05:18,601 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:18,601 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1644503158] [2024-11-09 16:05:18,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:18,601 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:18,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,729 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-09 16:05:18,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,759 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 16:05:18,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,762 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 16:05:18,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,772 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 16:05:18,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,850 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 16:05:18,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,857 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 16:05:18,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,862 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 16:05:18,862 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:18,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1644503158] [2024-11-09 16:05:18,863 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1644503158] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:18,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1928118567] [2024-11-09 16:05:18,863 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 16:05:18,863 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:18,864 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:18,865 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 16:05:18,867 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-09 16:05:18,910 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 16:05:18,910 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:18,911 INFO L255 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,913 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,963 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 16:05:18,967 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:19,246 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 16:05:19,246 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1928118567] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:19,246 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:19,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 17 [2024-11-09 16:05:19,247 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1388717641] [2024-11-09 16:05:19,247 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:19,415 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:19,415 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:19,415 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:19,416 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:19,416 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:19,416 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,416 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:19,416 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:19,416 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration4_Loop [2024-11-09 16:05:19,416 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:19,416 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:19,417 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,422 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,424 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,426 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,428 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,456 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:19,457 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:19,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,459 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:19,461 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-09 16:05:19,462 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:19,462 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:19,498 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-11-09 16:05:19,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,500 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:19,501 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-09 16:05:19,502 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:19,502 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:19,518 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:19,533 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2024-11-09 16:05:19,533 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:19,533 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:19,533 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:19,533 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:19,533 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:19,534 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,534 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:19,534 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:19,534 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration4_Loop [2024-11-09 16:05:19,534 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:19,534 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:19,535 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,540 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,542 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,544 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,545 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,571 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:19,571 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:19,571 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,571 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,572 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:19,573 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-09 16:05:19,574 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:19,584 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:19,584 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:19,584 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:19,584 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:19,584 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:19,585 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:19,585 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:19,587 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:19,590 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:19,590 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:19,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,592 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:19,594 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-11-09 16:05:19,594 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:19,594 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:19,594 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:19,594 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -1*f91_#in~x + 90 Supporting invariants [] [2024-11-09 16:05:19,608 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2024-11-09 16:05:19,609 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:19,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:19,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,663 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:19,664 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:19,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,850 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-09 16:05:19,852 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:20,053 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-09 16:05:20,054 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 10 loop predicates [2024-11-09 16:05:20,054 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:20,413 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Result 125 states and 150 transitions. Complement of second has 49 states. [2024-11-09 16:05:20,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 15 states 2 stem states 12 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:20,416 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 16:05:20,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-11-09 16:05:20,417 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-09 16:05:20,430 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:20,430 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:20,451 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2024-11-09 16:05:20,457 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:20,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:20,491 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:20,492 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:20,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:20,645 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:20,647 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:20,801 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:20,802 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 9 loop predicates [2024-11-09 16:05:20,802 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 16:05:21,072 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Result 125 states and 150 transitions. Complement of second has 39 states. [2024-11-09 16:05:21,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 14 states 2 stem states 11 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:21,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 16:05:21,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2024-11-09 16:05:21,074 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 14 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-09 16:05:21,074 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:21,074 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:21,083 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:21,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:21,116 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:21,117 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:21,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:21,277 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:21,278 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:21,440 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 16:05:21,440 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 9 loop predicates [2024-11-09 16:05:21,441 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 16:05:21,994 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Result 325 states and 417 transitions. Complement of second has 131 states. [2024-11-09 16:05:21,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 19 states 2 stem states 16 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:21,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 16:05:21,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 50 transitions. [2024-11-09 16:05:21,997 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-09 16:05:21,997 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:21,998 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2024-11-09 16:05:21,998 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:21,998 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 19 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2024-11-09 16:05:21,999 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:21,999 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 325 states and 417 transitions. [2024-11-09 16:05:22,009 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 25 [2024-11-09 16:05:22,013 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 325 states to 169 states and 230 transitions. [2024-11-09 16:05:22,013 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-09 16:05:22,014 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2024-11-09 16:05:22,014 INFO L73 IsDeterministic]: Start isDeterministic. Operand 169 states and 230 transitions. [2024-11-09 16:05:22,014 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:22,014 INFO L218 hiAutomatonCegarLoop]: Abstraction has 169 states and 230 transitions. [2024-11-09 16:05:22,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states and 230 transitions. [2024-11-09 16:05:22,029 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 140. [2024-11-09 16:05:22,029 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 86 states have (on average 1.0813953488372092) internal successors, (93), 88 states have internal predecessors, (93), 32 states have call successors, (42), 26 states have call predecessors, (42), 22 states have return successors, (43), 25 states have call predecessors, (43), 28 states have call successors, (43) [2024-11-09 16:05:22,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 178 transitions. [2024-11-09 16:05:22,031 INFO L240 hiAutomatonCegarLoop]: Abstraction has 140 states and 178 transitions. [2024-11-09 16:05:22,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:22,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-09 16:05:22,032 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=228, Unknown=0, NotChecked=0, Total=272 [2024-11-09 16:05:22,032 INFO L87 Difference]: Start difference. First operand 140 states and 178 transitions. Second operand has 17 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 10 states have internal predecessors, (24), 8 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 7 states have call predecessors, (10), 5 states have call successors, (10) [2024-11-09 16:05:22,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:22,224 INFO L93 Difference]: Finished difference Result 138 states and 163 transitions. [2024-11-09 16:05:22,224 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 138 states and 163 transitions. [2024-11-09 16:05:22,226 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:05:22,228 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 138 states to 101 states and 121 transitions. [2024-11-09 16:05:22,228 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-11-09 16:05:22,228 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-11-09 16:05:22,228 INFO L73 IsDeterministic]: Start isDeterministic. Operand 101 states and 121 transitions. [2024-11-09 16:05:22,229 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:22,229 INFO L218 hiAutomatonCegarLoop]: Abstraction has 101 states and 121 transitions. [2024-11-09 16:05:22,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states and 121 transitions. [2024-11-09 16:05:22,234 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2024-11-09 16:05:22,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 60 states have (on average 1.05) internal successors, (63), 61 states have internal predecessors, (63), 22 states have call successors, (29), 19 states have call predecessors, (29), 15 states have return successors, (25), 16 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 16:05:22,235 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 117 transitions. [2024-11-09 16:05:22,235 INFO L240 hiAutomatonCegarLoop]: Abstraction has 97 states and 117 transitions. [2024-11-09 16:05:22,236 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 16:05:22,237 INFO L425 stractBuchiCegarLoop]: Abstraction has 97 states and 117 transitions. [2024-11-09 16:05:22,237 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 16:05:22,237 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 97 states and 117 transitions. [2024-11-09 16:05:22,238 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:05:22,238 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:22,238 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:22,239 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2024-11-09 16:05:22,239 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:22,239 INFO L745 eck$LassoCheckResult]: Stem: 2781#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3); 2782#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 2779#L28 call main_#t~ret7#1 := f91(main_~x~0#1);< 2780#$Ultimate##0 ~x := #in~x; 2793#L18 assume !(~x > 100); 2794#L21 call #t~ret4 := f91(11 + ~x);< 2798#$Ultimate##0 ~x := #in~x; 2811#L18 assume !(~x > 100); 2805#L21 call #t~ret4 := f91(11 + ~x);< 2809#$Ultimate##0 ~x := #in~x; 2812#L18 assume ~x > 100;#res := ~x - 10; 2810#f91FINAL assume true; 2808#f91EXIT >#29#return; 2804#L21-1 call #t~ret5 := f91(#t~ret4);< 2807#$Ultimate##0 ~x := #in~x; 2837#L18 assume ~x > 100;#res := ~x - 10; 2825#f91FINAL assume true; 2824#f91EXIT >#31#return; 2822#L21-2 #res := #t~ret5;havoc #t~ret4;havoc #t~ret5; 2821#f91FINAL assume true; 2820#f91EXIT >#29#return; 2813#L21-1 call #t~ret5 := f91(#t~ret4);< 2819#$Ultimate##0 ~x := #in~x; 2817#L18 assume !(~x > 100); 2774#L21 call #t~ret4 := f91(11 + ~x);< 2815#$Ultimate##0 ~x := #in~x; 2831#L18 assume ~x > 100;#res := ~x - 10; 2830#f91FINAL assume true; 2829#f91EXIT >#29#return; 2796#L21-1 call #t~ret5 := f91(#t~ret4);< 2828#$Ultimate##0 ~x := #in~x; 2841#L18 assume !(~x > 100); 2795#L21 call #t~ret4 := f91(11 + ~x);< 2797#$Ultimate##0 ~x := #in~x; 2855#L18 assume ~x > 100;#res := ~x - 10; 2854#f91FINAL assume true; 2846#f91EXIT >#29#return; 2786#L21-1 call #t~ret5 := f91(#t~ret4);< 2845#$Ultimate##0 [2024-11-09 16:05:22,239 INFO L747 eck$LassoCheckResult]: Loop: 2845#$Ultimate##0 ~x := #in~x; 2850#L18 assume !(~x > 100); 2848#L21 call #t~ret4 := f91(11 + ~x);< 2797#$Ultimate##0 ~x := #in~x; 2855#L18 assume ~x > 100;#res := ~x - 10; 2854#f91FINAL assume true; 2846#f91EXIT >#29#return; 2785#L21-1 call #t~ret5 := f91(#t~ret4);< 2845#$Ultimate##0 [2024-11-09 16:05:22,240 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:22,240 INFO L85 PathProgramCache]: Analyzing trace with hash 1139827145, now seen corresponding path program 3 times [2024-11-09 16:05:22,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:22,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [636836913] [2024-11-09 16:05:22,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:22,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:22,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:22,250 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:22,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:22,259 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:22,260 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:22,260 INFO L85 PathProgramCache]: Analyzing trace with hash 31195136, now seen corresponding path program 2 times [2024-11-09 16:05:22,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:22,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [771099800] [2024-11-09 16:05:22,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:22,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:22,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:22,264 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:22,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:22,266 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:22,266 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:22,267 INFO L85 PathProgramCache]: Analyzing trace with hash 424810952, now seen corresponding path program 4 times [2024-11-09 16:05:22,267 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:22,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [786670190] [2024-11-09 16:05:22,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:22,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:22,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:22,280 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:22,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:22,296 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:22,374 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:22,374 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:22,374 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:22,374 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:22,374 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:22,374 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,374 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:22,375 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:22,375 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration5_Loop [2024-11-09 16:05:22,375 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:22,375 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:22,376 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,378 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,380 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,387 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,390 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,417 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:22,417 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:22,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,420 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,422 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-09 16:05:22,424 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:22,424 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:22,438 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:22,438 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#t~ret4=0} Honda state: {f91_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:22,453 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:22,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,454 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,455 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-09 16:05:22,458 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:22,458 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:22,475 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:22,475 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 16:05:22,490 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:22,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,493 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,495 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-09 16:05:22,497 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:22,497 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:22,528 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:22,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,531 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,532 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-11-09 16:05:22,533 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:22,533 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:22,550 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:22,566 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2024-11-09 16:05:22,567 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:22,567 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:22,567 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:22,567 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:22,567 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:22,567 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,567 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:22,567 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:22,567 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration5_Loop [2024-11-09 16:05:22,567 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:22,567 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:22,568 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,572 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,575 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,577 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,585 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:22,615 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:22,615 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:22,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,617 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,618 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-09 16:05:22,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 [2024-11-09 16:05:22,629 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:22,629 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:22,629 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:22,629 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:22,629 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:22,630 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:22,630 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:22,631 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:22,641 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2024-11-09 16:05:22,642 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,642 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,643 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,643 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-09 16:05:22,644 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:22,654 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:22,654 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:22,654 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:22,654 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:22,654 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:22,654 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:22,654 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:22,656 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:22,666 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-11-09 16:05:22,666 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,668 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,668 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-09 16:05:22,669 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:22,681 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:22,682 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:22,682 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:22,682 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:22,682 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:22,682 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:22,682 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:22,684 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:22,699 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-11-09 16:05:22,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,701 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,702 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-09 16:05:22,703 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 16:05:22,715 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:22,715 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:22,715 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:22,715 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:22,715 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:22,716 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:22,716 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:22,718 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:22,720 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:22,721 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:22,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:22,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,722 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-09 16:05:22,723 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-09 16:05:22,724 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:22,725 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:22,725 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:22,725 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -2*f91_#in~x + 201 Supporting invariants [] [2024-11-09 16:05:22,739 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:22,740 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:22,753 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:22,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:22,809 INFO L255 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:22,810 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:22,924 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 [2024-11-09 16:05:23,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:23,096 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:23,097 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:23,174 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:23,175 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:23,175 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:23,250 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 107 states and 127 transitions. Complement of second has 16 states. [2024-11-09 16:05:23,251 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:23,252 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:23,252 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 15 transitions. [2024-11-09 16:05:23,252 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 15 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-09 16:05:23,252 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:23,253 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:23,263 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:23,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:23,317 INFO L255 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:23,319 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:23,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:23,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:23,526 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:23,605 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:23,606 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:23,606 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:23,779 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 125 states and 146 transitions. Complement of second has 28 states. [2024-11-09 16:05:23,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:23,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:23,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 20 transitions. [2024-11-09 16:05:23,781 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 20 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-09 16:05:23,781 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:23,781 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:23,791 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:23,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:23,844 INFO L255 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:23,845 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:24,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:24,049 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:24,050 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:24,132 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:24,133 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:24,133 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:24,226 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 147 states and 167 transitions. Complement of second has 17 states. [2024-11-09 16:05:24,228 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:24,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:24,229 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2024-11-09 16:05:24,229 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-09 16:05:24,229 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:24,229 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:24,242 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:24,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:24,292 INFO L255 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:24,294 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:24,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:24,501 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:24,501 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:24,562 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 16:05:24,562 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-09 16:05:24,563 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:24,850 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 97 states and 117 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 182 states and 209 transitions. Complement of second has 51 states. [2024-11-09 16:05:24,851 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 12 states 2 stem states 9 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:24,852 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 16:05:24,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 27 transitions. [2024-11-09 16:05:24,852 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 8 letters. [2024-11-09 16:05:24,853 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:24,853 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 46 letters. Loop has 8 letters. [2024-11-09 16:05:24,853 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:24,853 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 12 states and 27 transitions. Stem has 38 letters. Loop has 16 letters. [2024-11-09 16:05:24,853 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:24,854 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 182 states and 209 transitions. [2024-11-09 16:05:24,859 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:24,859 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 182 states to 0 states and 0 transitions. [2024-11-09 16:05:24,859 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:05:24,859 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:05:24,859 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:05:24,859 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:05:24,859 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:24,859 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:24,860 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:24,860 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 16:05:24,860 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 16:05:24,860 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:24,860 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 16:05:24,869 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 04:05:24 BoogieIcfgContainer [2024-11-09 16:05:24,869 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 16:05:24,870 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 16:05:24,870 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 16:05:24,870 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 16:05:24,870 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 04:04:50" (3/4) ... [2024-11-09 16:05:24,872 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 16:05:24,872 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 16:05:24,873 INFO L158 Benchmark]: Toolchain (without parser) took 34963.97ms. Allocated memory was 157.3MB in the beginning and 188.7MB in the end (delta: 31.5MB). Free memory was 103.9MB in the beginning and 151.9MB in the end (delta: -48.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:24,873 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 96.5MB. Free memory was 58.8MB in the beginning and 58.8MB in the end (delta: 69.9kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:24,873 INFO L158 Benchmark]: CACSL2BoogieTranslator took 259.31ms. Allocated memory is still 157.3MB. Free memory was 103.4MB in the beginning and 91.9MB in the end (delta: 11.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 16:05:24,874 INFO L158 Benchmark]: Boogie Procedure Inliner took 27.46ms. Allocated memory is still 157.3MB. Free memory was 91.9MB in the beginning and 90.3MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:24,874 INFO L158 Benchmark]: Boogie Preprocessor took 31.69ms. Allocated memory is still 157.3MB. Free memory was 90.3MB in the beginning and 88.7MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:24,874 INFO L158 Benchmark]: RCFGBuilder took 258.36ms. Allocated memory is still 157.3MB. Free memory was 88.7MB in the beginning and 126.1MB in the end (delta: -37.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 16:05:24,874 INFO L158 Benchmark]: BuchiAutomizer took 34379.19ms. Allocated memory was 157.3MB in the beginning and 188.7MB in the end (delta: 31.5MB). Free memory was 125.2MB in the beginning and 153.0MB in the end (delta: -27.8MB). Peak memory consumption was 4.3MB. Max. memory is 16.1GB. [2024-11-09 16:05:24,875 INFO L158 Benchmark]: Witness Printer took 2.88ms. Allocated memory is still 188.7MB. Free memory was 153.0MB in the beginning and 151.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:24,877 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19ms. Allocated memory is still 96.5MB. Free memory was 58.8MB in the beginning and 58.8MB in the end (delta: 69.9kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 259.31ms. Allocated memory is still 157.3MB. Free memory was 103.4MB in the beginning and 91.9MB in the end (delta: 11.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 27.46ms. Allocated memory is still 157.3MB. Free memory was 91.9MB in the beginning and 90.3MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 31.69ms. Allocated memory is still 157.3MB. Free memory was 90.3MB in the beginning and 88.7MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 258.36ms. Allocated memory is still 157.3MB. Free memory was 88.7MB in the beginning and 126.1MB in the end (delta: -37.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 34379.19ms. Allocated memory was 157.3MB in the beginning and 188.7MB in the end (delta: 31.5MB). Free memory was 125.2MB in the beginning and 153.0MB in the end (delta: -27.8MB). Peak memory consumption was 4.3MB. Max. memory is 16.1GB. * Witness Printer took 2.88ms. Allocated memory is still 188.7MB. Free memory was 153.0MB in the beginning and 151.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret4 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 7 terminating modules (2 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function (211 + ((long long) -2 * \old(x))) and consists of 5 locations. One deterministic module has affine ranking function null and consists of 8 locations. One nondeterministic module has affine ranking function (((long long) -2 * x) + 189) and consists of 6 locations. One nondeterministic module has affine ranking function (((long long) -1 * \old(x)) + 90) and consists of 19 locations. One nondeterministic module has affine ranking function (((long long) -2 * \old(x)) + 201) and consists of 12 locations. 2 modules have a trivial ranking function, the largest among these consists of 17 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 34.3s and 6 iterations. TraceHistogramMax:8. Analysis of lassos took 27.9s. Construction of modules took 0.7s. Büchi inclusion checks took 5.4s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 48 StatesRemovedByMinimization, 6 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 [2, 0, 2, 1, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 10/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 268 SdHoareTripleChecker+Valid, 0.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 252 mSDsluCounter, 417 SdHoareTripleChecker+Invalid, 0.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 233 mSDsCounter, 208 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 882 IncrementalHoareTripleChecker+Invalid, 1090 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 208 mSolverCounterUnsat, 184 mSDtfsCounter, 882 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT3 conc0 concLT2 SILN0 SILU0 SILI0 SILT0 lasso0 LassoPreprocessingBenchmarks: Lassos: inital12 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq171 hnf91 smp100 dnf100 smp100 tf110 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 32ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 5 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 3 LassoNonterminationAnalysisUnknown: 2 LassoNonterminationAnalysisTime: 24.8s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-09 16:05:24,898 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:25,101 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE