Are decreasing diagrams complete for confluence of transition systems?

What the completeness question actually asks

Confluence, also called the Church–Rosser property, says that two finite computations starting from the same state can always be joined at a common reduct. The decreasing diagrams technique of van Oostrom reduces this global property to a local one: a system is confluent whenever its one-step relation admits a locally decreasing labeling, in which each local peak is joined by a diagram whose steps decrease in a well-founded order.

Completeness asks the converse: does every confluent transition system admit such a labeling? Van Oostrom posed this in 1993, and it became Problem 56 of the RTA List of Open Problems. Before this paper, a positive answer was known only for countable systems, and more recently up to the first uncountable cardinal aleph 1. The general case remained open.

Three labels suffice at every cardinality

The main theorem states that every confluent abstract rewriting system is decreasing Church–Rosser over the label order {0,1,2} with the usual less-than relation. The result carries no cardinality restriction, so it applies to countable systems, to systems of size aleph 1, and to systems far larger than the continuum.

The proof proceeds component by component. Countable components are handled by a two-label lemma. Uncountable almost regular components are handled by a fan construction. The remaining singular case, where the cofinality cardinal of the relation is singular, is handled by a double-fan construction that produces a cofinal, connected, confluent, locally almost deterministic subsystem.

Why two labels cannot be enough

The three-label bound is optimal. Two labels do not suffice even at the first uncountable cardinality, a fact established earlier by Ivanov and cited here as the matching lower bound. So the paper's contribution is not merely that some finite labeling exists, but that the smallest number of labels that works in general is exactly three.

This distinction matters because the countable case is genuinely easier: for countable systems, two labels already suffice. The gap between two and three labels opens only once uncountable systems are admitted, which is precisely the regime the paper is built to cover.

Almost deterministic subsystems do the work

The central mechanism is the existence, in every confluent abstract rewriting system of arbitrarily high cardinality, of a cofinal, connected, confluent, locally almost deterministic subsystem. An almost deterministic rewrite sequence contains at most one non-deterministic step, so it makes at most one genuine choice; this is exactly what a two-label decreasing diagram can absorb.

The paper describes this subsystem as a rewrite strategy. The proof builds it, shows it is cofinal in the original system, and then uses it to construct a locally decreasing labeling of the rewrite steps. The authors note that this generalizes Klop's cofinal reductions beyond the countable case.

Confluence now matches termination

The paper frames the result as putting confluence on the same footing as termination. For termination, complete-in-principle criteria have long existed: a term rewriting system terminates if and only if it is compatible with a well-founded monotone algebra, and the dependency-pair framework gives a complete characterization as well. For confluence, no comparably complete method was known before this work.

The compact corollary is that the Church–Rosser and decreasing Church–Rosser properties are equivalent. In the authors' reading, decreasing diagrams forfeit no power as a confluence criterion, because every confluent system is provably confluent by this single method. The same equivalence transfers to de Bruijn's weak diamond property, which is equal in strength to decreasing diagrams.

Real-number systems without extra assumptions

Because completeness holds at every cardinality, it holds in particular for systems whose states are real numbers, and it does so unconditionally, independent of the Continuum Hypothesis. The paper states this as a separate corollary, since the reals are the cardinality of greatest practical interest.

This matters for the earlier state of the art. Ivanov's bound reached the continuum only under the Continuum Hypothesis; without it, the cardinality of the reals may lie arbitrarily far up the hierarchy of alephs. The paper's unconditional treatment therefore covers real-valued systems that the previous bound could not reach without a set-theoretic assumption.

What the proof does not deliver

The proof is non-constructive and relies on the Axiom of Choice. The authors explicitly claim no effective content for the labelings it yields, and they list computability of decreasing labelings and constructive existence as open directions. For restricted classes such as left-linear term rewriting systems, decreasing labelings can already be constructed automatically via rule labeling and relative termination, but that is a separate line of work.

The result also does not extend to commutation. Van Oostrom's extension of decreasing diagrams to commutation is not complete for proving commutation, and the paper lists finding a complete generalization for commutation as future work. The completeness claim here is specifically about confluence.

The practical challenge becomes finding a labeling

The paper's own reading of the practical consequence is a shift in where the difficulty sits. Since a locally decreasing labeling always exists, the central practical challenge becomes finding a good one, rather than deciding whether one exists. The authors propose developing heuristics for applying decreasing diagrams and the weak diamond property to real-world programs, extending confluence analysis of actor programs and rule-labeling techniques for term rewriting systems.

The result was formalized independently in Isabelle/HOL and in Lean, both archived on Zenodo. The authors note that by the proof-theoretic conservativity of Isabelle/HOL, the theorem with its definitions unfolded is already provable in Pitts' standard HOL, so the completeness result holds in ZFC; a Lean proof alone would not give this, because Lean's type theory needs inaccessible cardinals to be interpreted in ZFC. The formalizations were developed with the assistance of Anthropic's Claude under the authors' direction and review.

Sources used in this answer