Confluence Relations

Confluent Relations (using Reduction Relations)


Master of Science in Mathematics
Lecture Notes. Accessed on: 2019-10-23 08:09:36

We discuss confluent relations; in particular, we prove Newman’s Lemma: that local confluence, confluence, the Church-Rosser property, and the unique normal forms property are all equivalent for a well-founded relation. We also give a generalization of Newman’s lemma based on the Buchberger-Winkler’s Property.

Reduction Relations

Let $\longrightarrow$ be a relation on $X.$ If there exists  $c\in X$ such that  $a\stackrel{*}{\longrightarrow} c$ and $b\stackrel{*}{\longrightarrow} c,$ then $a$ and $b$ are said to have a common successor, denoted by $a \downarrow b.$  If there does not exist $b\in X$ such that $a\longrightarrow b,$ then $a$ is called a normal form of $\longrightarrow.$ If $a\stackrel{*}{\longrightarrow} b$ and $b$ is a normal form, then $b$ is called a normal form of $X.$ 

Theorem. Well-founded implies every element has a normal form. 

Definition. Let $\longrightarrow$ be a relation on $X.$

1) A relation $\longrightarrow$ is called locally confluent whenever $a \longrightarrow b$ and $a \longrightarrow c$ implies $b \downarrow c,$ for all $a,b,c\in X.$ 

2) A relation $\longrightarrow$ is called confluent whenever $a \stackrel{*}{\longrightarrow} b$ and $a \stackrel{*}{\longrightarrow} c$ implies $b \downarrow c,$ for all $a,b,c\in X.$

3) A relation $\longrightarrow$ is said to satisfy the unique normal forms property if $a \stackrel{*}{\longrightarrow} b $ and $a \stackrel{*}{\longrightarrow} c$ with $b$ and $c$ in $\longrightarrow$-normal form implies $b=c,$ for all $a,b,c\in X.$

4) A relation $\longrightarrow$ is said to have the Church-Rosser property whenever $b\stackrel{*}{\longleftrightarrow} c$ implies $b\downarrow c,$ for all $a,b,c\in X.$

Newman’s Lemma

Newman’s Lemma states that a well-founded relation is confluent (locally confluent) is the same as having the unique normal forms property.

Theorem. (Newman’s Lemma) Let $\longrightarrow$ be a well-founded relation on $X.$  Then the following properties are equivalent. 

$\quad$ 1) local confluence 

$\quad$ 2) confluence

$\quad$ 3) unique normal forms

$\quad$ 4) Church-Rosser property

Proof. $(1)\Rightarrow(2)$:  Assume for a contradiction that $\longrightarrow$ is locally confluent but that the set  $$ T=\left\{ a \in X  : \exists \, \, b, c \in X \text{ with } a \stackrel{*}{\longrightarrow} b \text{ and } a \stackrel{*}{\longrightarrow} c \text{ but not } b \downarrow c\right \} $$ is non-empty.  Since $\longrightarrow$ is well-founded, $T$ has a $\longrightarrow$-minimial element $a.$  Let $b,c \in X $ with $a \stackrel{*}{\longrightarrow} b$ and $a \stackrel{*}{\longrightarrow} c,$ but not $b \downarrow c.$  If $a=b$ or $a=c,$ then it trivially follows $b \downarrow c.$  Otherwise there must exist $b’, c’\in X$ (possibly $b’=b$ or $c’=c$) with  $$ a \longrightarrow b’ \stackrel{*}{\longrightarrow} b \quad \text{and} \quad  a \longrightarrow c’ \stackrel{*}{\longrightarrow} c. $$ By the local confluence of $\longrightarrow,$ there exists $d\in X$ with $$ a \longrightarrow b’ \stackrel{*}{\longrightarrow} d \quad \text{and} \quad  a \longrightarrow c’ \stackrel{*}{\longrightarrow} d. $$ By the minimality of $a$ in $T$ it follows $b’\not\in T,$ and so  there exists $e\in X$ with  $$ a\longrightarrow b’ \stackrel{*}{\longrightarrow} b \stackrel{*}{\longrightarrow} e \quad \text{and} \quad  a\longrightarrow b’ \stackrel{*}{\longrightarrow} d \stackrel{*}{\longrightarrow} e. $$ Then $a\longrightarrow c’ \stackrel{*}{\longrightarrow} d \stackrel{*}{\longrightarrow} e$ and again by the minimality of $a$ in $T$ it follows $c’\not\in T.$  Thus there exists $f \in X$ with  $$ a \longrightarrow c’ \stackrel{*}{\longrightarrow} d \stackrel{*}{\longrightarrow} e \stackrel{*}{\longrightarrow} f \quad \text{and} \quad  a \longrightarrow c’ \stackrel{*}{\longrightarrow} c \stackrel{*}{\longrightarrow} f.  $$ Therefore we have shown $$a \longrightarrow b’ \stackrel{*}{\longrightarrow} b \stackrel{*}{\longrightarrow} e \stackrel{*}{\longrightarrow} f \quad \text{and} \quad  a \longrightarrow c’ \stackrel{*}{\longrightarrow} c \stackrel{*}{\longrightarrow} f.  $$ and so $b \downarrow c$ which is contrary to assumption. 

