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:
“We have seen over and over that white male historians in general have tended to dismiss any history they didn’t themselves write, on the grounds that it is unserious, unscholarly, a fad, too “political,” “merely” oral and thus unreliable.”
—Adrienne Rich (b. 1929)
“Before I get through with you, you will have a clear case for divorce and so will my wife. Now, the first thing to do is arrange for a settlement. You take the children, your husband takes the house, Junior burns down the house, you take the insurance and I take you!”
—S.J. Perelman, U.S. screenwriter, Arthur Sheekman, Will Johnstone, and Norman Z. McLeod. Groucho Marx, Monkey Business, terms for a divorce settlement proposed while trying to woo Lucille Briggs (Thelma Todd)
“We commonly say that the rich man can speak the truth, can afford honesty, can afford independence of opinion and action;—and that is the theory of nobility. But it is the rich man in a true sense, that is to say, not the man of large income and large expenditure, but solely the man whose outlay is less than his income and is steadily kept so.”
—Ralph Waldo Emerson (1803–1882)