nLab confluent relation

Redirected from "confluent".
Note: confluent category and confluent relation both redirect for "confluent".

Contents

Definition

Let (X,→)(X,\rightarrow) be an abstract rewriting system, i.e., a set equipped with a binary relation →\rightarrow. Write → *\rightarrow^{*} for the reflexive-transitive closure of →\rightarrow. We say that →\rightarrow is confluent iff for every a,b,c∈Xa,b,c \in X such that a→ *ba \rightarrow^* b and a→ *ca \rightarrow^* c, there exists d∈Xd \in X such that b→ *db \rightarrow^{*} d and c→ *dc \rightarrow^{*} d.

Note that only → *\rightarrow^{*} occurs in the definition of confluence, not the underlying →\rightarrow. Confluence can therefore be reframed as a property of a preorder.

Strong normalization

Say that an abstract rewriting system (X,→)(X, \rightarrow) is strongly normalizing if every sequence

x 0→x 1→…x_0 \rightarrow x_1 \rightarrow \ldots

is eventually stable: there is some ii such that x i=x i+1=…x_i = x_{i+1} = \ldots. An element xx is normal if x→yx \rightarrow y implies x=yx = y.

Define y≺xy \prec x to mean x→ *yx \rightarrow^{*} y and x≠yx \neq y. The condition of being strongly normalizing is that all downward chains

…≺x 1≺x 0\ldots \prec x_1 \prec x_0

terminate after finitely many steps (no infinite descent), i.e., that ≺\prec is a well-founded relation.

Proposition

In a confluent strongly normalizing abstract rewriting system (X,→)(X, \rightarrow), for every element xx there is a unique normal yy such that x→ *yx \rightarrow^{*} y.

Proof

Of course, for every xx there is some normal yy for which x→ *yx \rightarrow^{*} y. If that were not true for some xx, then by dependent choice, we can construct a sequence (x n)(x_n) with x 0=xx_0 = x and for which x n+1≺x nx_{n+1} \prec x_n (since by hypothesis no x nx_n in the chain is normal). But this violates “no infinite descent”.

Now suppose x→ *tx \rightarrow^{*} t and x→ *t′x \rightarrow^{*} t' for normal t,t′t, t'. By confluence, there is some uu such that t→ *ut \rightarrow^{*} u and t′→ *ut' \rightarrow^{*} u. By normality of t,t′t, t', we have t=u=t′t = u = t', establishing uniqueness.

With a little extra care, the word “confluent” in the proposition can be replaced by “locally confluent”, in the sense of locally confluent relation.

Relation to directions

Take any abstract rewriting system (X,→)(X, \rightarrow). Given a certain element x∈Xx \in X as the starting point, the set {t∈X∣x→ *t}\{ t \in X \mid x \rightarrow^{*} t\} is the set of the elements reachable from xx by rewrites in →\rightarrow. When →\rightarrow is confluent, → *\rightarrow^{*} restricted to that set is a direction on that set.

Confluence can be seen as a local form of directedness. Again viewing → *\rightarrow^{*} as a preorder, directedness says any two elements must have an upper bound, while confluence says that any two elements have an upper bound if they also have a lower bound.

References

Last revised on November 6, 2026 at 20:40:22. See the history of this page for a list of all contributions to it.