Local confluence implies confluence.

$(2)\Rightarrow(3)$:  Let $a \stackrel{*}{\longrightarrow} b$ and $a \stackrel{*}{\longrightarrow} c,$ and suppose $b$ and $c$ are in $\longrightarrow$-normal form.  There exists $d \in X$ with $b \stackrel{*}{\longrightarrow} d$ and $c \stackrel{*}{\longrightarrow} d,$ and thus $b=d=c.$ 

$(3)\Rightarrow(4)$:  Claim: by induction on $k\in \mathbb{N}$ that for all $a, b \in X$ with $a \stackrel{k}{\longleftrightarrow} b$ it follows that $a \downarrow b.$  The case $k=0$ is trivial. Now let $a \stackrel{k+1}{\longleftrightarrow} b,$ say $a \stackrel{k}{\longleftrightarrow} c \longleftrightarrow  b.$  Then by induction hypothesis there exists $d \in X$ with $a \stackrel{*}{\longrightarrow} d$ and $c \stackrel{*}{\longrightarrow} d.$ If $b \longrightarrow c,$ then $a \stackrel{*}{\longrightarrow} d$ and $b \stackrel{*}{\longrightarrow} d$ and so $a \downarrow b.$   For the other case, assume $c \longrightarrow b.$  Let $d’$ be a normal form of $d$ and let $b’$ be a normal form of $b$ with respect to $\longrightarrow.$  Then $c \stackrel{*}{\longrightarrow} b’$ and $c \stackrel{*}{\longrightarrow} d’,$ and so $d’$ and $b’$ are normal forms of $c$ and hence equal.  Thus we have $a \stackrel{*}{\longrightarrow} d’$ and  $b \stackrel{*}{\longrightarrow} d’,$ which means $a \downarrow b.$

$(4)\Rightarrow(1)$:  If $a \longrightarrow b$ and $a \longrightarrow c,$ then $b \stackrel{*}{\longleftrightarrow} c,$ and so it follows $b \downarrow c.$

Corollary. If $\longrightarrow$ is confluent and $a\stackrel{*}{\longleftrightarrow} b,$ then 

$\quad$ 1) if $b$ is in normal form, then $a\stackrel{*}{\longrightarrow} b,$ and

$\quad$ 2) if $a$ and $b$ are in normal form, then $a=b.$

Proof. This proof is left as an exercise.

Thus we know that for confluent relations, two elements are equivalent if and only if they have a common successor. 

Buchberger-Winkler’s Property

Definition. Let $\longrightarrow$ be a relation on $X.$

