Confluence (abstract Rewriting) - General Case and Theory

General Case and Theory

A rewriting system can be expressed as a directed graph in which nodes represent expressions and edges represent rewrites. So, for example, if the expression can be rewritten into, then we say that is a reduct of (alternatively, reduces to, or is an expansion of ). This is represented using arrow notation; indicates that reduces to . Intuitively, this means that the corresponding graph has a directed edge from to .

If there is a path between two graph nodes (let's call them and ), then the intermediate nodes form a reduction sequence. So, for instance, if, then we can write, indicating the existence of a reduction sequence from to .

With this established, confluence can be defined as follows. Let a, b, c ∈ S, with a →* b and a →* c. a is deemed confluent if there exists a d ∈ S with b →* d and c →* d. If every a ∈ S is confluent, we say that → is confluent, or has the Church-Rosser property. This property is also sometimes called the diamond property, after the shape of the diagram shown on the right. Caution: other presentations reserve the term diamond property for a variant of the diagram with single reductions everywhere; that is, whenever a → b and a → c, there must exist a d such that b → d and c → d. The single-reduction variant is strictly stronger than the multi-reduction one.

Read more about this topic:  Confluence (abstract Rewriting)

Famous quotes containing the words general, case and/or theory:

    “As a general rule never take your whole fee in advance, nor any more than a small retainer. When fully paid beforehand, you are more than a common mortal if you can feel the same interest in the case, as if something was still in prospect for you, as well as for your client.”
    —Abraham Lincoln (1809–1865)

    “Television is an excellent system when one has nothing to lose, as is the case with a nomadic and rootless country like the United States, but in Europe the affect of television is that of a bulldozer which reduces culture to the lowest possible denominator.”
    —Marc Fumaroli (b. 1932)

    “Osteopath—One who argues that all human ills are caused by the pressure of hard bone upon soft tissue. The proof of his theory is to be found in the heads of those who believe it.”
    —H.L. (Henry Lewis)