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:
“The general tendency of things throughout the world is to render mediocrity the ascendant power among mankind.”
—John Stuart Mill (1806–1873)
“What do you think of the human mind? I mean, in case you think there is a human mind.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“Every theory is a self-fulfilling prophecy that orders experience into the framework it provides.”
—Ruth Hubbard (b. 1924)