1) If there exists $c_1,c_2,…,c_n\in X$ such that  $$ b_1=c_1\longleftrightarrow c_2\longleftrightarrow \cdots \longleftrightarrow c_n=b_2 $$ and $a\longrightarrow^+ c_i$ for $i=1,2,…,n,$ then $b_1$ and $b_2$ are said to be connected below $a,$ denoted by $b_1 \stackrel{a}{\longleftrightarrow}  b_2.$

2) A relation $\longrightarrow$ on $X$ is said to have the Buchberger-Winkler property whenever $a\longrightarrow b$ and $a\longrightarrow c$ implies $b \stackrel{a}{\longleftrightarrow} c$ for all $a,b,c\in X.$

Theorem. Let $\longrightarrow$ be a well-founded relation on $X.$  Then $\longrightarrow$ is confluent if and only if the Buchberger-Winkler property holds.

Proof. Suppose $\longrightarrow$ is confluent and $a \longrightarrow b$ and $a \longrightarrow c$ for $a, b, c \in X.$  Then there exists $d$ such that $b\stackrel{*}{\longrightarrow} d$ and $c\stackrel{*}{\longrightarrow} d.$  It follows that $b \stackrel{a}{\longleftrightarrow} c.$ Conversely, assume $a, b, c$ are arbitrary, but fixed such that $a \stackrel{*}{\longrightarrow} b$ and $a \stackrel{*}{\longrightarrow} c.$  The proof follows by induction on $\longrightarrow.$  The first induction hypothesis is: $$\forall \, a’ \, (a\longrightarrow^+ a’), \forall \, b’, c’ \, (\text{if }  a’ \stackrel{*}{\longrightarrow} c’  \text{ and } a’ \stackrel{*}{\longrightarrow} b’  \text{, then } b’ \downarrow c’).$$ It is required to show $b \downarrow c,$ that is $b \stackrel{*}{\longrightarrow} d$ and $c \stackrel{*}{\longrightarrow} d$ for some $d.$ The cases $a=b$ or $a=c$ are trivial. Assume $a \neq b$ and $a \neq c.$ Then there exist $b_1$ and $c_1$ such that  $a \longrightarrow b_1 \stackrel{*}{\longrightarrow} b$ and $a \longrightarrow c_1 \stackrel{*}{\longrightarrow} c.$ By assuming $\longrightarrow$ has the Buchberger property, there exists $e_1, e_2, … , e_n$ such that $b_1=e_1 \longleftrightarrow e_2 \longleftrightarrow \cdots  \longleftrightarrow e_n=c_1$ and $a\longrightarrow^+ e_i.$ we will proceed by induction on $n$ and show: for all $n,$ for all $e_1, e_2, …,e_n$: \begin{equation} \label{conflutwo} \text{if} \quad  e_1 \longleftrightarrow e_2 \longleftrightarrow \cdots  \longleftrightarrow e_n \quad \text{with} \quad   a\longrightarrow^+ e_i , \qquad \text{then } \qquad e_1\downarrow e_n. \tag{*} \end{equation} Notice \eqref{conflutwo} is clear for $n=1.$   Our second induction hypothesis is: \eqref{conflutwo} is true for some $n.$  Assume $e_1\longleftrightarrow e_2 \longleftrightarrow \cdots  \longleftrightarrow e_n \longleftrightarrow e_{n+1}$ and $a\longrightarrow^+ e_i$ for $i=1, 2, …,n+1.$   By induction hypothesis 2, there exists $d_1$ such that $e_1\stackrel{*}{\longrightarrow} d_1$ and   $e_n\stackrel{*}{\longrightarrow} d_1.$  If $e_{n+1}\longrightarrow e_n$ then $e_{n+1} \stackrel{*}{\longrightarrow} d_1$ and so  $e_1\downarrow e_{n+1}.$ If $e_n \longrightarrow e_{n+1},$ then by induction hypothesis 1, there exists $d_1’$ such that $d_1\stackrel{*}{\longrightarrow} d_1’$ and $e_{n+1} \stackrel{*}{\longrightarrow} d_1′.$ Thus, it follows $e_1\downarrow e_{n+1}$ in this case as well. Therefore, \eqref{conflutwo} is proven by induction and so $d_1$ exists such that $e_1\stackrel{*}{\longrightarrow} d_1$ and $e_n\stackrel{*}{\longrightarrow} d_1$ for all $n.$  Then, $b_1 \stackrel{*}{\longrightarrow} d_1,$ $b_1 \stackrel{*}{\longrightarrow} b,$ and $a\longrightarrow b_1$ implies, by induction hypothesis 1, that there exists $f$ such that $b \stackrel{*}{\longrightarrow} f$ and  $d_1 \stackrel{*}{\longrightarrow} f.$  It follows that, $c_1 \stackrel{*}{\longrightarrow} c$ and $c_1 \stackrel{*}{\longrightarrow} f.$  Again by induction hypothesis 1, there exists $d$ such that $f \stackrel{*}{\longrightarrow} d$ and $c \stackrel{*}{\longrightarrow} d.$ Therefore, it follows $b \stackrel{*}{\longrightarrow} d$ and  $c \stackrel{*}{\longrightarrow} d.$

