## You are here

Homeconfluence

## Primary tabs

# confluence

Call a binary relation $\to$ on a set $S$ a reduction. Let $\to^{*}$ be the reflexive transitive closure of $\to$. Two elements $a,b\in S$ are said to be *joinable* if there is an element $c\in S$ such that $a\to^{*}c$ and $b\to^{*}c$. Graphically, this means that

$\xymatrix@R-=10pt{a\ar[dr]^{{*}}\\ &c\\ b\ar[ur]_{{*}}}$

where the starred arrows represent

$a\to a_{1}\to\cdots\to a_{n}\to c\qquad\mbox{ and }\qquad b\to b_{1}\to\cdots% \to b_{m}\to c$ |

respectively ($m,n$ are non-negative integers). The case $m=0$ (or $n=0$) means $a\to c$ (or $b\to c$).

Definition. $\to$ is said to be *confluent* if whenever $x\to^{*}a$ and $x\to^{*}b$, then $a,b$ are joinable. In other words, $\to$ is confluent iff $\to^{*}$ has the amalgamation property. Graphically, this says that, whenever we have a diagram

$\xymatrix@R-=10pt{&a\\ x\ar[ur]^{{*}}\ar[dr]_{{*}}&\\ &b}$

then it can be “completed” into a “diamond”:

$\xymatrix@R-=10pt{&a\ar[dr]^{{*}}\\ x\ar[ur]^{{*}}\ar[dr]_{{*}}&&c\\ &b\ar[ur]_{{*}}&}$

Remark. A more general property than confluence, called *semi-confluence* is defined as follows: $\to$ is *semi-confluent* if for any triple $x,a,b\in S$ such that $x\to a$ and $x\to^{*}b$, then $a,b$ are joinable. It turns out that this seemingly weaker notion is actually equivalent to the stronger notion of confluence. In addition, it can be shown that $\to$ is confluent iff $\to$ has the Church-Rosser property.

# References

- 1
F. Baader, T. Nipkow,
*Term Rewriting and All That*, Cambridge University Press (1998).

## Mathematics Subject Classification

68Q42*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections