Confluent Relations (using Reduction Relations)

Share on tumblr
Share on facebook
Share on linkedin
Share on twitter
Share on stumbleupon
Share on email
Share on pinterest

Confluent Relations (using Reduction Relations)

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.

0/5 (0 Reviews)