Let $X$ be a set and $\to$ a reduction (binary relation) on $X.$  A chain with respect to $\to$ is a sequence of elements $x_1,x_2,x_3,\ldots$ in $X$ such that $x_1\to x_2,$ $x_2\to x_3,$ etc… A chain with respect to $\to$ is usually written $$x_1\to x_2 \to x_3 \to \cdots \to x_n \to \cdots.$$ The length of a chain is the cardinality of its underlying sequence.  A chain is finite if its length is finite.  Otherwise, it is infinite.  

Definition. A reduction $\to$ on a set $X$ is said to be terminating if it has no infinite chains.   In other words, every chain terminates.

Here are a few examples.

  • If $\to$ is reflexive, or non-trivial symmetric, then it is never terminating.
  • Let $X$ be the set of all positive integers greater than $1.$  Define $\to$ on $X$ so that $a\to b$ means that $a=bc$ for some $c\in X.$  Then $\to$ is a terminating reduction.  By the way, $\to$ is also a normalizing reduction.
  • In fact, it is easy to see that a terminating reduction is normalizing: if $a$ has no normal form, then we may form an infinite chain starting from $a.$
  • On the other hand, not all normalizing reduction is terminating.  A canonical example is the set of all non-negative integers with the reduction $\to$ defined by $a\to b$ if and only if either $a,b\ne 0,$ $a\ne b,$ and $aj,$ and $j$ arbitrary.
  • The reflexive transitive closure of a terminating relation is a partial order.

A closely related concept is the descending chain condition (DCC). A reduction $\to$ on $X$ is said to satisfy the descending chain condition (DCC) if the only infinite chains on $X$ are those that are eventually constant. A chain $x_1\to x_2 \to x_3 \to \cdots $ is eventually constant if there is a positive integer $N$ such that for all $n\ge N,$ $x_n=x_N.$  Every terminating relation satisfies DCC.   The converse is obviously not true, as a reflexive reduction illustrates.

Another related concept is acyclicity.   Let $\to$ be a reduction on $X.$  A chain $x_0\to x_1 \to \cdots x_n$ is said to be cyclic if $x_i=x_j$ for some $0\le i < j\le n.$ This means that there is a “closed loop” in the chain.   The reduction $\to$ is said to be acyclic if there are no cyclic chains with respect to $\to.$ Every terminating relation is acyclic, but not conversely. The usual strict inequality relation on the set of positive integers is an example of an acyclic but non-terminating relation.

5/5 (1 Review)

Leave a Comment

Scroll to Top