Rewriting Information & Rewriting Links at HealthHaven.com

In mathematics, computer science and logic, rewriting covers a wide range of (potentially non-deterministic) methods of replacing subterms of a formula with other terms. What is considered are rewriting systems (also known as rewrite systems or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

Rewriting can be non-deterministic. One rule to rewrite a term could be applied in many different ways to that term, or more than one rule could be applicable. Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications. When combined with an appropriate algorithm, however, rewrite systems can be viewed as computer programs, and several declarative programming languages are based on term rewriting.

[edit] Intuitive examples

[edit] Logic

In logic, the procedure for determining the conjunctive normal form (CNF) of a formula can be conveniently written as a rewriting system. The rules of such a system would be:

$\neg\neg A \to A$ (double negative elimination)

$\neg(A \land B) \to \neg A \lor \neg B$ (De Morgan's laws)

$\neg(A \lor B) \to \neg A \land\neg B$

$(A \land B) \lor C \to (A \lor C) \land (B \lor C)$ (Distributivity)

$A \lor (B \land C) \to (A \lor B) \land (A \lor C)$ ,

where the arrow ( $\to$ ) indicates that the left side of the rule can be rewritten to the right side (so it does not denote logical implication).

[edit] Abstract rewriting systems

Main article: abstract rewriting system

From the above examples, it's clear that we can think of rewriting systems in an abstract manner. We need to specify a set of objects and the rules that can be applied to transform them. The most general (unidimensional) setting of this notion is called an abstract reduction system, (abbreviated ARS), although more recently authors use abstract rewriting system as well.^[1] (The preference for the word "reduction" here instead of "rewriting" constitutes a departure from the uniform use of "rewriting" in the names of systems that are particularizations of ARS. Because the word "reduction" does not appear in the names of more specialized systems, in older texts reduction system is a synonym for ARS).^[2]

An ARS is simply a set A, whose elements are usually called objects, together with a binary relation on A, traditionally denoted by →, and called the reduction relation, rewrite relation^[3] or just reduction.^[2] This (entrenched) terminology using "reduction" is a little misleading, because the relation is not necessarily reducing some measure of the objects; this will become more apparent when we discuss string rewriting systems further in this article.

Example 1. Suppose the set of objects is T = {a, b, c} and the binary relation is given by the rules a → b, b → a, a → c, and b → c. Observe that these rules can be applied to both a and b in any fashion to get the term c. Such a property is clearly an important one. Note also, that c is, in a sense, a "simplest" term in the system, since nothing can be applied to c to transform it any further. This example leads us to define some important notions in the general setting of an ARS. First we need some basic notions and notations.^[4]

$\stackrel{*}{\rightarrow}$ is the transitive closure of $\rightarrow \cup =$ , where = is the identity relation, i.e. $\stackrel{*}{\rightarrow}$ is the smallest preorder (reflexive and transitive relation) containing $\rightarrow$ . It is also called the reflexive transitive closure of $\rightarrow$ .
$\leftrightarrow$ is $\rightarrow \cup \rightarrow^{-1}$ , that is the union of the relation → with its inverse relation, also known as the symmetric closure of $\rightarrow$ .
$\stackrel{*}{\leftrightarrow}$ is the transitive closure of $\leftrightarrow \cup =$ , that is $\stackrel{*}{\leftrightarrow}$ is the smallest equivalence relation containing $\rightarrow$ . It is also known as the reflexive transitive symmetric closure of $\rightarrow$ .

[edit] Normal forms, joinability and the word problem

An object x in A is called reducible if there exist some other y in A and $x \rightarrow y$ ; otherwise it is called irreducible or a normal form. An object y is called a normal form of x if $x \stackrel{*}{\rightarrow} y$ , and y is irreducible. If x has a unique normal form, then this is usually denoted with $x\downarrow$ . In example 1 above, c is a normal form, and $c = a\downarrow = b\downarrow$ . If every object has at least one normal form, the ARS is called normalizing.

A related, but weaker notion than the existence of normal forms is that of two objects being joinable: x and y are said joinable if there exists some z with the property that $x \stackrel{*}{\rightarrow} z \stackrel{*}{\leftarrow} y$ . From this definition, it's apparent one may define the joinability relation as $\stackrel{*}{\rightarrow} \circ \stackrel{*}{\leftarrow}$ , where $\circ$ is the composition of relations. Joinability is usually denoted, somewhat confusingly, also with $\downarrow$ , but in this notation the down arrow is a binary relation, i.e. we write $x\mathbin\downarrow y$ if x and y are joinable.

One of the important problems that may be formulated in an ARS is the word problem: given x and y are they equivalent under $\stackrel{*}{\leftrightarrow}$ ? This is a very general setting for formulating the word problem for the presentation of an algebraic structure. For instance, the word problem for groups is a particular case of an ARS word problem. Central to an "easy" solution for the word problem is the existence of unique normal forms: in this case if two objects have the same normal form, then they are equivalent under $\stackrel{*}{\leftrightarrow}$ . The word problem for an ARS is undecidable in general.

[edit] The Church-Rosser property and confluence

An ARS is said to possess the Church-Rosser property if and only if $x\stackrel{*}{\leftrightarrow}y$ implies $x\mathbin\downarrow y$ . In words, the Church-Rosser propery means that the reflexive transitive symmetric closure is contained in the joinability relation. Alonzo Church and J. Barkley Rosser proved in 1936 that lambda calculus has this property;^[5] hence the name of the property.^[6] (The fact that lambda calculus has this property is also known as the Church-Rosser theorem.) In an ARS with the Church-Rosser property the word problem may be reduced to the search for a common successor. In a Church-Rosser system, an object has at most one normal form; that is the normal form of an object is unique if it exists, but it may well not exist.

Several different properties are equivalent to the Church-Rosser property, but may be simpler to check in any particular setting. In particular, confluence is equivalent to Church-Rosser. The notion of confluence can be defined for individual elements, something that's not possible for Church-Rosser. An ARS $(A,\rightarrow)$ is said:

confluent if and only if for all w, x, and y in A, $x \stackrel{*}{\leftarrow} w \stackrel{*}{\rightarrow} y$ implies $x\mathbin\downarrow y$ . Roughly speaking, confluence says that no matter how two paths diverge from a common ancestor (w), the paths are joining at some common successor. This notion may be refined as property of a particular object w, and the system called confluent if all its elements are confluent.
locally confluent if and only if for all w, x, and y in A, $x \leftarrow w \rightarrow y$ implies $x\mathbin\downarrow y$ . This property is sometimes called weak confluence.

Theorem. For an ARS the following conditions are equivalent: (i) it has the Church-Rosser property, (ii) it is confluent.^[7]

Corollary.^[8] In a confluent ARS if $x \stackrel{*}{\leftrightarrow} y$ then

If both x and y are normal forms, then x = y.
If y is a normal form, then $x \stackrel{*}{\rightarrow} y$

Because of these equivalences, a fair bit of variation in definitions is encountered in the literature. For instance, in Bezem et al 2003 the Church-Rosser property and confluence are defined to be synonymous and identical to the definition of confluence presented here; Church-Rosser as defined here remains unnamed, but is given as an equivalent property; this departure from other texts is deliberate.^[9] Because of the above corollary, one may define a normal form y of x as an irreducible y with the property that $x \stackrel{*}{\leftrightarrow} y$ . This definition, found in Book and Otto, is equivalent to common one given here in a confluent system, but it is more inclusive in a non-confluent ARS.

Local confluence on the other hand is not equivalent with the other notions of confluence given in this section, but it is strictly weaker than confluence.

[edit] Termination and convergence

An abstract rewriting system is said to be terminating or noetherian if there is no infinite chain $x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \cdots$ . In a terminating ARS, every object has at least one normal form, thus it is normalizing. The converse is not true. In example 1 for instance, there is an infinite rewriting chain, namely $a \rightarrow b \rightarrow a \rightarrow b \rightarrow \cdots$ , even though the system is normalizing. A confluent and terminating ARS is called convergent. In a convergent ARS, every object has a unique normal form. But it is sufficient for the system to be confluent and normalizing for a unique normal to exist for every element, as seen in example 1.

Theorem (Newman's Lemma): A terminating ARS is confluent if and only if it is locally confluent.

[edit] String rewriting systems

Main article: String rewriting system

A string rewriting system (SRS), also known as semi-Thue system, exploits the free monoid structure of the strings (words) over an alphabet to extend a rewriting relation, R to all strings in the alphabet that contain left- and respectively right-hand sides of some rules as substrings. Formally a semi-Thue systems is a tuple $(Σ, R)$ where $Σ$ is a (usually finite) alphabet, and R is a binary relation between some (fixed) strings in the alphabet, called rewrite rules. The one-step rewriting relation relation $\rightarrow_R$ induced by R on $Σ *$ is defined as: for any strings s, and t in $Σ *$ $s \rightarrow_R t$ if and only if there exist x, y, u, v in $Σ *$ such that s = xuy, t = xvy, and u R v. Since $\rightarrow_R$ is a relation on $Σ *$ , the pair $(\Sigma^*, \rightarrow_R)$ fits the definition of an abstract rewriting system. Obviously R is subset of $\rightarrow_R$ . If the relation $R$ is symmetric, then the system is called a Thue system.

In a SRS, the reduction relation $\stackrel{*}{\rightarrow}_R$ is compatible with the monoid operation, meaning that $x\stackrel{*}{\rightarrow}_R y$ implies $uxv\stackrel{*}{\rightarrow}_R uyv$ for all strings x, y, u, v in $Σ *$ . Similarly, the reflexive transitive symmetric closure of $\rightarrow_R$ , denoted $\stackrel{*}{\leftrightarrow}_R$ , is a congruence, meaning it is an equivalence relation (by definition) and it is also compatible with string concatenation. The relation $\stackrel{*}{\leftrightarrow}_R$ is called the Thue congruence generated by R. In a Thue system, i.e. if R is symmetric, the rewrite relation $\stackrel{*}{\rightarrow}_R$ coincides with the Thue congruence $\stackrel{*}{\leftrightarrow}_R$ .

The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Since $\stackrel{*}{\leftrightarrow}_R$ is a congruence, we can define the factor monoid $\mathcal{M}_R = \Sigma^*/\stackrel{*}{\leftrightarrow}_R$ of the free monoid $Σ *$ by the Thue congruence in the usual manner. If a monoid $\mathcal{M}$ is isomorphic with $\mathcal{M}_R$ , then the semi-Thue system $(Σ, R)$ is called a monoid presentation of $\mathcal{M}$ .

We immediately get some very useful connections with other areas of algebra. For example, the alphabet {a, b} with the rules { ab → ε, ba → ε }, where ε is the empty string, is a presentation of the free group on one generator. If instead the rules are just { ab → ε }, then we obtain a presentation of the bicyclic monoid. Thus semi-Thue systems constitute a natural framework for solving the word problem for monoids and groups. In fact, every monoid has a presentation of the form $(Σ, R)$ , i.e. it may be always be presented by a semi-Thue system, possibly over an infinite alphabet.

The word problem for a semi-Thue system is undecidable in general; this result is sometimes know as the Post-Markov theorem.^[10]

[edit] Term rewriting systems

A generalization of term rewrite systems are graph rewrite systems, operating on graphs instead of (ground-) terms / their corresponding tree representation.

[edit] Trace rewriting systems

Trace theory provides a means for discussing multiprocessing in more formal terms, such as via the trace monoid and the history monoid. Rewriting can be performed in trace systems as well.

[edit] Philosophy

Rewriting systems can be seen as programs that infer end-effects from a list of cause-effect relationships. In this way, rewriting systems can be considered to be automated causality provers.

[edit] Properties of rewriting systems

Observe that in both of the above rewriting systems, it is possible to get terms rewritten to a "simplest" term, where this term cannot be modified any further from the rules in the rewriting system. Terms which cannot be written any further are called normal forms. The potential existence or uniqueness of normal forms can be used to classify and describe certain rewriting systems. There are rewriting systems which do not have normal forms: a very simple one is the rewriting system on two terms a and b with a → b, b → a.

The property exhibited above where terms can be rewritten regardless of the choice of rewriting rule to obtain the same normal form is known as confluence. The property of confluence is linked with the property of having unique normal forms.

[edit] See also

Look up rewriting in Wiktionary, the free dictionary.

[edit] Notes

^ Bezem et al, p. 7,
^ ^a ^b Book and Otto, p. 10
^ Bezem et al, p. 7
^ Baader and Nipkow, pp. 8-9
^ Alonzo Church and J. Barkley Rosser. Some properties of conversion. Trans. AMS, 39:472-482, 1936
^ Baader and Nipkow, p. 9
^ Baader and Nipkow, p. 11
^ Baader and Nipkow, p. 12
^ Bezem et al, p.11
^ Martin Davis et al. 1994, p. 178

[edit] References

Franz Baader and Tobias Nipkow (1999). Term rewriting and all that. Cambridge University Press. ISBN 0-521-77920-0. http://books.google.com/books?id=N7BvXVUCQk8C&dq. 316 pages. A textbook suitable for undergraduates.
Marc Bezem, J. W. Klop, Roel de Vrijer ("Terese"), Term rewriting systems, Cambridge University Press, 2003, ISBN 0521391156. This is the most recent comprehensive monograph. It uses however a fair deal of non-yet-standard notations and definitions. For instance the Church-Rosser property is defined to be identical with confluence.
Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer (1993).
Nachum Dershowitz and Jean-Pierre Jouannaud Rewrite Systems, Chapter 6 in Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics., Elsevier and MIT Press, 1990, ISBN 0-444-88074-7, pp. 243–320. The preprint of this chapter is freely available from the authors, but it misses the figures.

Barot

[edit] External links

The Rewriting Home Page

[0] Bezem et al, p. 7,

[Book_and_Otto.2C_p._10-1] Book and Otto, p. 10

[2] Bezem et al, p. 7

[3] Baader and Nipkow, pp. 8-9

[4] Alonzo Church and J. Barkley Rosser. Some properties of conversion. Trans. AMS, 39:472-482, 1936

[5] Baader and Nipkow, p. 9

[6] Baader and Nipkow, p. 11

[7] Baader and Nipkow, p. 12

[8] Bezem et al, p.11

[9] Martin Davis et al. 1994, p. 178

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Contents