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

where the starred arrows represent

$$a\to a_1\to \mathrm{\cdots }\to a_n\to c\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}b\to b_1\to \mathrm{\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

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

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.