./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/McCarthy91-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/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.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive/McCarthy91-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 2a5dd5c1c64cd1875ba800cc2db6d1da955f2d2f519c1964ff87558bc42b9b4c --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-17 20:34:58,016 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 20:34:58,078 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-03-17 20:34:58,081 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 20:34:58,081 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 20:34:58,082 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-17 20:34:58,104 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 20:34:58,105 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 20:34:58,106 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 20:34:58,106 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 20:34:58,107 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 20:34:58,107 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 20:34:58,107 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 20:34:58,108 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-17 20:34:58,108 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-17 20:34:58,108 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 20:34:58,109 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 20:34:58,109 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 20:34:58,109 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-17 20:34:58,109 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR 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 [2025-03-17 20:34:58,361 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 20:34:58,366 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 20:34:58,369 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 20:34:58,370 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 20:34:58,370 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 20:34:58,371 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/McCarthy91-2.c [2025-03-17 20:34:59,611 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/59dd80f2b/85e565b7f15643c19df766956ef3db9a/FLAG8a0c0aa00 [2025-03-17 20:34:59,822 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 20:34:59,822 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-2.c [2025-03-17 20:34:59,828 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/59dd80f2b/85e565b7f15643c19df766956ef3db9a/FLAG8a0c0aa00 [2025-03-17 20:34:59,838 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/59dd80f2b/85e565b7f15643c19df766956ef3db9a [2025-03-17 20:34:59,840 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 20:34:59,841 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 20:34:59,842 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 20:34:59,842 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 20:34:59,845 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 20:34:59,845 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:34:59,846 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5ffc96e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59, skipping insertion in model container [2025-03-17 20:34:59,846 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:34:59,856 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 20:34:59,947 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 20:34:59,956 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 20:34:59,963 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 20:34:59,973 INFO L204 MainTranslator]: Completed translation [2025-03-17 20:34:59,974 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59 WrapperNode [2025-03-17 20:34:59,974 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 20:34:59,975 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 20:34:59,975 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 20:34:59,975 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 20:34:59,980 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:34:59,985 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:34:59,996 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2025-03-17 20:34:59,996 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 20:34:59,997 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 20:34:59,997 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 20:34:59,997 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 20:35:00,002 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,002 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,003 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,011 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]. [2025-03-17 20:35:00,011 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,012 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,013 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,014 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,015 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,015 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,016 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 20:35:00,017 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 20:35:00,017 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 20:35:00,017 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 20:35:00,018 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (1/1) ... [2025-03-17 20:35:00,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,042 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) [2025-03-17 20:35:00,044 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 [2025-03-17 20:35:00,065 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-17 20:35:00,065 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 20:35:00,065 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 20:35:00,065 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-17 20:35:00,065 INFO L130 BoogieDeclarations]: Found specification of procedure f91 [2025-03-17 20:35:00,065 INFO L138 BoogieDeclarations]: Found implementation of procedure f91 [2025-03-17 20:35:00,108 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 20:35:00,110 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 20:35:00,179 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L21: havoc #t~ret4;havoc #t~ret5; [2025-03-17 20:35:00,185 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-03-17 20:35:00,186 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 20:35:00,193 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 20:35:00,193 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 20:35:00,194 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:35:00 BoogieIcfgContainer [2025-03-17 20:35:00,194 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 20:35:00,194 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-17 20:35:00,195 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-17 20:35:00,198 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-17 20:35:00,199 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:35:00,199 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.03 08:34:59" (1/3) ... [2025-03-17 20:35:00,199 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6ef18985 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 08:35:00, skipping insertion in model container [2025-03-17 20:35:00,200 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:35:00,200 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:59" (2/3) ... [2025-03-17 20:35:00,200 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6ef18985 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 08:35:00, skipping insertion in model container [2025-03-17 20:35:00,200 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:35:00,200 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:35:00" (3/3) ... [2025-03-17 20:35:00,201 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91-2.c [2025-03-17 20:35:00,232 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-17 20:35:00,232 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-17 20:35:00,232 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-17 20:35:00,232 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-17 20:35:00,232 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-17 20:35:00,232 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-17 20:35:00,232 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-17 20:35:00,233 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-17 20:35:00,236 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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) [2025-03-17 20:35:00,248 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:35:00,248 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:00,248 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:00,251 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 20:35:00,251 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 20:35:00,252 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-17 20:35:00,252 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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) [2025-03-17 20:35:00,252 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:35:00,253 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:00,253 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:00,253 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 20:35:00,253 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 20:35:00,256 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< [2025-03-17 20:35:00,256 INFO L754 eck$LassoCheckResult]: Loop: "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< [2025-03-17 20:35:00,259 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,260 INFO L85 PathProgramCache]: Analyzing trace with hash 1163, now seen corresponding path program 1 times [2025-03-17 20:35:00,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:00,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [391428707] [2025-03-17 20:35:00,265 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:00,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:00,312 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:35:00,324 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:35:00,324 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,324 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:00,324 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:00,329 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:35:00,334 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:35:00,336 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,337 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:00,346 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:00,348 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,349 INFO L85 PathProgramCache]: Analyzing trace with hash 43668, now seen corresponding path program 1 times [2025-03-17 20:35:00,349 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:00,349 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2061891059] [2025-03-17 20:35:00,349 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:00,349 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:00,353 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:00,357 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:00,357 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,357 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:00,357 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:00,358 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:00,359 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:00,359 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,359 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:00,360 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:00,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,361 INFO L85 PathProgramCache]: Analyzing trace with hash 34660810, now seen corresponding path program 1 times [2025-03-17 20:35:00,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:00,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1419584761] [2025-03-17 20:35:00,362 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:00,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:00,365 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-03-17 20:35:00,368 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-03-17 20:35:00,368 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,368 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:00,368 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:00,370 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-03-17 20:35:00,372 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-03-17 20:35:00,372 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,372 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:00,374 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:00,466 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:00,466 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:00,466 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:00,467 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:00,467 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:00,467 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,467 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:00,467 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:00,467 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2025-03-17 20:35:00,467 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:00,467 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:00,480 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,487 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,498 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,502 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,504 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,541 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:00,542 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:00,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,543 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,546 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) [2025-03-17 20:35:00,548 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 [2025-03-17 20:35:00,550 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,550 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,565 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,565 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:00,574 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:00,575 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,575 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,577 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) [2025-03-17 20:35:00,578 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 [2025-03-17 20:35:00,579 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,579 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,596 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 [2025-03-17 20:35:00,596 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,598 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) [2025-03-17 20:35:00,600 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 [2025-03-17 20:35:00,602 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:00,602 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,734 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:00,740 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 [2025-03-17 20:35:00,740 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:00,740 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:00,740 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:00,740 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:00,740 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:00,740 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,740 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:00,740 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:00,740 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2025-03-17 20:35:00,740 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:00,740 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:00,742 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,745 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,752 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,755 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,759 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,793 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:00,796 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:00,797 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,799 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) [2025-03-17 20:35:00,802 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 [2025-03-17 20:35:00,804 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 [2025-03-17 20:35:00,816 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,816 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,816 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,816 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,817 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,819 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,819 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,821 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:00,827 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 [2025-03-17 20:35:00,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,829 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) [2025-03-17 20:35:00,830 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 [2025-03-17 20:35:00,832 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 [2025-03-17 20:35:00,843 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,843 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,843 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,843 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,843 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,844 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,844 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,849 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:00,853 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:00,856 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:00,857 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,857 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,859 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 20:35:00,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-03-17 20:35:00,860 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:00,860 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:00,860 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:00,861 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -2*f91_#in~x + 211 Supporting invariants [] [2025-03-17 20:35:00,866 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2025-03-17 20:35:00,869 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:00,901 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,912 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:35:00,923 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:35:00,923 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,923 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,925 INFO L256 TraceCheckSpWp]: Trace formula consists of 53 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,926 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,935 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:00,940 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:00,940 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,940 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,940 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,941 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,972 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:00,995 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 [2025-03-17 20:35:00,996 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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.0) internal successors, (3), 3 states have internal predecessors, (3), 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) [2025-03-17 20:35:01,064 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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.0) internal successors, (3), 3 states have internal predecessors, (3), 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 32 states and 40 transitions. Complement of second has 16 states. [2025-03-17 20:35:01,065 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 [2025-03-17 20:35:01,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 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) [2025-03-17 20:35:01,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 7 transitions. [2025-03-17 20:35:01,072 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 3 letters. [2025-03-17 20:35:01,072 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,072 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 5 letters. Loop has 3 letters. [2025-03-17 20:35:01,072 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,072 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 6 letters. [2025-03-17 20:35:01,072 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,073 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 40 transitions. [2025-03-17 20:35:01,074 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:35:01,077 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 18 states and 24 transitions. [2025-03-17 20:35:01,077 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2025-03-17 20:35:01,077 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 13 [2025-03-17 20:35:01,078 INFO L73 IsDeterministic]: Start isDeterministic. Operand 18 states and 24 transitions. [2025-03-17 20:35:01,078 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:01,079 INFO L218 hiAutomatonCegarLoop]: Abstraction has 18 states and 24 transitions. [2025-03-17 20:35:01,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states and 24 transitions. [2025-03-17 20:35:01,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 16. [2025-03-17 20:35:01,095 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 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) [2025-03-17 20:35:01,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 20 transitions. [2025-03-17 20:35:01,096 INFO L240 hiAutomatonCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-03-17 20:35:01,096 INFO L432 stractBuchiCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-03-17 20:35:01,096 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-17 20:35:01,096 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 16 states and 20 transitions. [2025-03-17 20:35:01,097 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:35:01,097 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:01,097 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:01,097 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:01,097 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:01,099 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" [2025-03-17 20:35:01,099 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" [2025-03-17 20:35:01,100 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,100 INFO L85 PathProgramCache]: Analyzing trace with hash -404919830, now seen corresponding path program 1 times [2025-03-17 20:35:01,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2135378221] [2025-03-17 20:35:01,100 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:01,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,107 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:35:01,112 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:35:01,112 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,112 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,112 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:01,114 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:35:01,117 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:35:01,117 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,117 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,119 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:01,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,119 INFO L85 PathProgramCache]: Analyzing trace with hash -570415228, now seen corresponding path program 1 times [2025-03-17 20:35:01,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,120 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [819789130] [2025-03-17 20:35:01,120 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:01,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,123 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:01,125 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:01,125 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,125 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,125 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:01,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:01,134 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:01,134 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,134 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,135 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:01,136 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,136 INFO L85 PathProgramCache]: Analyzing trace with hash -1666344851, now seen corresponding path program 1 times [2025-03-17 20:35:01,136 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,136 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1671627550] [2025-03-17 20:35:01,136 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:01,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,141 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-17 20:35:01,161 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-17 20:35:01,163 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,163 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,163 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:01,165 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-17 20:35:01,173 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:01,176 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-17 20:35:01,176 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,176 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,181 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:01,299 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:01,299 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:01,299 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:01,299 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:01,299 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:01,299 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,299 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:01,299 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:01,299 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2025-03-17 20:35:01,299 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:01,299 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:01,300 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,302 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,304 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,343 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:01,343 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:01,343 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,343 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,345 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) [2025-03-17 20:35:01,346 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 [2025-03-17 20:35:01,348 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:01,348 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:01,359 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:01,359 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#t~ret5=0} Honda state: {f91_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:01,366 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 [2025-03-17 20:35:01,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,368 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) [2025-03-17 20:35:01,369 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 [2025-03-17 20:35:01,370 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:01,370 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:01,380 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:01,381 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:01,387 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 [2025-03-17 20:35:01,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,388 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,389 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) [2025-03-17 20:35:01,391 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 [2025-03-17 20:35:01,392 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:01,392 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:01,421 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:01,422 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,423 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) [2025-03-17 20:35:01,424 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 [2025-03-17 20:35:01,425 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:01,425 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:02,003 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:02,017 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2025-03-17 20:35:02,018 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:02,018 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:02,018 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:02,018 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:02,018 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:02,018 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,018 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:02,018 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:02,018 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2025-03-17 20:35:02,018 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:02,018 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:02,019 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,029 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,031 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,075 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:02,075 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:02,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,075 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,077 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) [2025-03-17 20:35:02,078 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 [2025-03-17 20:35:02,079 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 [2025-03-17 20:35:02,089 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:02,089 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:02,089 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:02,089 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:02,089 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:02,091 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:02,091 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:02,093 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:02,097 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:02,097 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:02,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,098 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,099 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) [2025-03-17 20:35:02,101 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 [2025-03-17 20:35:02,102 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:02,102 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:02,102 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:02,102 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2025-03-17 20:35:02,108 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 [2025-03-17 20:35:02,109 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:02,110 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2025-03-17 20:35:02,120 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:35:02,141 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:35:02,141 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,141 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,142 INFO L256 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,143 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,206 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:02,217 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:02,217 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,217 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,219 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,220 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,314 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:02,314 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 [2025-03-17 20:35:02,315 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 16 states and 20 transitions. cyclomatic complexity: 6 Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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) [2025-03-17 20:35:02,461 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 16 states and 20 transitions. cyclomatic complexity: 6. Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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 50 states and 72 transitions. Complement of second has 32 states. [2025-03-17 20:35:02,461 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 [2025-03-17 20:35:02,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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) [2025-03-17 20:35:02,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 20:35:02,463 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 8 letters. [2025-03-17 20:35:02,463 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,464 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 17 letters. Loop has 8 letters. [2025-03-17 20:35:02,464 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,464 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 16 letters. [2025-03-17 20:35:02,464 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,464 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 50 states and 72 transitions. [2025-03-17 20:35:02,466 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-17 20:35:02,469 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 50 states to 41 states and 61 transitions. [2025-03-17 20:35:02,469 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-03-17 20:35:02,469 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 26 [2025-03-17 20:35:02,469 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 61 transitions. [2025-03-17 20:35:02,469 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:02,469 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 61 transitions. [2025-03-17 20:35:02,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 61 transitions. [2025-03-17 20:35:02,473 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 35. [2025-03-17 20:35:02,473 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 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) [2025-03-17 20:35:02,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 50 transitions. [2025-03-17 20:35:02,474 INFO L240 hiAutomatonCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-03-17 20:35:02,474 INFO L432 stractBuchiCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-03-17 20:35:02,474 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-17 20:35:02,474 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 35 states and 50 transitions. [2025-03-17 20:35:02,475 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-17 20:35:02,475 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:02,475 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:02,475 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:02,475 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 20:35:02,478 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" [2025-03-17 20:35:02,478 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" [2025-03-17 20:35:02,479 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,479 INFO L85 PathProgramCache]: Analyzing trace with hash 1596496679, now seen corresponding path program 2 times [2025-03-17 20:35:02,479 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,479 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346428904] [2025-03-17 20:35:02,479 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:02,479 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,485 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 12 statements into 2 equivalence classes. [2025-03-17 20:35:02,495 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:02,495 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:02,495 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,495 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:02,496 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:02,500 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:02,500 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,500 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,501 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:02,501 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,501 INFO L85 PathProgramCache]: Analyzing trace with hash 49458, now seen corresponding path program 2 times [2025-03-17 20:35:02,501 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1735338730] [2025-03-17 20:35:02,501 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:02,501 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,503 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:02,503 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:02,503 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-17 20:35:02,503 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,503 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:02,504 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:02,504 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:02,504 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,504 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,509 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:02,509 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,510 INFO L85 PathProgramCache]: Analyzing trace with hash -1235252148, now seen corresponding path program 3 times [2025-03-17 20:35:02,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,510 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [444648643] [2025-03-17 20:35:02,510 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:02,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,513 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 15 statements into 4 equivalence classes. [2025-03-17 20:35:02,518 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 15 of 15 statements. [2025-03-17 20:35:02,519 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-17 20:35:02,519 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,634 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-17 20:35:02,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:02,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [444648643] [2025-03-17 20:35:02,635 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [444648643] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 20:35:02,635 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 20:35:02,635 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-17 20:35:02,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [933094782] [2025-03-17 20:35:02,636 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 20:35:02,684 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:02,684 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:02,684 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:02,684 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:02,684 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:02,684 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,684 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:02,684 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:02,684 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2025-03-17 20:35:02,684 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:02,684 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:02,685 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,694 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,707 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:02,759 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 [2025-03-17 20:35:02,796 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:02,796 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:02,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,798 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) [2025-03-17 20:35:02,800 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 [2025-03-17 20:35:02,802 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:02,802 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:02,828 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 [2025-03-17 20:35:02,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:02,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,830 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) [2025-03-17 20:35:02,831 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 [2025-03-17 20:35:02,832 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:02,832 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:03,176 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:03,187 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2025-03-17 20:35:03,188 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:03,188 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:03,188 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:03,188 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:03,188 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:03,188 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,188 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:03,188 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:03,188 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2025-03-17 20:35:03,188 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:03,188 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:03,189 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,190 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,196 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,198 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,228 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:03,228 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:03,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,228 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,230 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) [2025-03-17 20:35:03,232 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 [2025-03-17 20:35:03,232 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 [2025-03-17 20:35:03,243 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:03,243 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:03,243 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:03,243 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:03,243 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:03,243 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:03,243 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:03,244 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:03,250 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2025-03-17 20:35:03,250 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,250 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,252 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) [2025-03-17 20:35:03,252 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 [2025-03-17 20:35:03,253 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-17 20:35:03,264 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:03,264 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:03,264 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:03,264 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:03,264 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:03,266 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:03,266 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:03,268 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:03,270 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:03,270 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:03,270 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,270 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,271 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) [2025-03-17 20:35:03,272 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 [2025-03-17 20:35:03,273 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:03,273 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:03,273 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:03,273 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_~x) = -2*f91_~x + 189 Supporting invariants [] [2025-03-17 20:35:03,279 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 [2025-03-17 20:35:03,279 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:03,293 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,298 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:03,309 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:03,309 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,309 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,310 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,311 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,359 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:03,362 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:03,362 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,362 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,363 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,364 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,381 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:03,383 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 [2025-03-17 20:35:03,383 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,432 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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 42 states and 58 transitions. Complement of second has 13 states. [2025-03-17 20:35:03,433 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 [2025-03-17 20:35:03,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 20:35:03,433 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 20:35:03,433 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,433 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:03,440 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,446 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:03,456 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:03,456 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,456 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,456 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,457 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,521 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:03,525 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:03,525 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,525 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,526 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,526 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,549 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:03,550 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 [2025-03-17 20:35:03,550 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,598 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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 42 states and 58 transitions. Complement of second has 13 states. [2025-03-17 20:35:03,601 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 [2025-03-17 20:35:03,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 20:35:03,602 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 20:35:03,602 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,602 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:03,609 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,619 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:03,630 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:03,630 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,630 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,631 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,631 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,679 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:03,683 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:03,683 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,683 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,683 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,684 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,701 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:03,702 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 [2025-03-17 20:35:03,702 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,765 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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 70 states and 99 transitions. Complement of second has 16 states. [2025-03-17 20:35:03,767 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 [2025-03-17 20:35:03,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2025-03-17 20:35:03,769 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 20:35:03,769 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,769 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 15 letters. Loop has 3 letters. [2025-03-17 20:35:03,769 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,769 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 6 letters. [2025-03-17 20:35:03,769 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,769 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 70 states and 99 transitions. [2025-03-17 20:35:03,772 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-03-17 20:35:03,773 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 70 states to 47 states and 73 transitions. [2025-03-17 20:35:03,773 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-03-17 20:35:03,774 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-03-17 20:35:03,774 INFO L73 IsDeterministic]: Start isDeterministic. Operand 47 states and 73 transitions. [2025-03-17 20:35:03,774 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:03,774 INFO L218 hiAutomatonCegarLoop]: Abstraction has 47 states and 73 transitions. [2025-03-17 20:35:03,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states and 73 transitions. [2025-03-17 20:35:03,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 41. [2025-03-17 20:35:03,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 25 states have (on average 1.04) internal successors, (26), 25 states have internal predecessors, (26), 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) [2025-03-17 20:35:03,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 59 transitions. [2025-03-17 20:35:03,777 INFO L240 hiAutomatonCegarLoop]: Abstraction has 41 states and 59 transitions. [2025-03-17 20:35:03,777 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:03,778 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-17 20:35:03,779 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-17 20:35:03,779 INFO L87 Difference]: Start difference. First operand 41 states and 59 transitions. Second operand has 8 states, 6 states have (on average 1.5) internal successors, (9), 5 states have internal predecessors, (9), 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) [2025-03-17 20:35:03,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:03,858 INFO L93 Difference]: Finished difference Result 62 states and 81 transitions. [2025-03-17 20:35:03,858 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 62 states and 81 transitions. [2025-03-17 20:35:03,860 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 20:35:03,861 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 62 states to 57 states and 74 transitions. [2025-03-17 20:35:03,861 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2025-03-17 20:35:03,861 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 41 [2025-03-17 20:35:03,861 INFO L73 IsDeterministic]: Start isDeterministic. Operand 57 states and 74 transitions. [2025-03-17 20:35:03,861 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:03,861 INFO L218 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-17 20:35:03,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states and 74 transitions. [2025-03-17 20:35:03,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2025-03-17 20:35:03,864 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 34 states have (on average 1.0588235294117647) internal successors, (36), 36 states have internal predecessors, (36), 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) [2025-03-17 20:35:03,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2025-03-17 20:35:03,864 INFO L240 hiAutomatonCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-03-17 20:35:03,864 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-17 20:35:03,865 INFO L432 stractBuchiCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-03-17 20:35:03,865 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-17 20:35:03,865 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 56 states and 73 transitions. [2025-03-17 20:35:03,866 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 20:35:03,866 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:03,866 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:03,866 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2025-03-17 20:35:03,866 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-03-17 20:35:03,867 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#19#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< [2025-03-17 20:35:03,867 INFO L754 eck$LassoCheckResult]: Loop: "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#19#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< [2025-03-17 20:35:03,867 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,867 INFO L85 PathProgramCache]: Analyzing trace with hash 1221193575, now seen corresponding path program 1 times [2025-03-17 20:35:03,867 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:03,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1111325319] [2025-03-17 20:35:03,867 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:03,867 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:03,870 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:03,873 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:03,873 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,873 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:03,873 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:03,874 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:03,882 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:03,882 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,882 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:03,885 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:03,888 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,889 INFO L85 PathProgramCache]: Analyzing trace with hash -466426831, now seen corresponding path program 1 times [2025-03-17 20:35:03,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:03,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [92266650] [2025-03-17 20:35:03,889 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:03,889 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:03,891 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:03,897 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:03,898 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,898 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:03,898 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:03,902 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:03,905 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:03,905 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,905 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:03,908 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:03,909 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,909 INFO L85 PathProgramCache]: Analyzing trace with hash 1315438347, now seen corresponding path program 2 times [2025-03-17 20:35:03,909 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:03,909 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1287299649] [2025-03-17 20:35:03,909 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:03,909 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:03,923 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-17 20:35:03,935 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-03-17 20:35:03,935 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-17 20:35:03,937 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:03,937 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,043 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-17 20:35:04,044 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:04,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1287299649] [2025-03-17 20:35:04,044 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1287299649] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:35:04,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1272987268] [2025-03-17 20:35:04,044 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:04,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:35:04,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,046 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 20:35:04,046 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-17 20:35:04,069 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-17 20:35:04,079 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-17 20:35:04,080 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:04,080 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,080 INFO L256 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,082 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,115 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-17 20:35:04,115 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 20:35:04,302 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-17 20:35:04,302 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1272987268] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 20:35:04,302 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 20:35:04,302 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-03-17 20:35:04,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2130330752] [2025-03-17 20:35:04,302 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 20:35:04,433 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:04,433 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:04,433 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:04,433 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:04,433 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:04,433 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,433 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:04,433 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:04,433 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2025-03-17 20:35:04,433 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:04,433 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:04,433 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,438 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,440 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,441 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,443 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,462 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:04,462 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:04,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,464 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) [2025-03-17 20:35:04,466 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 [2025-03-17 20:35:04,467 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:04,467 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:04,490 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 [2025-03-17 20:35:04,490 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,492 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 20:35:04,493 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2025-03-17 20:35:04,495 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:04,495 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:04,506 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:04,513 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:04,513 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:04,513 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:04,513 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:04,513 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:04,513 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:04,513 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,513 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:04,513 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:04,513 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2025-03-17 20:35:04,513 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:04,513 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:04,514 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,519 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,520 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,521 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,523 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:04,540 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:04,541 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:04,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,543 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) [2025-03-17 20:35:04,544 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 [2025-03-17 20:35:04,545 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 [2025-03-17 20:35:04,555 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:04,555 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:04,556 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:04,556 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:04,556 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:04,557 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:04,557 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:04,558 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:04,560 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:04,561 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:04,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:04,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:04,585 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) [2025-03-17 20:35:04,586 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 [2025-03-17 20:35:04,587 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:04,587 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:04,587 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:04,587 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -1*f91_#in~x + 90 Supporting invariants [] [2025-03-17 20:35:04,593 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 [2025-03-17 20:35:04,594 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:04,603 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:04,613 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:04,631 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:04,632 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,632 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,633 INFO L256 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,634 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,713 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 [2025-03-17 20:35:04,784 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:04,796 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:04,796 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,796 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,797 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,798 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,968 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-17 20:35:04,969 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 [2025-03-17 20:35:04,970 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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) [2025-03-17 20:35:05,261 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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 124 states and 149 transitions. Complement of second has 49 states. [2025-03-17 20:35:05,262 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 [2025-03-17 20:35:05,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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) [2025-03-17 20:35:05,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-03-17 20:35:05,263 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 20:35:05,263 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,263 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:05,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:05,309 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:05,334 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:05,334 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:05,334 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:05,335 INFO L256 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:35:05,336 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:05,465 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:05,478 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:05,478 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:05,478 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:05,479 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 20:35:05,480 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:05,635 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-17 20:35:05,635 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 10 loop predicates [2025-03-17 20:35:05,635 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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) [2025-03-17 20:35:05,890 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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 124 states and 149 transitions. Complement of second has 49 states. [2025-03-17 20:35:05,891 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 [2025-03-17 20:35:05,891 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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) [2025-03-17 20:35:05,892 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-03-17 20:35:05,892 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 20:35:05,892 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,892 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:05,905 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:05,912 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:05,926 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:05,926 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:05,926 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:05,927 INFO L256 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:35:05,928 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:06,028 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:06,039 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:06,039 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:06,039 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:06,042 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 20:35:06,043 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:06,186 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-17 20:35:06,187 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 [2025-03-17 20:35:06,187 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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) [2025-03-17 20:35:06,705 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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 430 states and 530 transitions. Complement of second has 224 states. [2025-03-17 20:35:06,706 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 [2025-03-17 20:35:06,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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) [2025-03-17 20:35:06,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 49 transitions. [2025-03-17 20:35:06,707 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 49 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 20:35:06,708 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:06,708 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 49 transitions. Stem has 40 letters. Loop has 19 letters. [2025-03-17 20:35:06,708 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:06,708 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 49 transitions. Stem has 21 letters. Loop has 38 letters. [2025-03-17 20:35:06,709 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:06,709 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 430 states and 530 transitions. [2025-03-17 20:35:06,720 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 29 [2025-03-17 20:35:06,727 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 430 states to 202 states and 268 transitions. [2025-03-17 20:35:06,727 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 94 [2025-03-17 20:35:06,728 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 105 [2025-03-17 20:35:06,729 INFO L73 IsDeterministic]: Start isDeterministic. Operand 202 states and 268 transitions. [2025-03-17 20:35:06,729 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:06,729 INFO L218 hiAutomatonCegarLoop]: Abstraction has 202 states and 268 transitions. [2025-03-17 20:35:06,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states and 268 transitions. [2025-03-17 20:35:06,742 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 156. [2025-03-17 20:35:06,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 96 states have (on average 1.09375) internal successors, (105), 98 states have internal predecessors, (105), 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) [2025-03-17 20:35:06,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 197 transitions. [2025-03-17 20:35:06,747 INFO L240 hiAutomatonCegarLoop]: Abstraction has 156 states and 197 transitions. [2025-03-17 20:35:06,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:06,748 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-17 20:35:06,748 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-03-17 20:35:06,748 INFO L87 Difference]: Start difference. First operand 156 states and 197 transitions. Second operand has 15 states, 12 states have (on average 1.75) internal successors, (21), 8 states have internal predecessors, (21), 7 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 7 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-17 20:35:06,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:06,897 INFO L93 Difference]: Finished difference Result 158 states and 187 transitions. [2025-03-17 20:35:06,897 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 158 states and 187 transitions. [2025-03-17 20:35:06,899 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2025-03-17 20:35:06,900 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 158 states to 103 states and 122 transitions. [2025-03-17 20:35:06,900 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 75 [2025-03-17 20:35:06,900 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 75 [2025-03-17 20:35:06,900 INFO L73 IsDeterministic]: Start isDeterministic. Operand 103 states and 122 transitions. [2025-03-17 20:35:06,900 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:06,900 INFO L218 hiAutomatonCegarLoop]: Abstraction has 103 states and 122 transitions. [2025-03-17 20:35:06,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states and 122 transitions. [2025-03-17 20:35:06,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 99. [2025-03-17 20:35:06,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 62 states have (on average 1.0483870967741935) internal successors, (65), 63 states have internal predecessors, (65), 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) [2025-03-17 20:35:06,905 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 118 transitions. [2025-03-17 20:35:06,905 INFO L240 hiAutomatonCegarLoop]: Abstraction has 99 states and 118 transitions. [2025-03-17 20:35:06,907 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-17 20:35:06,907 INFO L432 stractBuchiCegarLoop]: Abstraction has 99 states and 118 transitions. [2025-03-17 20:35:06,907 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-17 20:35:06,907 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 99 states and 118 transitions. [2025-03-17 20:35:06,908 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2025-03-17 20:35:06,908 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:06,908 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:06,909 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1] [2025-03-17 20:35:06,909 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:06,909 INFO L752 eck$LassoCheckResult]: Stem: "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);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;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#19#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" [2025-03-17 20:35:06,909 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#21#return;" [2025-03-17 20:35:06,909 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:06,909 INFO L85 PathProgramCache]: Analyzing trace with hash 158007207, now seen corresponding path program 3 times [2025-03-17 20:35:06,909 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:06,909 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1705767480] [2025-03-17 20:35:06,909 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:06,909 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:06,912 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 31 statements into 7 equivalence classes. [2025-03-17 20:35:06,916 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 26 of 31 statements. [2025-03-17 20:35:06,916 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-17 20:35:06,916 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:07,003 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 28 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-17 20:35:07,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:07,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1705767480] [2025-03-17 20:35:07,003 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1705767480] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:35:07,004 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1395018647] [2025-03-17 20:35:07,004 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:07,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:35:07,004 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,007 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-17 20:35:07,008 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2025-03-17 20:35:07,029 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 31 statements into 7 equivalence classes. [2025-03-17 20:35:07,039 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 26 of 31 statements. [2025-03-17 20:35:07,039 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-17 20:35:07,039 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:07,040 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 20:35:07,041 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:07,066 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-17 20:35:07,066 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 20:35:07,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1395018647] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 20:35:07,066 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 20:35:07,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 9 [2025-03-17 20:35:07,067 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1838801383] [2025-03-17 20:35:07,067 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 20:35:07,067 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:35:07,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:07,067 INFO L85 PathProgramCache]: Analyzing trace with hash -570415228, now seen corresponding path program 2 times [2025-03-17 20:35:07,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:07,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [747169853] [2025-03-17 20:35:07,067 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:07,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:07,069 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-03-17 20:35:07,071 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:07,072 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:07,072 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:07,072 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:07,072 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:07,075 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:07,075 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:07,075 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:07,076 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:07,154 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:07,154 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:07,155 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:07,155 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:07,155 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:07,155 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,155 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:07,155 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:07,155 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2025-03-17 20:35:07,155 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:07,155 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:07,155 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:07,156 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:07,162 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:07,180 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:07,181 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:07,181 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,181 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,185 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) [2025-03-17 20:35:07,185 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 [2025-03-17 20:35:07,187 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:07,187 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:07,197 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:07,197 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:07,203 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-03-17 20:35:07,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,203 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,204 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-17 20:35:07,205 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-03-17 20:35:07,207 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:07,207 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:07,239 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2025-03-17 20:35:07,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,241 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) [2025-03-17 20:35:07,242 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 [2025-03-17 20:35:07,243 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:07,243 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:07,847 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:07,866 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 [2025-03-17 20:35:07,866 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:07,866 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:07,866 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:07,866 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:07,866 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:07,866 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,866 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:07,866 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:07,866 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2025-03-17 20:35:07,866 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:07,866 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:07,867 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:07,871 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:07,873 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:07,899 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:07,899 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:07,899 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,901 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) [2025-03-17 20:35:07,901 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 [2025-03-17 20:35:07,902 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 [2025-03-17 20:35:07,912 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:07,912 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:07,912 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:07,912 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:07,912 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:07,913 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:07,913 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:07,914 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:07,920 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 [2025-03-17 20:35:07,920 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,920 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,921 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) [2025-03-17 20:35:07,922 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 [2025-03-17 20:35:07,923 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 [2025-03-17 20:35:07,932 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:07,933 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:07,933 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:07,933 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:07,933 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:07,933 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:07,933 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:07,934 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:07,939 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2025-03-17 20:35:07,940 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,940 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,941 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) [2025-03-17 20:35:07,942 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 [2025-03-17 20:35:07,943 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 [2025-03-17 20:35:07,953 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:07,953 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:07,953 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:07,953 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:07,953 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:07,955 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:07,955 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:07,957 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:07,959 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:07,959 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:07,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:07,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:07,961 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) [2025-03-17 20:35:07,962 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 [2025-03-17 20:35:07,963 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:07,963 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:07,963 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:07,963 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2025-03-17 20:35:07,969 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2025-03-17 20:35:07,970 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:07,971 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2025-03-17 20:35:07,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:07,991 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:08,012 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:08,013 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:08,013 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:08,013 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 20:35:08,014 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:08,134 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 [2025-03-17 20:35:08,151 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:08,158 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:08,158 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:08,158 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:08,159 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:08,159 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:08,216 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:08,216 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 [2025-03-17 20:35:08,217 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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) [2025-03-17 20:35:08,316 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 138 states and 160 transitions. Complement of second has 24 states. [2025-03-17 20:35:08,317 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 [2025-03-17 20:35:08,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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) [2025-03-17 20:35:08,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 20:35:08,319 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 31 letters. Loop has 8 letters. [2025-03-17 20:35:08,319 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:08,319 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:08,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:08,337 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:08,357 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:08,357 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:08,357 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:08,358 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 20:35:08,359 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:08,470 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:08,475 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:08,476 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:08,476 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:08,476 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:08,477 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:08,538 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:08,539 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 [2025-03-17 20:35:08,539 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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) [2025-03-17 20:35:08,649 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 138 states and 160 transitions. Complement of second has 24 states. [2025-03-17 20:35:08,651 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 [2025-03-17 20:35:08,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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) [2025-03-17 20:35:08,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 20:35:08,651 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 31 letters. Loop has 8 letters. [2025-03-17 20:35:08,651 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:08,651 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:08,660 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:08,668 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:08,687 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:08,687 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:08,687 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:08,688 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 20:35:08,689 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:08,818 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:08,824 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:08,825 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:08,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:08,825 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:08,826 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:08,877 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-17 20:35:08,878 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 [2025-03-17 20:35:08,878 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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) [2025-03-17 20:35:08,971 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 180 states and 210 transitions. Complement of second has 27 states. [2025-03-17 20:35:08,975 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 [2025-03-17 20:35:08,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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) [2025-03-17 20:35:08,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 20 transitions. [2025-03-17 20:35:08,976 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 20 transitions. Stem has 31 letters. Loop has 8 letters. [2025-03-17 20:35:08,976 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:08,976 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 20 transitions. Stem has 39 letters. Loop has 8 letters. [2025-03-17 20:35:08,976 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:08,976 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 20 transitions. Stem has 31 letters. Loop has 16 letters. [2025-03-17 20:35:08,977 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:08,977 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 180 states and 210 transitions. [2025-03-17 20:35:08,978 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:08,978 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 180 states to 0 states and 0 transitions. [2025-03-17 20:35:08,978 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 20:35:08,978 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 20:35:08,978 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 20:35:08,978 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 20:35:08,978 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:08,978 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:08,979 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-17 20:35:08,979 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-17 20:35:08,979 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 5 states have internal predecessors, (15), 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) [2025-03-17 20:35:08,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:08,979 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:08,979 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 20:35:08,979 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 20:35:08,979 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 20:35:08,979 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-17 20:35:08,979 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-17 20:35:08,979 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-17 20:35:08,979 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:08,979 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-17 20:35:08,986 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.03 08:35:08 BoogieIcfgContainer [2025-03-17 20:35:08,986 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-17 20:35:08,986 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-17 20:35:08,987 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-17 20:35:08,987 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-17 20:35:08,987 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:35:00" (3/4) ... [2025-03-17 20:35:08,989 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-17 20:35:08,989 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-17 20:35:08,990 INFO L158 Benchmark]: Toolchain (without parser) took 9148.81ms. Allocated memory is still 142.6MB. Free memory was 109.8MB in the beginning and 70.2MB in the end (delta: 39.7MB). Peak memory consumption was 44.4MB. Max. memory is 16.1GB. [2025-03-17 20:35:08,990 INFO L158 Benchmark]: CDTParser took 0.23ms. Allocated memory is still 201.3MB. Free memory is still 127.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:08,991 INFO L158 Benchmark]: CACSL2BoogieTranslator took 132.67ms. Allocated memory is still 142.6MB. Free memory was 109.8MB in the beginning and 99.7MB in the end (delta: 10.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 20:35:08,991 INFO L158 Benchmark]: Boogie Procedure Inliner took 21.36ms. Allocated memory is still 142.6MB. Free memory was 99.7MB in the beginning and 98.8MB in the end (delta: 949.9kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:08,991 INFO L158 Benchmark]: Boogie Preprocessor took 19.67ms. Allocated memory is still 142.6MB. Free memory was 98.8MB in the beginning and 97.9MB in the end (delta: 896.5kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:08,991 INFO L158 Benchmark]: IcfgBuilder took 176.63ms. Allocated memory is still 142.6MB. Free memory was 97.9MB in the beginning and 87.6MB in the end (delta: 10.3MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-17 20:35:08,992 INFO L158 Benchmark]: BuchiAutomizer took 8791.50ms. Allocated memory is still 142.6MB. Free memory was 87.6MB in the beginning and 70.2MB in the end (delta: 17.4MB). Peak memory consumption was 10.9MB. Max. memory is 16.1GB. [2025-03-17 20:35:08,992 INFO L158 Benchmark]: Witness Printer took 2.82ms. Allocated memory is still 142.6MB. Free memory was 70.2MB in the beginning and 70.2MB in the end (delta: 41.6kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 20:35:08,993 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.23ms. Allocated memory is still 201.3MB. Free memory is still 127.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 132.67ms. Allocated memory is still 142.6MB. Free memory was 109.8MB in the beginning and 99.7MB in the end (delta: 10.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 21.36ms. Allocated memory is still 142.6MB. Free memory was 99.7MB in the beginning and 98.8MB in the end (delta: 949.9kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 19.67ms. Allocated memory is still 142.6MB. Free memory was 98.8MB in the beginning and 97.9MB in the end (delta: 896.5kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 176.63ms. Allocated memory is still 142.6MB. Free memory was 97.9MB in the beginning and 87.6MB in the end (delta: 10.3MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * BuchiAutomizer took 8791.50ms. Allocated memory is still 142.6MB. Free memory was 87.6MB in the beginning and 70.2MB in the end (delta: 17.4MB). Peak memory consumption was 10.9MB. Max. memory is 16.1GB. * Witness Printer took 2.82ms. Allocated memory is still 142.6MB. Free memory was 70.2MB in the beginning and 70.2MB in the end (delta: 41.6kB). Peak memory consumption was 8.4MB. 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 15 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.7s and 6 iterations. TraceHistogramMax:7. Analysis of lassos took 4.2s. Construction of modules took 0.5s. Büchi inclusion checks took 3.8s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 6. Automata minimization 0.0s 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, 251 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 238 mSDsluCounter, 371 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 212 mSDsCounter, 202 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 808 IncrementalHoareTripleChecker+Invalid, 1010 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 202 mSolverCounterUnsat, 159 mSDtfsCounter, 808 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: 24ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.9s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-17 20:35:09,007 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:09,210 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:09,411 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