|
|
|
|
|
Call a binary relation on a set a reduction. Let be the reflexive transitive closure of . Two elements are said to be joinable if there is an element such that and . Graphically, this means that
where the starred arrows represent
 and 
respectively ( are non-negative integers). The case (or ) means (or ).
Definition. is said to be confluent if whenever and , then are joinable. In other words, is confluent iff 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: is semi-confluent if for any triple
such that and , then 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 is confluent iff 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)
Cross-references: Church-Rosser property, addition, equivalent, property, 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 621 times total.
Classification:
| AMS MSC: | 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|