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:
“In effect, to follow, not to force the public inclination; to give a direction, a form, a technical dress, and a specific sanction, to the general sense of the community, is the true end of legislature.”
—Edmund Burke (1729–1797)
“A more problematic example is the parallel between the increasingly abstract and insubstantial picture of the physical universe which modern physics has given us and the popularity of abstract and non-representational forms of art and poetry. In each case the representation of reality is increasingly removed from the picture which is immediately presented to us by our senses.”
—Harvey Brooks (b. 1915)
“There is in him, hidden deep-down, a great instinctive artist, and hence the makings of an aristocrat. In his muddled way, held back by the manacles of his race and time, and his steps made uncertain by a guiding theory which too often eludes his own comprehension, he yet manages to produce works of unquestionable beauty and authority, and to interpret life in a manner that is poignant and illuminating.”
—H.L. (Henry Lewis)