|
|
|
|
|
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 \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
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.
- 1
- F. Baader, T. Nipkow, Term Rewriting and All That, Cambridge University Press (1998).
|
"confluence" is owned by CWoo.
|
|
(view preamble | get metadata)
Cross-references: Church-Rosser property, addition, stronger, equivalent, property, diagram, amalgamation property, iff, integers, represent, reflexive transitive closure, reduction, binary relation
There are 5 references to this entry.
This is version 11 of confluence, born on 2008-02-09, modified 2008-03-31.
Object id is 10251, canonical name is Confluence.
Accessed 2002 times total.
Classification:
| AMS MSC: | 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$ \xymatrix@R-=10pt{ a\ar[dr]^{*}\ &c\ b\ar[ur]_{*} } $](http://images.planetmath.org:8080/cache/objects/10251/js/img1.png "$ \xymatrix@R-=10pt{ a\ar[dr]^{*}\ &c\ b\ar[ur]_{*} } $")
![$ \xymatrix@R-=10pt{ &a\ x\ar[ur]^{*}\ar[dr]_{*} &\ &b } $](http://images.planetmath.org:8080/cache/objects/10251/js/img2.png "$ \xymatrix@R-=10pt{ &a\ x\ar[ur]^{*}\ar[dr]_{*} &\ &b } $")
![$ \xymatrix@R-=10pt{ &a\ar[dr]^{*}\ x\ar[ur]^{*}\ar[dr]_{*} &&c\ &b\ar[ur]_{*}& } $](http://images.planetmath.org:8080/cache/objects/10251/js/img3.png "$ \xymatrix@R-=10pt{ &a\ar[dr]^{*}\ x\ar[ur]^{*}\ar[dr]_{*} &&c\ &b\ar[ur]_{*}& } $")