From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
Authors: J.-C. Kassing, F. Frohn, and J. Giesl
There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems. These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool AProVE.
ERRATUM
Theorem 27 and Theorem 38 are incorrect
Theorem 27 claims that for every non-overlapping and right-linear PTRS S, iAST (iPAST) w.r.t. innermost simultaneous rewriting implies fAST (fPAST). Theorem 38 claims the same on basic start terms for every non-overlapping and spare PTRS. Both theorems are false. The same holds for their PAST/SAST versions in App. B of the extended version.
Counterexample
Let s = h(f(a,a)) and let P consist of the rules
h(x) -> {1/2: h1(x), 1/2: h2(x)} a -> {1/2: b, 1/2: c} f(x,x) -> {1: x} h1(b) -> {1: s} h1(c) -> {1: s} h2(f(b,c)) -> {1: d(s,s,s)} h2(f(c,b)) -> {1: e(s,s)}
P is non-overlapping and right-linear, hence also spare.
- P is not fAST, not even on the basic start term h1(b) (which rewrites to s). Under full rewriting, a rewrite strategy can proceed as follows: on h1(f(a,a)), first apply the f-rule; on h2(f(a,a)), first rewrite both a’s separately. Then every copy of s produces 0, 1, 2, or 3 new copies of s with probabilities 1/4, 1/2, 1/8, and 1/8. This is a branching process with mean 9/8 > 1, so it terminates only with probability sqrt(3) - 1 < 1.
- P is iAST, and even iSAST, w.r.t. innermost simultaneous rewriting. In innermost evaluation, the two a’s in f(a,a) have to be rewritten before the f-rule can be applied. If they are rewritten simultaneously, s produces 1/2 new copies of s in expectation; if they are rewritten one after another, it produces 7/8. In both cases, the process is subcritical.
So P refutes Theorem 27 and Theorem 38 for AST, PAST, and SAST. The proofs only work for terms with at most two nested defined symbols.
Consequences
- The claims in Sect. 1 and Sect. 5 that left-linearity can be dropped by using simultaneous rewriting are withdrawn. Def. 24, Cor. 25, Cor. 29, and Counterexamples 26, 28, and 30 are correct, but they are only relevant for the withdrawn theorems.
- Sect. 6 (evaluation): the results that rely on Theorem 27 or Theorem 38 are not supported. These are
- the columns “Thm. 27” (44) and “Thm. 38” (56) of the table and the corresponding part of the diagram;
- the 3 examples that “can only be solved by Thm. 38”, so for basic start terms, 61 drops to 58;
- the increase from 48 to 49 examples for arbitrary start terms, so 49 drops to 48.
- The strategy of AProVE described in Sect. 6 is unsound for PTRSs that are not left-linear.
- All other results are not affected. This includes Theorems 17, 20, 22, and 33 and Lemma 35.
The counterexample is also given in the journal version of the paper, which no longer contains the two theorems: Jan-Christoph Kassing, Jürgen Giesl: “From Innermost to Full Probabilistic Term Rewriting: Almost-Sure Termination, Complexity, and Modularity”. Logical Methods in Computer Science 21(4:28), 2025 (Counterexample 5.5).
Download Paper | Extended Version | Download Slides | Evaluation Website