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:
“Even more important than the discovery of Columbus, which we are gathered together to celebrate, is the fact that the general government has just discovered women.”
—Bertha Honore Potter Palmer (1849–1918)
“If there is a case for mental events and mental states, it must be that the positing of them, like the positing of molecules, has some indirect systematic efficacy in the development of theory.”
—Willard Van Orman Quine (b. 1908)
“Don’t confuse hypothesis and theory. The former is a possible explanation; the latter, the correct one. The establishment of theory is the very purpose of science.”
—Martin H. Fischer (1879–1962)