./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/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-tmp.dk.eval-mul-div-a046e57-m [2024-10-13 17:41:25,734 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-13 17:41:25,788 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-13 17:41:25,792 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-13 17:41:25,792 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-13 17:41:25,813 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-13 17:41:25,814 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-13 17:41:25,814 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-13 17:41:25,814 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-13 17:41:25,815 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-13 17:41:25,815 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-13 17:41:25,815 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-13 17:41:25,816 INFO L153 SettingsManager]: * Use SBE=true [2024-10-13 17:41:25,816 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-13 17:41:25,816 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-13 17:41:25,816 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-13 17:41:25,817 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-13 17:41:25,817 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-13 17:41:25,817 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-13 17:41:25,818 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-13 17:41:25,818 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-13 17:41:25,818 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-13 17:41:25,819 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-13 17:41:25,819 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-13 17:41:25,819 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-13 17:41:25,820 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-13 17:41:25,820 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-13 17:41:25,820 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-13 17:41:25,820 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-13 17:41:25,821 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-13 17:41:25,821 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-13 17:41:25,821 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-13 17:41:25,821 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-13 17:41:25,822 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-13 17:41:25,822 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-13 17:41:25,822 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-13 17:41:25,822 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-13 17:41:25,823 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-13 17:41:25,823 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-13 17:41:25,823 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-10-13 17:41:26,025 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-13 17:41:26,050 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-13 17:41:26,056 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-13 17:41:26,057 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-13 17:41:26,061 INFO L274 PluginConnector]: CDTParser initialized [2024-10-13 17:41:26,062 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-2.c [2024-10-13 17:41:27,530 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-13 17:41:27,680 INFO L384 CDTParser]: Found 1 translation units. [2024-10-13 17:41:27,681 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-2.c [2024-10-13 17:41:27,688 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b520aff28/c2095715a7f64a63b7623f1203a03420/FLAG19ce15d67 [2024-10-13 17:41:28,080 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b520aff28/c2095715a7f64a63b7623f1203a03420 [2024-10-13 17:41:28,082 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-13 17:41:28,083 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-13 17:41:28,085 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:28,085 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-13 17:41:28,089 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-13 17:41:28,091 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,091 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@23b4f25b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28, skipping insertion in model container [2024-10-13 17:41:28,092 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,111 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-13 17:41:28,366 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:28,375 INFO L200 MainTranslator]: Completed pre-run [2024-10-13 17:41:28,384 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:28,396 INFO L204 MainTranslator]: Completed translation [2024-10-13 17:41:28,396 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28 WrapperNode [2024-10-13 17:41:28,396 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:28,398 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:28,398 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-13 17:41:28,398 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-13 17:41:28,403 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,407 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,421 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2024-10-13 17:41:28,421 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:28,421 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-13 17:41:28,422 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-13 17:41:28,422 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-13 17:41:28,431 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,431 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,432 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,439 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-10-13 17:41:28,439 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,440 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,441 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,442 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,443 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,443 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,444 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-13 17:41:28,445 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-13 17:41:28,445 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-13 17:41:28,445 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-13 17:41:28,446 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (1/1) ... [2024-10-13 17:41:28,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:28,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:28,475 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:28,480 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-10-13 17:41:28,512 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-13 17:41:28,512 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-13 17:41:28,513 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-13 17:41:28,513 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-13 17:41:28,513 INFO L130 BoogieDeclarations]: Found specification of procedure f91 [2024-10-13 17:41:28,513 INFO L138 BoogieDeclarations]: Found implementation of procedure f91 [2024-10-13 17:41:28,569 INFO L238 CfgBuilder]: Building ICFG [2024-10-13 17:41:28,570 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-13 17:41:28,659 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-10-13 17:41:28,659 INFO L287 CfgBuilder]: Performing block encoding [2024-10-13 17:41:28,674 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-13 17:41:28,675 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-13 17:41:28,675 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:28 BoogieIcfgContainer [2024-10-13 17:41:28,679 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-13 17:41:28,680 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-13 17:41:28,680 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-13 17:41:28,684 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-13 17:41:28,686 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:28,688 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 13.10 05:41:28" (1/3) ... [2024-10-13 17:41:28,689 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@2bcaa5a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:28, skipping insertion in model container [2024-10-13 17:41:28,689 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:28,689 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:28" (2/3) ... [2024-10-13 17:41:28,689 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@2bcaa5a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:28, skipping insertion in model container [2024-10-13 17:41:28,690 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:28,690 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:28" (3/3) ... [2024-10-13 17:41:28,692 INFO L332 chiAutomizerObserver]: Analyzing ICFG McCarthy91-2.c [2024-10-13 17:41:28,790 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-13 17:41:28,790 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-13 17:41:28,790 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-13 17:41:28,791 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-13 17:41:28,792 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-13 17:41:28,792 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-13 17:41:28,796 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-13 17:41:28,796 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-13 17:41:28,801 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-10-13 17:41:28,835 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-13 17:41:28,835 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:28,836 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:28,840 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:28,844 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-13 17:41:28,844 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-13 17:41:28,845 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-10-13 17:41:28,851 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-13 17:41:28,851 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:28,851 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:28,851 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:28,851 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-13 17:41:28,863 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-10-13 17:41:28,867 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-10-13 17:41:28,877 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:28,877 INFO L85 PathProgramCache]: Analyzing trace with hash 29879, now seen corresponding path program 1 times [2024-10-13 17:41:28,897 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:28,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [211556186] [2024-10-13 17:41:28,898 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:28,898 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:29,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:29,052 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:29,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:29,095 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:29,099 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:29,103 INFO L85 PathProgramCache]: Analyzing trace with hash 46807, now seen corresponding path program 1 times [2024-10-13 17:41:29,103 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:29,104 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1613698607] [2024-10-13 17:41:29,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:29,104 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:29,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:29,120 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:29,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:29,130 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:29,131 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:29,131 INFO L85 PathProgramCache]: Analyzing trace with hash 890142305, now seen corresponding path program 1 times [2024-10-13 17:41:29,132 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:29,133 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [3527199] [2024-10-13 17:41:29,133 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:29,133 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:29,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:29,154 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:29,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:29,169 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:29,328 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:29,328 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:29,328 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:29,328 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:29,328 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:29,328 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,329 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:29,329 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:29,329 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2024-10-13 17:41:29,329 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:29,329 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:29,344 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,357 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,372 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,380 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,383 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,445 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:29,445 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:29,447 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,450 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,452 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:29,464 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-10-13 17:41:29,466 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,466 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,481 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:29,481 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:29,492 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-10-13 17:41:29,493 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,495 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:29,496 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-10-13 17:41:29,497 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:29,497 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,534 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-10-13 17:41:29,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,535 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:29,537 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:29,538 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-10-13 17:41:29,539 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:29,539 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:29,928 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:29,934 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-10-13 17:41:29,935 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:29,935 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:29,935 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:29,939 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:29,939 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:29,939 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:29,939 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:29,939 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:29,940 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2024-10-13 17:41:29,940 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:29,940 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:29,941 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,944 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,955 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,961 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:29,964 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,024 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:30,031 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:30,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,032 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,034 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,036 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-10-13 17:41:30,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-10-13 17:41:30,048 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:30,049 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:30,049 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:30,049 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:30,049 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:30,051 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:30,051 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:30,053 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:30,065 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-10-13 17:41:30,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,069 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-10-13 17:41:30,075 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:30,086 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:30,086 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:30,086 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:30,086 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:30,087 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:30,087 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:30,087 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:30,091 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:30,095 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:30,096 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:30,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,104 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,105 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-10-13 17:41:30,106 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:30,106 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:30,106 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:30,107 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -2*f91_#in~x + 211 Supporting invariants [] [2024-10-13 17:41:30,117 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:30,123 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:30,160 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,192 INFO L255 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-13 17:41:30,193 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:30,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:30,219 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:30,219 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:30,278 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:30,325 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-10-13 17:41:30,327 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-10-13 17:41:30,417 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-10-13 17:41:30,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:30,423 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-10-13 17:41:30,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2024-10-13 17:41:30,424 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2024-10-13 17:41:30,425 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,425 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2024-10-13 17:41:30,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,426 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2024-10-13 17:41:30,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:30,426 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 35 states and 43 transitions. [2024-10-13 17:41:30,429 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-13 17:41:30,432 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 35 states to 19 states and 25 transitions. [2024-10-13 17:41:30,433 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2024-10-13 17:41:30,433 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2024-10-13 17:41:30,433 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2024-10-13 17:41:30,434 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:30,434 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2024-10-13 17:41:30,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2024-10-13 17:41:30,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-10-13 17:41:30,453 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-10-13 17:41:30,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-10-13 17:41:30,455 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-10-13 17:41:30,455 INFO L425 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-10-13 17:41:30,455 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-13 17:41:30,455 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2024-10-13 17:41:30,456 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-10-13 17:41:30,456 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:30,456 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:30,457 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:30,457 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:30,457 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-10-13 17:41:30,457 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-10-13 17:41:30,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,458 INFO L85 PathProgramCache]: Analyzing trace with hash -218206616, now seen corresponding path program 1 times [2024-10-13 17:41:30,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [713411447] [2024-10-13 17:41:30,458 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,466 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:30,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,474 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:30,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,474 INFO L85 PathProgramCache]: Analyzing trace with hash 1767505954, now seen corresponding path program 1 times [2024-10-13 17:41:30,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001521225] [2024-10-13 17:41:30,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,480 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:30,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,484 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:30,485 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:30,485 INFO L85 PathProgramCache]: Analyzing trace with hash -1919740023, now seen corresponding path program 1 times [2024-10-13 17:41:30,485 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:30,485 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971097375] [2024-10-13 17:41:30,485 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:30,486 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:30,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,496 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:30,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:30,506 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:30,655 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:30,656 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:30,656 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:30,656 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:30,656 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:30,656 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,656 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:30,656 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:30,656 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2024-10-13 17:41:30,656 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:30,656 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:30,657 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,662 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,664 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:30,705 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:30,707 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:30,707 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,708 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,713 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-10-13 17:41:30,714 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:30,714 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:30,725 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:30,726 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-10-13 17:41:30,736 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:30,737 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,738 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,739 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-10-13 17:41:30,741 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:30,743 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:30,755 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:30,755 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:30,767 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-10-13 17:41:30,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,769 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,776 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-10-13 17:41:30,778 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:30,778 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:30,815 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-10-13 17:41:30,816 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:30,816 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:30,818 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:30,819 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-10-13 17:41:30,820 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:30,820 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:34,475 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-13 17:41:43,075 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-10-13 17:41:43,093 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:43,093 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:43,093 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:43,093 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:43,094 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:43,094 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:43,094 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,094 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:43,094 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:43,094 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2024-10-13 17:41:43,094 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:43,094 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:43,095 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,101 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,103 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,166 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:43,166 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:43,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:43,169 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:43,174 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-10-13 17:41:43,175 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:43,186 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:43,187 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:43,187 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:43,187 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:43,187 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:43,188 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:43,188 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:43,190 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:43,215 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:43,216 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:43,219 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:43,224 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:43,225 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-10-13 17:41:43,235 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:43,235 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:43,235 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:43,236 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:43,236 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:43,237 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:43,237 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:43,239 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:43,249 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:43,250 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,250 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:43,253 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:43,262 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-10-13 17:41:43,266 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:43,284 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:43,284 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:43,285 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:43,285 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:43,285 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:43,287 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:43,287 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:43,290 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:43,293 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:43,294 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:43,294 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,294 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:43,305 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:43,313 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-10-13 17:41:43,314 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:43,314 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:43,314 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:43,314 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2024-10-13 17:41:43,326 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:43,327 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:43,331 WARN L953 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2024-10-13 17:41:43,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:43,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:43,378 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:43,379 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:43,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:43,462 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-13 17:41:43,463 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:43,560 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:43,561 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-10-13 17:41:43,562 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-10-13 17:41:43,708 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-10-13 17:41:43,710 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-10-13 17:41:43,711 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-10-13 17:41:43,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-10-13 17:41:43,713 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2024-10-13 17:41:43,713 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:43,714 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2024-10-13 17:41:43,714 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:43,714 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2024-10-13 17:41:43,714 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:43,715 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2024-10-13 17:41:43,718 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-10-13 17:41:43,721 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2024-10-13 17:41:43,721 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-10-13 17:41:43,721 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2024-10-13 17:41:43,721 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2024-10-13 17:41:43,722 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:43,722 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2024-10-13 17:41:43,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2024-10-13 17:41:43,725 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2024-10-13 17:41:43,725 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-10-13 17:41:43,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2024-10-13 17:41:43,726 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-10-13 17:41:43,726 INFO L425 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2024-10-13 17:41:43,726 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-13 17:41:43,726 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2024-10-13 17:41:43,728 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2024-10-13 17:41:43,728 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:43,728 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:43,729 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:43,729 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-10-13 17:41:43,729 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-10-13 17:41:43,729 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-10-13 17:41:43,729 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:43,729 INFO L85 PathProgramCache]: Analyzing trace with hash 1987218266, now seen corresponding path program 2 times [2024-10-13 17:41:43,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:43,729 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [478356908] [2024-10-13 17:41:43,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:43,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:43,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:43,746 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:43,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:43,756 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:43,756 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:43,756 INFO L85 PathProgramCache]: Analyzing trace with hash 57247, now seen corresponding path program 2 times [2024-10-13 17:41:43,756 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:43,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1877368949] [2024-10-13 17:41:43,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:43,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:43,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:43,759 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:43,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:43,760 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:43,761 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:43,761 INFO L85 PathProgramCache]: Analyzing trace with hash -609818202, now seen corresponding path program 3 times [2024-10-13 17:41:43,761 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:43,761 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1183174935] [2024-10-13 17:41:43,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:43,761 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:43,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:43,855 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-13 17:41:43,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:43,876 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-13 17:41:43,876 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:43,876 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1183174935] [2024-10-13 17:41:43,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1183174935] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:43,877 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:43,877 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-13 17:41:43,877 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [690470878] [2024-10-13 17:41:43,879 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:43,934 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:43,934 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:43,934 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:43,934 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:43,934 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:43,934 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,934 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:43,934 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:43,934 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2024-10-13 17:41:43,934 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:43,934 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:43,935 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,944 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,946 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,947 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:43,982 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:43,982 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:43,982 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:43,982 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:43,987 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:43,992 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-10-13 17:41:43,993 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:43,993 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:44,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:44,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:44,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:44,043 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:44,044 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-10-13 17:41:44,045 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:44,045 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:56,079 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-10-13 17:41:56,088 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-13 17:41:56,089 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:56,089 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:56,089 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:56,089 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:56,089 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:56,089 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:56,089 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:56,089 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:56,090 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2024-10-13 17:41:56,090 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:56,090 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:56,090 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:56,092 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:56,097 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:56,098 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:56,126 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:56,126 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:56,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:56,127 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:56,128 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:56,133 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-10-13 17:41:56,136 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:56,146 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:56,146 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:56,146 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:56,146 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:56,146 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:56,147 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:56,147 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:56,148 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:56,158 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:56,159 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:56,159 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:56,160 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:56,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-10-13 17:41:56,164 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:56,174 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:56,175 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:56,175 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:56,175 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:56,175 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:56,177 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:56,177 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:56,179 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:56,183 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:56,183 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:56,183 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:56,183 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:56,189 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:56,205 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-10-13 17:41:56,206 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:56,206 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:56,206 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:56,206 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_~x) = -2*f91_~x + 189 Supporting invariants [] [2024-10-13 17:41:56,217 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-10-13 17:41:56,222 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:56,252 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:56,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,325 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,326 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,430 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,430 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,451 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:56,452 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-13 17:41:56,452 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-10-13 17:41:56,504 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-10-13 17:41:56,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:56,507 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-10-13 17:41:56,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-13 17:41:56,508 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-10-13 17:41:56,508 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,508 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:56,542 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:56,554 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:56,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,565 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,566 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,573 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:56,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,627 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,628 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,648 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:56,649 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-13 17:41:56,649 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-10-13 17:41:56,691 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-10-13 17:41:56,691 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:56,692 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-10-13 17:41:56,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-13 17:41:56,692 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2024-10-13 17:41:56,693 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,693 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:56,703 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:56,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,724 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,724 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,772 INFO L255 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,773 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,792 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:56,792 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-13 17:41:56,792 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-10-13 17:41:56,844 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-10-13 17:41:56,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:56,845 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-10-13 17:41:56,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2024-10-13 17:41:56,846 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2024-10-13 17:41:56,846 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,846 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2024-10-13 17:41:56,846 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,846 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2024-10-13 17:41:56,847 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,847 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2024-10-13 17:41:56,849 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2024-10-13 17:41:56,850 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2024-10-13 17:41:56,850 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-10-13 17:41:56,850 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-10-13 17:41:56,851 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2024-10-13 17:41:56,851 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:56,851 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2024-10-13 17:41:56,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2024-10-13 17:41:56,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2024-10-13 17:41:56,854 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-10-13 17:41:56,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2024-10-13 17:41:56,855 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2024-10-13 17:41:56,855 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:56,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-13 17:41:56,857 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-10-13 17:41:56,858 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-10-13 17:41:56,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:56,930 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2024-10-13 17:41:56,930 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2024-10-13 17:41:56,932 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-10-13 17:41:56,933 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2024-10-13 17:41:56,934 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2024-10-13 17:41:56,934 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2024-10-13 17:41:56,934 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2024-10-13 17:41:56,934 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:56,934 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-10-13 17:41:56,934 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2024-10-13 17:41:56,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-10-13 17:41:56,938 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-10-13 17:41:56,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-10-13 17:41:56,938 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-10-13 17:41:56,939 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-13 17:41:56,939 INFO L425 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-10-13 17:41:56,939 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-13 17:41:56,940 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2024-10-13 17:41:56,940 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2024-10-13 17:41:56,940 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:56,941 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:56,941 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-10-13 17:41:56,942 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-10-13 17:41:56,942 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-10-13 17:41:56,942 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-10-13 17:41:56,942 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:56,942 INFO L85 PathProgramCache]: Analyzing trace with hash -834951989, now seen corresponding path program 1 times [2024-10-13 17:41:56,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:56,943 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642830048] [2024-10-13 17:41:56,943 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:56,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:56,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:56,961 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:56,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:56,972 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:56,976 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:56,976 INFO L85 PathProgramCache]: Analyzing trace with hash -871747263, now seen corresponding path program 1 times [2024-10-13 17:41:56,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:56,977 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1149977840] [2024-10-13 17:41:56,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:56,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:56,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:56,985 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:56,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:56,994 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:56,997 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:56,997 INFO L85 PathProgramCache]: Analyzing trace with hash 418853943, now seen corresponding path program 2 times [2024-10-13 17:41:56,998 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:56,998 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1706187773] [2024-10-13 17:41:56,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:56,998 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:57,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,105 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-13 17:41:57,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,147 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-13 17:41:57,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,152 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-13 17:41:57,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,164 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-13 17:41:57,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,211 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-13 17:41:57,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,215 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-13 17:41:57,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,218 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-13 17:41:57,219 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:57,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1706187773] [2024-10-13 17:41:57,219 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1706187773] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:57,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2091627939] [2024-10-13 17:41:57,219 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-13 17:41:57,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:57,220 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:57,224 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-10-13 17:41:57,228 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-10-13 17:41:57,265 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-13 17:41:57,265 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:57,267 INFO L255 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-13 17:41:57,268 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:57,300 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-13 17:41:57,300 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:57,466 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-13 17:41:57,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2091627939] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:57,466 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:57,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 17 [2024-10-13 17:41:57,467 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1316059306] [2024-10-13 17:41:57,467 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:57,582 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:57,583 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:57,583 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:57,583 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:57,583 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:57,583 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:57,583 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:57,583 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:57,583 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2024-10-13 17:41:57,583 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:57,583 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:57,584 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,587 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,589 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,590 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,592 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,610 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:57,610 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:57,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:57,611 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:57,612 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:57,613 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-10-13 17:41:57,614 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:57,614 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:57,641 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-10-13 17:41:57,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:57,642 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:57,643 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:57,644 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-10-13 17:41:57,645 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:57,645 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:57,656 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:57,669 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-10-13 17:41:57,669 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:57,670 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:57,670 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:57,670 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:57,670 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:57,670 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:57,670 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:57,670 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:57,670 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2024-10-13 17:41:57,670 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:57,670 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:57,670 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,675 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,676 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,678 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,679 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:57,697 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:57,697 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:57,697 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:57,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:57,698 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:57,701 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-10-13 17:41:57,702 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:57,711 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:57,712 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:57,712 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:57,712 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:57,712 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:57,716 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:57,716 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:57,718 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:57,719 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:57,719 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:57,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:57,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:57,721 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:57,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-10-13 17:41:57,722 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:57,722 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:57,723 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:57,723 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -1*f91_#in~x + 90 Supporting invariants [] [2024-10-13 17:41:57,733 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:57,734 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:57,747 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:57,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,778 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:57,780 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:57,881 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:57,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:57,960 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-13 17:41:57,961 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:58,101 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-13 17:41:58,102 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-10-13 17:41:58,102 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-10-13 17:41:58,352 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-10-13 17:41:58,353 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-10-13 17:41:58,353 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-10-13 17:41:58,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 35 transitions. [2024-10-13 17:41:58,354 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-10-13 17:41:58,354 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:58,354 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:58,362 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:58,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:58,384 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:58,385 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:58,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:58,507 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-10-13 17:41:58,508 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:58,628 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:58,628 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-10-13 17:41:58,629 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-10-13 17:41:58,849 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-10-13 17:41:58,849 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-10-13 17:41:58,850 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-10-13 17:41:58,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2024-10-13 17:41:58,850 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 14 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2024-10-13 17:41:58,850 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:58,850 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:58,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:58,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:58,883 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:58,884 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:58,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:58,998 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-13 17:41:58,999 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:59,185 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-13 17:41:59,186 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-10-13 17:41:59,186 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-10-13 17:41:59,853 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-10-13 17:41:59,853 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-10-13 17:41:59,854 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-10-13 17:41:59,854 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 50 transitions. [2024-10-13 17:41:59,854 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2024-10-13 17:41:59,855 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:59,855 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2024-10-13 17:41:59,855 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:59,855 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2024-10-13 17:41:59,856 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:59,856 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 431 states and 531 transitions. [2024-10-13 17:41:59,873 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 29 [2024-10-13 17:41:59,878 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 431 states to 203 states and 269 transitions. [2024-10-13 17:41:59,878 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 95 [2024-10-13 17:41:59,882 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 106 [2024-10-13 17:41:59,882 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 269 transitions. [2024-10-13 17:41:59,883 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:59,883 INFO L218 hiAutomatonCegarLoop]: Abstraction has 203 states and 269 transitions. [2024-10-13 17:41:59,883 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 269 transitions. [2024-10-13 17:41:59,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 157. [2024-10-13 17:41:59,900 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-10-13 17:41:59,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 198 transitions. [2024-10-13 17:41:59,905 INFO L240 hiAutomatonCegarLoop]: Abstraction has 157 states and 198 transitions. [2024-10-13 17:41:59,905 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:59,906 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-13 17:41:59,906 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=228, Unknown=0, NotChecked=0, Total=272 [2024-10-13 17:41:59,906 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-10-13 17:42:00,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:42:00,321 INFO L93 Difference]: Finished difference Result 159 states and 188 transitions. [2024-10-13 17:42:00,321 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 159 states and 188 transitions. [2024-10-13 17:42:00,323 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-10-13 17:42:00,330 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 159 states to 104 states and 123 transitions. [2024-10-13 17:42:00,330 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2024-10-13 17:42:00,330 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-13 17:42:00,330 INFO L73 IsDeterministic]: Start isDeterministic. Operand 104 states and 123 transitions. [2024-10-13 17:42:00,331 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:42:00,331 INFO L218 hiAutomatonCegarLoop]: Abstraction has 104 states and 123 transitions. [2024-10-13 17:42:00,331 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states and 123 transitions. [2024-10-13 17:42:00,341 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 100. [2024-10-13 17:42:00,341 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-10-13 17:42:00,342 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 119 transitions. [2024-10-13 17:42:00,346 INFO L240 hiAutomatonCegarLoop]: Abstraction has 100 states and 119 transitions. [2024-10-13 17:42:00,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-13 17:42:00,348 INFO L425 stractBuchiCegarLoop]: Abstraction has 100 states and 119 transitions. [2024-10-13 17:42:00,348 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-13 17:42:00,348 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 100 states and 119 transitions. [2024-10-13 17:42:00,350 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-10-13 17:42:00,350 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:42:00,350 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:42:00,351 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1] [2024-10-13 17:42:00,351 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2024-10-13 17:42:00,351 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-10-13 17:42:00,351 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-10-13 17:42:00,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:00,352 INFO L85 PathProgramCache]: Analyzing trace with hash 2083076242, now seen corresponding path program 3 times [2024-10-13 17:42:00,352 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:00,352 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1088433662] [2024-10-13 17:42:00,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:00,352 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:00,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:00,399 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-13 17:42:00,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:00,417 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-13 17:42:00,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:00,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-13 17:42:00,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:00,429 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-13 17:42:00,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:00,431 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 28 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-13 17:42:00,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:42:00,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1088433662] [2024-10-13 17:42:00,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1088433662] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:42:00,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1414905627] [2024-10-13 17:42:00,431 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-13 17:42:00,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:42:00,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:00,436 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-10-13 17:42:00,437 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-10-13 17:42:00,481 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-10-13 17:42:00,481 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:42:00,482 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-13 17:42:00,483 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:00,500 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-13 17:42:00,500 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-13 17:42:00,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1414905627] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:42:00,500 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-13 17:42:00,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 9 [2024-10-13 17:42:00,501 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [768849751] [2024-10-13 17:42:00,501 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:42:00,501 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:42:00,501 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:00,501 INFO L85 PathProgramCache]: Analyzing trace with hash 1767505954, now seen corresponding path program 2 times [2024-10-13 17:42:00,501 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:42:00,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [8460060] [2024-10-13 17:42:00,502 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:42:00,502 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:42:00,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:00,504 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:42:00,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:42:00,506 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:42:00,576 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:00,576 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:00,576 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:00,576 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:00,576 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:42:00,576 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:00,576 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:00,576 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:00,576 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2024-10-13 17:42:00,577 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:00,577 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:00,577 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:00,579 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:00,585 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:00,610 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:00,610 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:42:00,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:00,610 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:00,612 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:00,613 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-10-13 17:42:00,613 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:00,613 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:00,624 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:42:00,625 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:42:00,635 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:00,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:00,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:00,637 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:00,638 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-10-13 17:42:00,638 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:42:00,638 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:00,669 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-10-13 17:42:00,670 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:00,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:00,671 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:00,672 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-10-13 17:42:00,672 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:42:00,672 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:42:12,711 INFO L403 LassoAnalysis]: Proving nontermination failed: SMT Solver returned 'unknown'. [2024-10-13 17:42:12,720 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:12,721 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:42:12,721 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:42:12,721 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:42:12,721 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:42:12,721 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:42:12,721 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:12,721 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:42:12,721 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:42:12,721 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2024-10-13 17:42:12,721 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:42:12,721 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:42:12,722 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:12,724 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:12,731 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:42:12,755 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:42:12,755 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:42:12,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:12,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:12,756 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-10-13 17:42:12,757 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-10-13 17:42:12,758 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:12,768 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:12,768 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:12,769 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:12,769 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:12,769 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:12,769 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:12,769 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:12,770 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:42:12,781 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:12,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:12,782 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:12,783 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-10-13 17:42:12,784 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-10-13 17:42:12,784 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:42:12,795 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:42:12,795 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:42:12,795 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:42:12,795 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:42:12,795 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:42:12,796 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:42:12,796 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:42:12,799 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:42:12,802 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:42:12,802 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:42:12,802 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:42:12,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:42:12,810 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:42:12,814 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-10-13 17:42:12,815 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:42:12,815 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:42:12,815 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:42:12,815 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2024-10-13 17:42:12,829 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-10-13 17:42:12,830 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:42:12,834 WARN L953 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2024-10-13 17:42:12,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:12,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:12,880 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-13 17:42:12,881 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:12,999 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-10-13 17:42:13,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:13,047 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-13 17:42:13,047 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:13,108 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:13,108 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-10-13 17:42:13,108 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-10-13 17:42:13,221 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-10-13 17:42:13,222 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-10-13 17:42:13,223 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-10-13 17:42:13,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-10-13 17:42:13,223 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2024-10-13 17:42:13,224 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:13,224 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:42:13,232 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:13,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:13,266 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-13 17:42:13,267 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:13,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:13,386 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-13 17:42:13,386 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:13,444 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:13,445 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-10-13 17:42:13,445 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-10-13 17:42:13,549 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-10-13 17:42:13,550 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-10-13 17:42:13,550 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-10-13 17:42:13,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2024-10-13 17:42:13,550 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2024-10-13 17:42:13,551 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:13,551 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:42:13,558 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:42:13,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:13,586 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-13 17:42:13,587 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:13,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:42:13,706 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-13 17:42:13,706 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:42:13,761 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:42:13,762 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-10-13 17:42:13,762 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-10-13 17:42:13,878 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-10-13 17:42:13,878 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-10-13 17:42:13,878 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-10-13 17:42:13,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 21 transitions. [2024-10-13 17:42:13,879 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 8 letters. [2024-10-13 17:42:13,879 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:13,879 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 40 letters. Loop has 8 letters. [2024-10-13 17:42:13,879 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:13,880 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 16 letters. [2024-10-13 17:42:13,880 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:42:13,880 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 181 states and 211 transitions. [2024-10-13 17:42:13,881 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:42:13,881 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 181 states to 0 states and 0 transitions. [2024-10-13 17:42:13,881 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-13 17:42:13,881 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-13 17:42:13,881 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-13 17:42:13,881 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-13 17:42:13,881 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,882 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,882 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:42:13,882 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-13 17:42:13,882 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-13 17:42:13,882 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-10-13 17:42:13,882 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:42:13,882 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2024-10-13 17:42:13,882 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2024-10-13 17:42:13,882 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:42:13,883 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2024-10-13 17:42:13,883 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-13 17:42:13,883 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-13 17:42:13,883 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-13 17:42:13,883 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-13 17:42:13,883 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,883 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,883 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-13 17:42:13,883 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:42:13,883 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-13 17:42:13,883 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-13 17:42:13,884 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:42:13,884 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-13 17:42:13,889 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 13.10 05:42:13 BoogieIcfgContainer [2024-10-13 17:42:13,889 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-13 17:42:13,889 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-13 17:42:13,889 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-13 17:42:13,890 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-13 17:42:13,890 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:28" (3/4) ... [2024-10-13 17:42:13,891 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-13 17:42:13,892 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-13 17:42:13,892 INFO L158 Benchmark]: Toolchain (without parser) took 45809.03ms. Allocated memory was 172.0MB in the beginning and 270.5MB in the end (delta: 98.6MB). Free memory was 103.9MB in the beginning and 106.7MB in the end (delta: -2.8MB). Peak memory consumption was 97.7MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,893 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 172.0MB. Free memory was 131.1MB in the beginning and 130.9MB in the end (delta: 160.8kB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:42:13,893 INFO L158 Benchmark]: CACSL2BoogieTranslator took 311.85ms. Allocated memory is still 172.0MB. Free memory was 103.7MB in the beginning and 142.4MB in the end (delta: -38.6MB). Peak memory consumption was 11.9MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,893 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.51ms. Allocated memory is still 172.0MB. Free memory was 142.4MB in the beginning and 141.2MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,893 INFO L158 Benchmark]: Boogie Preprocessor took 22.98ms. Allocated memory is still 172.0MB. Free memory was 141.2MB in the beginning and 140.0MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:42:13,893 INFO L158 Benchmark]: RCFGBuilder took 234.13ms. Allocated memory is still 172.0MB. Free memory was 139.1MB in the beginning and 129.9MB in the end (delta: 9.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,894 INFO L158 Benchmark]: BuchiAutomizer took 45209.26ms. Allocated memory was 172.0MB in the beginning and 270.5MB in the end (delta: 98.6MB). Free memory was 129.9MB in the beginning and 107.7MB in the end (delta: 22.2MB). Peak memory consumption was 123.5MB. Max. memory is 16.1GB. [2024-10-13 17:42:13,894 INFO L158 Benchmark]: Witness Printer took 2.57ms. Allocated memory is still 270.5MB. Free memory was 107.7MB in the beginning and 106.7MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:42:13,895 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.11ms. Allocated memory is still 172.0MB. Free memory was 131.1MB in the beginning and 130.9MB in the end (delta: 160.8kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 311.85ms. Allocated memory is still 172.0MB. Free memory was 103.7MB in the beginning and 142.4MB in the end (delta: -38.6MB). Peak memory consumption was 11.9MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.51ms. Allocated memory is still 172.0MB. Free memory was 142.4MB in the beginning and 141.2MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 22.98ms. Allocated memory is still 172.0MB. Free memory was 141.2MB in the beginning and 140.0MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 234.13ms. Allocated memory is still 172.0MB. Free memory was 139.1MB in the beginning and 129.9MB in the end (delta: 9.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 45209.26ms. Allocated memory was 172.0MB in the beginning and 270.5MB in the end (delta: 98.6MB). Free memory was 129.9MB in the beginning and 107.7MB in the end (delta: 22.2MB). Peak memory consumption was 123.5MB. Max. memory is 16.1GB. * Witness Printer took 2.57ms. Allocated memory is still 270.5MB. Free memory was 107.7MB in the beginning and 106.7MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret4 - 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 45.1s and 6 iterations. TraceHistogramMax:7. Analysis of lassos took 39.9s. Construction of modules took 0.6s. Büchi inclusion checks took 4.3s. 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: 20ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 2 LassoNonterminationAnalysisUnknown: 3 LassoNonterminationAnalysisTime: 37.0s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-13 17:42:13,913 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Ended with exit code 0 [2024-10-13 17:42:14,114 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-10-13 17:42:14,315 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE