./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/McCarthy91-2.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-2.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 2a5dd5c1c64cd1875ba800cc2db6d1da955f2d2f519c1964ff87558bc42b9b4c --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 16:04:48,146 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 16:04:48,217 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:48,221 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 16:04:48,221 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 16:04:48,254 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 16:04:48,256 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 16:04:48,257 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 16:04:48,258 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 16:04:48,258 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 16:04:48,259 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 16:04:48,259 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 16:04:48,260 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 16:04:48,262 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 16:04:48,262 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 16:04:48,263 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 16:04:48,263 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 16:04:48,263 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 16:04:48,267 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 16:04:48,267 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 16:04:48,267 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 16:04:48,268 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 16:04:48,268 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 16:04:48,268 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 16:04:48,269 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 16:04:48,269 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 16:04:48,269 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 16:04:48,270 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 16:04:48,270 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 16:04:48,270 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 16:04:48,270 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 16:04:48,271 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 16:04:48,271 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 16:04:48,271 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 16:04:48,271 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 16:04:48,272 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 16:04:48,272 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 16:04:48,272 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 16:04:48,273 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 16:04:48,273 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 -> 2a5dd5c1c64cd1875ba800cc2db6d1da955f2d2f519c1964ff87558bc42b9b4c [2024-11-09 16:04:48,555 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 16:04:48,583 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 16:04:48,588 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 16:04:48,590 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 16:04:48,591 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 16:04:48,592 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/McCarthy91-2.c [2024-11-09 16:04:50,057 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 16:04:50,243 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 16:04:50,243 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-2.c [2024-11-09 16:04:50,251 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ccacaa7ce/f528376d877d425fad4ec9ae874a682d/FLAG306ba050f [2024-11-09 16:04:50,272 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ccacaa7ce/f528376d877d425fad4ec9ae874a682d [2024-11-09 16:04:50,275 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 16:04:50,278 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 16:04:50,282 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 16:04:50,282 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 16:04:50,289 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 16:04:50,292 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,293 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5fa4a08 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 04:04:50, skipping insertion in model container [2024-11-09 16:04:50,293 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 04:04:50" (1/1) ... [2024-11-09 16:04:50,318 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 16:04:50,520 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:04:50,536 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 16:04:50,549 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 16:04:50,568 INFO L204 MainTranslator]: Completed translation [2024-11-09 16:04:50,569 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,569 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 16:04:50,570 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 16:04:50,570 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 16:04:50,570 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 16:04:50,577 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,584 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,600 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2024-11-09 16:04:50,601 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 16:04:50,601 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 16:04:50,601 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 16:04:50,602 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 16:04:50,611 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,612 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,613 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,624 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,625 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,626 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,628 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,634 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,634 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,635 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,636 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 16:04:50,637 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 16:04:50,637 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 16:04:50,637 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 16:04:50,638 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,644 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:50,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:50,674 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,680 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,728 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 16:04:50,728 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 16:04:50,729 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 16:04:50,729 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 16:04:50,729 INFO L130 BoogieDeclarations]: Found specification of procedure f91 [2024-11-09 16:04:50,729 INFO L138 BoogieDeclarations]: Found implementation of procedure f91 [2024-11-09 16:04:50,783 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 16:04:50,784 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 16:04:50,875 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 16:04:50,875 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 16:04:50,888 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 16:04:50,888 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 16:04:50,889 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,889 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 16:04:50,891 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 16:04:50,891 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 16:04:50,895 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 16:04:50,899 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:50,899 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 04:04:50" (1/3) ... [2024-11-09 16:04:50,900 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@49f190b4 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,900 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:50,900 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,901 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@49f190b4 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,901 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 16:04:50,901 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,905 INFO L332 chiAutomizerObserver]: Analyzing ICFG McCarthy91-2.c [2024-11-09 16:04:50,972 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 16:04:50,972 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 16:04:50,972 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 16:04:50,972 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 16:04:50,972 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 16:04:50,972 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 16:04:50,972 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 16:04:50,973 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 16:04:50,976 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,995 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:50,996 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:50,996 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:51,001 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:04:51,001 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 16:04:51,001 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 16:04:51,001 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:51,003 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:51,003 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:51,003 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:51,004 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 16:04:51,004 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 16:04:51,010 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:51,010 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:51,016 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:51,016 INFO L85 PathProgramCache]: Analyzing trace with hash 29879, now seen corresponding path program 1 times [2024-11-09 16:04:51,028 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:51,029 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1801019808] [2024-11-09 16:04:51,029 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:51,030 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:51,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,108 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:51,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,133 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:51,136 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:51,136 INFO L85 PathProgramCache]: Analyzing trace with hash 46807, now seen corresponding path program 1 times [2024-11-09 16:04:51,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:51,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2084816981] [2024-11-09 16:04:51,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:51,137 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:51,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,147 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:51,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,152 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:51,153 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:51,154 INFO L85 PathProgramCache]: Analyzing trace with hash 890142305, now seen corresponding path program 1 times [2024-11-09 16:04:51,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:51,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510203417] [2024-11-09 16:04:51,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:51,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:51,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,169 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:51,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:51,188 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:51,300 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:51,301 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:51,301 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:51,301 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:51,301 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:51,301 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,301 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:51,301 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:51,301 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2024-11-09 16:04:51,301 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:51,302 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:51,313 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,321 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,334 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,337 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,340 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,393 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:51,394 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:51,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,398 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,400 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,402 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,402 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,420 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:51,420 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,432 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,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,433 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,435 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,437 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,438 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:51,438 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,462 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,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,465 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,467 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,469 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:51,469 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:51,834 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:04:51,840 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,840 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:51,840 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:51,840 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:51,840 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:51,840 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:04:51,840 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,841 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:51,841 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:51,841 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2024-11-09 16:04:51,841 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:51,841 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:51,842 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,847 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,853 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,855 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,858 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:51,894 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:51,898 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:04:51,900 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,900 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,901 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,904 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,905 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,919 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:51,919 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:51,920 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:51,920 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:51,920 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:51,923 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:51,923 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:51,926 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:04:51,942 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:51,943 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,943 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,945 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,946 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,947 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,960 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:04:51,960 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:04:51,960 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:04:51,960 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:04:51,960 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:04:51,962 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:04:51,962 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:04:51,964 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:04:51,968 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:04:51,968 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:04:51,969 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:51,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:51,972 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,979 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:04:51,980 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:04:51,980 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:04:51,980 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,981 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,994 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-09 16:04:51,997 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:04:52,033 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,056 INFO L255 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,057 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:04:52,086 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:04:52,087 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:04:52,135 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:52,164 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:52,165 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:52,257 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:52,261 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:52,267 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:52,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2024-11-09 16:04:52,269 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2024-11-09 16:04:52,271 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:52,271 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2024-11-09 16:04:52,272 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:52,272 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2024-11-09 16:04:52,272 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:04:52,274 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 35 states and 43 transitions. [2024-11-09 16:04:52,278 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:52,305 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 35 states to 19 states and 25 transitions. [2024-11-09 16:04:52,310 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2024-11-09 16:04:52,310 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2024-11-09 16:04:52,311 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2024-11-09 16:04:52,312 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:04:52,312 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2024-11-09 16:04:52,326 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:04:52,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2024-11-09 16:04:52,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-11-09 16:04:52,361 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:52,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-11-09 16:04:52,363 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-09 16:04:52,364 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-09 16:04:52,364 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 16:04:52,365 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2024-11-09 16:04:52,366 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-09 16:04:52,366 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:04:52,366 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:04:52,368 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:52,368 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:04:52,368 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:52,370 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:52,371 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,372 INFO L85 PathProgramCache]: Analyzing trace with hash -218206616, now seen corresponding path program 1 times [2024-11-09 16:04:52,372 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:52,374 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171140576] [2024-11-09 16:04:52,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:52,374 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:52,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,387 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:52,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,398 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:52,399 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,399 INFO L85 PathProgramCache]: Analyzing trace with hash 1767505954, now seen corresponding path program 1 times [2024-11-09 16:04:52,399 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:52,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1203532666] [2024-11-09 16:04:52,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:52,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:52,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,409 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:52,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,421 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:52,422 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:04:52,422 INFO L85 PathProgramCache]: Analyzing trace with hash -1919740023, now seen corresponding path program 1 times [2024-11-09 16:04:52,423 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:04:52,423 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [167860126] [2024-11-09 16:04:52,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:04:52,423 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:04:52,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,439 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:04:52,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:04:52,468 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:04:52,630 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:04:52,630 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:04:52,631 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:04:52,631 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:04:52,631 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:04:52,631 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,631 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:04:52,631 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:04:52,631 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2024-11-09 16:04:52,631 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:04:52,631 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:04:52,632 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:52,638 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:52,641 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:04:52,689 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:04:52,690 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:04:52,691 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,693 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,694 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,696 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:52,696 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,713 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:52,713 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,729 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,729 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,731 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,733 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,734 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:52,734 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,747 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:04:52,748 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,762 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-09 16:04:52,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,765 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,766 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,769 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:04:52,769 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:04:52,818 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-11-09 16:04:52,818 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:04:52,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:04:52,820 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,820 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,821 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:04:52,821 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:05,094 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-09 16:05:05,115 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:05,115 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:05,115 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:05,116 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:05,116 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:05,116 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:05,116 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,116 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:05,116 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:05,116 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2024-11-09 16:05:05,116 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:05,116 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:05,117 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,119 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,122 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:05,174 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:05,174 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:05,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,174 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,177 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:05,179 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:05,179 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:05,192 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:05,192 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:05,192 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:05,192 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:05,193 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:05,193 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:05,193 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:05,195 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:05,210 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:05,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,212 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:05,214 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:05,215 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:05,227 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:05,228 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:05,228 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:05,228 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:05,228 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:05,229 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:05,229 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:05,233 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:05,248 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-09 16:05:05,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,249 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,250 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:05,252 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:05,253 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:05,267 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:05,267 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:05,267 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:05,267 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:05,267 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:05,271 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:05,271 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:05,275 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:05,278 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:05,278 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:05,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:05,279 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:05,281 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:05,283 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:05,283 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:05,284 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:05,284 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:05,284 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:05,298 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-09 16:05:05,300 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:05,305 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2024-11-09 16:05:05,318 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:05,341 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 16:05:05,342 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:05,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:05,421 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:05,422 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:05,527 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:05,528 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:05,528 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,726 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,727 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,728 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,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-11-09 16:05:05,729 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,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:05,730 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,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:05,730 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,730 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:05,731 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2024-11-09 16:05:05,737 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-11-09 16:05:05,740 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2024-11-09 16:05:05,740 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-09 16:05:05,740 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2024-11-09 16:05:05,741 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2024-11-09 16:05:05,741 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:05,741 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2024-11-09 16:05:05,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2024-11-09 16:05:05,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2024-11-09 16:05:05,747 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,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2024-11-09 16:05:05,749 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-11-09 16:05:05,750 INFO L425 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-11-09 16:05:05,750 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 16:05:05,750 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2024-11-09 16:05:05,751 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-11-09 16:05:05,752 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:05,752 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:05,753 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:05,753 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 16:05:05,755 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,755 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,756 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,756 INFO L85 PathProgramCache]: Analyzing trace with hash 1987218266, now seen corresponding path program 2 times [2024-11-09 16:05:05,756 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:05,756 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [136608442] [2024-11-09 16:05:05,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:05,756 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:05,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,772 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:05,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,788 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:05,788 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,790 INFO L85 PathProgramCache]: Analyzing trace with hash 57247, now seen corresponding path program 2 times [2024-11-09 16:05:05,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:05,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2140518898] [2024-11-09 16:05:05,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:05,791 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:05,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,797 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:05,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:05,800 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:05,801 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:05,801 INFO L85 PathProgramCache]: Analyzing trace with hash -609818202, now seen corresponding path program 3 times [2024-11-09 16:05:05,801 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:05,801 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1555008541] [2024-11-09 16:05:05,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:05,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:05,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:05,944 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-09 16:05:05,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:05,979 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,979 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:05,979 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1555008541] [2024-11-09 16:05:05,980 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1555008541] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:05,980 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 16:05:05,980 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-09 16:05:05,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2108880762] [2024-11-09 16:05:05,981 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:06,037 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:06,038 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:06,038 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:06,038 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:06,038 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:06,038 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,038 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:06,038 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:06,038 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2024-11-09 16:05:06,038 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:06,038 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:06,039 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,047 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,050 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,052 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:06,078 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:06,078 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:06,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,080 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:06,082 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:06,083 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:06,083 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:06,114 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:06,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:06,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:06,116 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:06,116 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:06,117 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:06,117 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:18,150 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-09 16:05:18,159 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:18,159 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:18,159 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:18,160 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:18,160 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:18,160 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:18,160 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:18,160 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:18,160 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:18,160 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2024-11-09 16:05:18,160 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:18,160 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:18,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:18,163 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:18,168 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:18,170 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:18,196 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:18,197 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:18,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:18,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:18,199 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:18,201 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:18,203 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:18,213 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:18,213 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:18,213 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:18,213 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:18,213 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:18,214 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:18,214 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:18,215 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:18,226 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-09 16:05:18,226 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:18,226 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:18,227 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:18,228 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:18,229 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:18,239 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:18,239 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:18,239 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:18,239 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:18,239 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:18,240 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:18,240 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:18,243 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:18,245 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:18,246 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:18,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:18,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:18,247 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:18,249 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:18,249 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:18,249 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:18,249 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:18,249 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_~x) = -2*f91_~x + 189 Supporting invariants [] [2024-11-09 16:05:18,260 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-09 16:05:18,261 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:18,296 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:18,301 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,333 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:18,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,349 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,350 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,456 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,457 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,484 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,485 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:18,485 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,549 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,550 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,551 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,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 16:05:18,551 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,551 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,552 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:18,562 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,582 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,583 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,655 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,656 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,682 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,683 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,683 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,740 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,743 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,744 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,745 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-09 16:05:18,745 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,745 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,745 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:18,757 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:18,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,780 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,781 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:18,844 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 16:05:18,845 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:18,869 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,870 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,870 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,936 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,936 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,937 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,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2024-11-09 16:05:18,939 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,939 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,939 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,940 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,940 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,940 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:18,941 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2024-11-09 16:05:18,945 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2024-11-09 16:05:18,947 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2024-11-09 16:05:18,947 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-09 16:05:18,947 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-11-09 16:05:18,947 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2024-11-09 16:05:18,947 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:18,947 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2024-11-09 16:05:18,947 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2024-11-09 16:05:18,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2024-11-09 16:05:18,955 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,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2024-11-09 16:05:18,957 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2024-11-09 16:05:18,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:18,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 16:05:18,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-09 16:05:18,961 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:19,067 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:19,067 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2024-11-09 16:05:19,068 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2024-11-09 16:05:19,070 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-09 16:05:19,073 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2024-11-09 16:05:19,075 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2024-11-09 16:05:19,076 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-11-09 16:05:19,076 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2024-11-09 16:05:19,076 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:19,076 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-11-09 16:05:19,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2024-11-09 16:05:19,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-11-09 16:05:19,081 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:19,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-11-09 16:05:19,082 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-11-09 16:05:19,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 16:05:19,083 INFO L425 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-11-09 16:05:19,083 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 16:05:19,083 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2024-11-09 16:05:19,084 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-11-09 16:05:19,084 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:19,085 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:19,085 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-09 16:05:19,085 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-09 16:05:19,086 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:19,086 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:19,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:19,086 INFO L85 PathProgramCache]: Analyzing trace with hash -834951989, now seen corresponding path program 1 times [2024-11-09 16:05:19,086 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:19,087 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [807608852] [2024-11-09 16:05:19,087 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:19,087 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:19,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:19,094 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:19,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:19,102 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:19,102 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:19,102 INFO L85 PathProgramCache]: Analyzing trace with hash -871747263, now seen corresponding path program 1 times [2024-11-09 16:05:19,102 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:19,102 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [96959909] [2024-11-09 16:05:19,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:19,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:19,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:19,108 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:19,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:19,113 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:19,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:19,114 INFO L85 PathProgramCache]: Analyzing trace with hash 418853943, now seen corresponding path program 2 times [2024-11-09 16:05:19,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:19,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1450164497] [2024-11-09 16:05:19,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:19,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:19,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,222 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-09 16:05:19,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,263 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 16:05:19,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,266 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 16:05:19,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,275 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 16:05:19,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,347 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 16:05:19,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,356 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 16:05:19,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:19,363 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,365 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:19,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1450164497] [2024-11-09 16:05:19,366 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1450164497] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:19,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [421246596] [2024-11-09 16:05:19,366 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 16:05:19,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:19,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,368 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:19,369 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:19,411 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 16:05:19,411 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:19,412 INFO L255 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 16:05:19,414 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:19,460 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,463 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 16:05:19,709 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,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [421246596] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 16:05:19,710 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 16:05:19,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 17 [2024-11-09 16:05:19,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1187732204] [2024-11-09 16:05:19,711 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 16:05:19,880 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:19,880 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:19,881 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:19,881 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:19,881 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:19,881 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,881 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:19,881 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:19,881 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2024-11-09 16:05:19,881 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:19,882 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:19,882 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,887 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,890 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,892 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,894 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:19,919 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:19,919 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:19,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,921 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,923 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,924 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:19,924 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:19,963 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:19,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:19,965 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,966 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,967 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:19,967 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:19,979 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 16:05:19,994 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,995 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:19,995 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:19,995 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:19,995 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:19,995 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:19,995 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:19,995 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:19,996 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:19,996 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2024-11-09 16:05:19,996 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:19,996 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:19,997 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:20,002 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:20,004 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:20,006 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:20,008 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:20,033 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:20,034 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:20,034 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:20,034 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:20,036 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:20,037 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:20,038 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:20,049 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:20,049 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:20,049 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:20,049 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:20,049 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:20,050 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:20,050 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:20,053 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:20,055 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:20,055 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:20,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:20,056 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:20,057 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:20,057 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:20,058 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:20,058 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:20,058 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:20,058 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:20,068 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:20,069 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:20,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:20,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:20,118 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:20,119 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:20,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:20,310 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-09 16:05:20,312 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:20,516 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,516 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,517 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,880 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,899 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,900 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,901 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,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-11-09 16:05:20,901 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,902 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:20,902 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:20,912 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:20,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:20,944 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:20,946 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:21,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:21,109 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-09 16:05:21,111 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:21,254 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,255 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:21,255 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,536 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,537 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,538 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,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2024-11-09 16:05:21,538 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,539 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:21,539 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:21,547 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:21,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:21,582 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 16:05:21,583 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:21,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:21,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-09 16:05:21,750 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:21,963 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:21,963 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 10 loop predicates [2024-11-09 16:05:21,964 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:22,596 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 431 states and 531 transitions. Complement of second has 224 states. [2024-11-09 16:05:22,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 21 states 2 stem states 18 non-accepting loop states 1 accepting loop states [2024-11-09 16:05:22,598 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:22,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 50 transitions. [2024-11-09 16:05:22,599 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2024-11-09 16:05:22,599 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:22,599 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2024-11-09 16:05:22,600 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:22,600 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2024-11-09 16:05:22,601 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:22,601 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 431 states and 531 transitions. [2024-11-09 16:05:22,608 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 29 [2024-11-09 16:05:22,612 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 431 states to 203 states and 269 transitions. [2024-11-09 16:05:22,612 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 95 [2024-11-09 16:05:22,613 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 106 [2024-11-09 16:05:22,613 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 269 transitions. [2024-11-09 16:05:22,613 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:22,613 INFO L218 hiAutomatonCegarLoop]: Abstraction has 203 states and 269 transitions. [2024-11-09 16:05:22,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 269 transitions. [2024-11-09 16:05:22,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 157. [2024-11-09 16:05:22,627 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 97 states have (on average 1.092783505154639) internal successors, (106), 99 states have internal predecessors, (106), 35 states have call successors, (45), 29 states have call predecessors, (45), 25 states have return successors, (47), 28 states have call predecessors, (47), 32 states have call successors, (47) [2024-11-09 16:05:22,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 198 transitions. [2024-11-09 16:05:22,629 INFO L240 hiAutomatonCegarLoop]: Abstraction has 157 states and 198 transitions. [2024-11-09 16:05:22,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:22,630 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-09 16:05:22,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=228, Unknown=0, NotChecked=0, Total=272 [2024-11-09 16:05:22,630 INFO L87 Difference]: Start difference. First operand 157 states and 198 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,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:22,791 INFO L93 Difference]: Finished difference Result 159 states and 188 transitions. [2024-11-09 16:05:22,791 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 159 states and 188 transitions. [2024-11-09 16:05:22,793 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-11-09 16:05:22,795 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 159 states to 104 states and 123 transitions. [2024-11-09 16:05:22,795 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2024-11-09 16:05:22,795 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-09 16:05:22,795 INFO L73 IsDeterministic]: Start isDeterministic. Operand 104 states and 123 transitions. [2024-11-09 16:05:22,795 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 16:05:22,796 INFO L218 hiAutomatonCegarLoop]: Abstraction has 104 states and 123 transitions. [2024-11-09 16:05:22,796 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states and 123 transitions. [2024-11-09 16:05:22,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 100. [2024-11-09 16:05:22,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 63 states have (on average 1.0476190476190477) internal successors, (66), 64 states have internal predecessors, (66), 21 states have call successors, (28), 20 states have call predecessors, (28), 16 states have return successors, (25), 15 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 16:05:22,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 119 transitions. [2024-11-09 16:05:22,811 INFO L240 hiAutomatonCegarLoop]: Abstraction has 100 states and 119 transitions. [2024-11-09 16:05:22,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 16:05:22,812 INFO L425 stractBuchiCegarLoop]: Abstraction has 100 states and 119 transitions. [2024-11-09 16:05:22,813 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 16:05:22,813 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 100 states and 119 transitions. [2024-11-09 16:05:22,814 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-11-09 16:05:22,815 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 16:05:22,815 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 16:05:22,816 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1] [2024-11-09 16:05:22,816 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-11-09 16:05:22,817 INFO L745 eck$LassoCheckResult]: Stem: 3022#$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); 3023#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; 3020#L28 call main_#t~ret7#1 := f91(main_~x~0#1);< 3021#$Ultimate##0 ~x := #in~x; 3033#L18 assume !(~x > 100); 3034#L21 call #t~ret4 := f91(11 + ~x);< 3037#$Ultimate##0 ~x := #in~x; 3050#L18 assume !(~x > 100); 3044#L21 call #t~ret4 := f91(11 + ~x);< 3048#$Ultimate##0 ~x := #in~x; 3051#L18 assume ~x > 100;#res := ~x - 10; 3049#f91FINAL assume true; 3047#f91EXIT >#29#return; 3043#L21-1 call #t~ret5 := f91(#t~ret4);< 3045#$Ultimate##0 ~x := #in~x; 3077#L18 assume ~x > 100;#res := ~x - 10; 3064#f91FINAL assume true; 3063#f91EXIT >#31#return; 3061#L21-2 #res := #t~ret5;havoc #t~ret4;havoc #t~ret5; 3060#f91FINAL assume true; 3059#f91EXIT >#29#return; 3052#L21-1 call #t~ret5 := f91(#t~ret4);< 3058#$Ultimate##0 ~x := #in~x; 3056#L18 assume !(~x > 100); 3015#L21 call #t~ret4 := f91(11 + ~x);< 3014#$Ultimate##0 ~x := #in~x; 3016#L18 assume !(~x > 100); 3004#L21 call #t~ret4 := f91(11 + ~x);< 3055#$Ultimate##0 ~x := #in~x; 3102#L18 assume ~x > 100;#res := ~x - 10; 3101#f91FINAL assume true; 3003#f91EXIT >#29#return; 3005#L21-1 [2024-11-09 16:05:22,818 INFO L747 eck$LassoCheckResult]: Loop: 3005#L21-1 call #t~ret5 := f91(#t~ret4);< 3017#$Ultimate##0 ~x := #in~x; 3099#L18 assume !(~x > 100); 3035#L21 call #t~ret4 := f91(11 + ~x);< 3036#$Ultimate##0 ~x := #in~x; 3097#L18 assume ~x > 100;#res := ~x - 10; 3096#f91FINAL assume true; 3095#f91EXIT >#29#return; 3005#L21-1 [2024-11-09 16:05:22,818 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:22,818 INFO L85 PathProgramCache]: Analyzing trace with hash 2083076242, now seen corresponding path program 3 times [2024-11-09 16:05:22,819 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:22,819 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [268694731] [2024-11-09 16:05:22,819 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:22,819 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:22,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:22,909 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-09 16:05:22,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:22,940 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 16:05:22,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:22,942 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 16:05:22,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:22,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-09 16:05:22,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:22,956 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 28 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-09 16:05:22,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 16:05:22,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [268694731] [2024-11-09 16:05:22,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [268694731] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 16:05:22,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [867423614] [2024-11-09 16:05:22,957 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 16:05:22,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 16:05:22,957 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:22,959 INFO L229 MonitoredProcess]: Starting monitored process 26 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:22,961 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Waiting until timeout for monitored process [2024-11-09 16:05:22,997 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-09 16:05:22,998 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 16:05:22,998 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 16:05:22,999 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:23,018 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-09 16:05:23,020 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 16:05:23,020 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [867423614] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 16:05:23,020 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 16:05:23,021 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 9 [2024-11-09 16:05:23,021 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [217603610] [2024-11-09 16:05:23,021 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 16:05:23,021 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 16:05:23,022 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:23,034 INFO L85 PathProgramCache]: Analyzing trace with hash 1767505954, now seen corresponding path program 2 times [2024-11-09 16:05:23,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 16:05:23,035 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1012988934] [2024-11-09 16:05:23,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 16:05:23,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 16:05:23,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:23,039 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 16:05:23,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 16:05:23,042 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 16:05:23,138 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:23,138 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:23,138 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:23,138 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:23,138 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 16:05:23,138 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:23,139 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:23,139 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:23,139 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2024-11-09 16:05:23,139 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:23,139 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:23,140 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:23,141 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:23,150 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:23,183 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:23,183 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 16:05:23,183 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:23,183 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:23,185 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:23,186 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:23,189 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:23,189 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:23,204 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 16:05:23,204 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:23,219 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-11-09 16:05:23,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:23,219 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:23,220 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:23,221 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:23,222 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 16:05:23,222 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:23,254 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:23,255 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:23,255 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:23,256 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:23,257 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:23,258 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 16:05:23,258 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 16:05:35,541 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-11-09 16:05:35,560 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:35,561 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 16:05:35,561 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 16:05:35,561 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 16:05:35,561 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 16:05:35,561 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 16:05:35,561 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:35,561 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 16:05:35,561 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 16:05:35,561 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2024-11-09 16:05:35,561 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 16:05:35,562 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 16:05:35,562 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:35,564 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:35,571 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 16:05:35,599 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 16:05:35,599 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 16:05:35,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:35,600 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:35,602 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:35,606 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:35,606 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:35,619 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:35,619 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:35,619 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:35,619 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:35,619 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:35,620 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:35,620 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:35,621 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 16:05:35,636 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:35,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:35,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:35,638 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:35,640 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:35,641 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:35,653 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 16:05:35,653 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 16:05:35,654 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 16:05:35,654 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 16:05:35,654 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 16:05:35,655 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 16:05:35,655 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 16:05:35,659 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 16:05:35,662 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 16:05:35,663 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 16:05:35,663 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 16:05:35,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 16:05:35,666 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:35,667 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:35,668 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 16:05:35,668 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 16:05:35,668 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 16:05:35,669 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:35,684 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:35,685 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 16:05:35,690 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2024-11-09 16:05:35,701 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:35,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,738 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 16:05:35,740 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:35,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:35,921 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:35,922 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:35,994 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:35,994 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:35,994 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 16:05:36,118 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 139 states and 161 transitions. Complement of second has 24 states. [2024-11-09 16:05:36,119 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:36,119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 16:05:36,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-11-09 16:05:36,120 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2024-11-09 16:05:36,120 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:36,120 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:36,130 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:36,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,167 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 16:05:36,168 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:36,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,336 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:36,337 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:36,376 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:36,448 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:36,448 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:36,449 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 16:05:36,593 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 139 states and 161 transitions. Complement of second has 24 states. [2024-11-09 16:05:36,593 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:36,594 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 16:05:36,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-11-09 16:05:36,594 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2024-11-09 16:05:36,594 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:36,595 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 16:05:36,605 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 16:05:36,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,649 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 16:05:36,651 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:36,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 16:05:36,820 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 16:05:36,821 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 16:05:36,900 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:36,901 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:36,901 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 16:05:37,058 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 181 states and 211 transitions. Complement of second has 27 states. [2024-11-09 16:05:37,059 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:37,060 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, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 16:05:37,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 21 transitions. [2024-11-09 16:05:37,061 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 8 letters. [2024-11-09 16:05:37,061 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:37,061 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 40 letters. Loop has 8 letters. [2024-11-09 16:05:37,061 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:37,062 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 16 letters. [2024-11-09 16:05:37,062 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 16:05:37,062 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 181 states and 211 transitions. [2024-11-09 16:05:37,064 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:37,064 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 181 states to 0 states and 0 transitions. [2024-11-09 16:05:37,064 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:05:37,064 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:05:37,064 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:05:37,065 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:05:37,065 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:37,065 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:37,065 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 16:05:37,065 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 16:05:37,065 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-09 16:05:37,065 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 5 states have internal predecessors, (16), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 16:05:37,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 16:05:37,065 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:37,066 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 16:05:37,066 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 16:05:37,066 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 16:05:37,066 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 16:05:37,066 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 16:05:37,066 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 16:05:37,067 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 16:05:37,067 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 16:05:37,067 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 16:05:37,078 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 04:05:37 BoogieIcfgContainer [2024-11-09 16:05:37,079 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 16:05:37,079 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 16:05:37,079 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 16:05:37,080 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 16:05:37,080 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:37,082 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 16:05:37,083 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 16:05:37,084 INFO L158 Benchmark]: Toolchain (without parser) took 46806.50ms. Allocated memory is still 190.8MB. Free memory was 162.1MB in the beginning and 88.5MB in the end (delta: 73.6MB). Peak memory consumption was 74.0MB. Max. memory is 16.1GB. [2024-11-09 16:05:37,084 INFO L158 Benchmark]: CDTParser took 0.22ms. Allocated memory is still 144.7MB. Free memory is still 102.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:37,084 INFO L158 Benchmark]: CACSL2BoogieTranslator took 287.57ms. Allocated memory is still 190.8MB. Free memory was 162.1MB in the beginning and 149.9MB in the end (delta: 12.2MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-09 16:05:37,085 INFO L158 Benchmark]: Boogie Procedure Inliner took 30.92ms. Allocated memory is still 190.8MB. Free memory was 149.9MB in the beginning and 148.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:37,085 INFO L158 Benchmark]: Boogie Preprocessor took 34.93ms. Allocated memory is still 190.8MB. Free memory was 148.9MB in the beginning and 146.8MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 16:05:37,085 INFO L158 Benchmark]: RCFGBuilder took 252.14ms. Allocated memory is still 190.8MB. Free memory was 146.8MB in the beginning and 136.3MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 16:05:37,085 INFO L158 Benchmark]: BuchiAutomizer took 46188.94ms. Allocated memory is still 190.8MB. Free memory was 136.3MB in the beginning and 88.5MB in the end (delta: 47.8MB). Peak memory consumption was 48.8MB. Max. memory is 16.1GB. [2024-11-09 16:05:37,086 INFO L158 Benchmark]: Witness Printer took 4.11ms. Allocated memory is still 190.8MB. Free memory is still 88.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 16:05:37,087 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.22ms. Allocated memory is still 144.7MB. Free memory is still 102.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 287.57ms. Allocated memory is still 190.8MB. Free memory was 162.1MB in the beginning and 149.9MB in the end (delta: 12.2MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 30.92ms. Allocated memory is still 190.8MB. Free memory was 149.9MB in the beginning and 148.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 34.93ms. Allocated memory is still 190.8MB. Free memory was 148.9MB in the beginning and 146.8MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 252.14ms. Allocated memory is still 190.8MB. Free memory was 146.8MB in the beginning and 136.3MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 46188.94ms. Allocated memory is still 190.8MB. Free memory was 136.3MB in the beginning and 88.5MB in the end (delta: 47.8MB). Peak memory consumption was 48.8MB. Max. memory is 16.1GB. * Witness Printer took 4.11ms. Allocated memory is still 190.8MB. Free memory is still 88.5MB. 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 - 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 8 terminating modules (3 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 21 locations. One nondeterministic module has affine ranking function null and consists of 8 locations. 3 modules have a trivial ranking function, the largest among these consists of 17 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 46.1s and 6 iterations. TraceHistogramMax:7. Analysis of lassos took 40.3s. Construction of modules took 0.6s. Büchi inclusion checks took 4.9s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 65 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, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 12/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 250 SdHoareTripleChecker+Valid, 0.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 235 mSDsluCounter, 402 SdHoareTripleChecker+Invalid, 0.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 232 mSDsCounter, 199 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 821 IncrementalHoareTripleChecker+Invalid, 1020 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 199 mSolverCounterUnsat, 170 mSDtfsCounter, 821 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT2 conc0 concLT2 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital13 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq176 hnf90 smp100 dnf100 smp100 tf110 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 26ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 2 LassoNonterminationAnalysisUnknown: 3 LassoNonterminationAnalysisTime: 37.2s 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:37,116 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Forceful destruction successful, exit code 0 [2024-11-09 16:05:37,312 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:37,513 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