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.
Intuitive examples
Logic
In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be conveniently written as a rewriting system. The rules of such a system would be:
- $\backslash neg\backslash neg\; A\; \backslash to\; A$ (double negative elimination)
- $\backslash neg(A\; \backslash land\; B)\; \backslash to\; \backslash neg\; A\; \backslash lor\; \backslash neg\; B$ (De Morgan's laws)
- $\backslash neg(A\; \backslash lor\; B)\; \backslash to\; \backslash neg\; A\; \backslash land\backslash neg\; B$
- $(A\; \backslash land\; B)\; \backslash lor\; C\; \backslash to\; (A\; \backslash lor\; C)\; \backslash land\; (B\; \backslash lor\; C)$ (Distributivity)
- $A\; \backslash lor\; (B\; \backslash land\; C)\; \backslash to\; (A\; \backslash lor\; B)\; \backslash land\; (A\; \backslash lor\; C)$,
where the symbol ($\backslash to$) indicates that an expression matching the left hand side of the rule can be rewritten to one formed by the right hand side. In this system, we can perform a rewrite from left to right only when the logical interpretation of the left hand side is equivalent to that of the right.
Abstract rewriting systems
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]}
Normal forms, joinability and the word problem
An object x in A is called reducible if there exists some other y in A such that $x\; \backslash rightarrow\; y$; otherwise it is called irreducible or a normal form. An object y is called a normal form of x if $x\; \backslash stackrel\{*\}\{\backslash rightarrow\}\; y$, and y is irreducible. If x has a unique normal form, then this is usually denoted with $x\backslash downarrow$. In example 1 above, c is a normal form, and $c\; =\; a\backslash downarrow\; =\; b\backslash 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 to be joinable if there exists some z with the property that $x\; \backslash stackrel\{*\}\{\backslash rightarrow\}\; z\; \backslash stackrel\{*\}\{\backslash leftarrow\}\; y$. From this definition, it's apparent one may define the joinability relation as $\backslash stackrel\{*\}\{\backslash rightarrow\}\; \backslash circ\; \backslash stackrel\{*\}\{\backslash leftarrow\}$, where $\backslash circ$ is the composition of relations. Joinability is usually denoted, somewhat confusingly, also with $\backslash downarrow$, but in this notation the down arrow is a binary relation, i.e. we write $x\backslash mathbin\backslash 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 $\backslash stackrel\{*\}\{\backslash 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 $\backslash stackrel\{*\}\{\backslash leftrightarrow\}$. The word problem for an ARS is undecidable in general.
The Church-Rosser property and confluence
An ARS is said to possess the Church-Rosser property if and only if $x\backslash stackrel\{*\}\{\backslash leftrightarrow\}y$ implies $x\backslash mathbin\backslash downarrow\; y$. In words, the Church-Rosser property means that any two equivalent objects are joinable. 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 some particular setting. In particular, confluence is equivalent to Church-Rosser. An ARS $(A,\backslash rightarrow)$ is said:
- confluent if for all w, x, and y in A, $x\; \backslash stackrel\{*\}\{\backslash leftarrow\}\; w\; \backslash stackrel\{*\}\{\backslash rightarrow\}\; y$ implies $x\backslash mathbin\backslash 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 for all w, x, and y in A, $x\; \backslash leftarrow\; w\; \backslash rightarrow\; y$ implies $x\backslash mathbin\backslash 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\; \backslash stackrel\{*\}\{\backslash leftrightarrow\}\; y$ then
- If both x and y are normal forms, then x = y.
- If y is a normal form, then $x\; \backslash stackrel\{*\}\{\backslash 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, in a confluent ARS one may define a normal form y of x as an irreducible y with the property that $x\; \backslash stackrel\{*\}\{\backslash 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 ^{[10]} more 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.
The relation $a\; \backslash rightarrow\; b,\; \backslash ;\; b\; \backslash rightarrow\; a,\; \backslash ;\; a\; \backslash rightarrow\; c,\backslash ;\; b\; \backslash rightarrow\; d$ is locally confluent, but not confluent, as $c$ and $d$ are equivalent, but not joinable.^{[11]}
Termination and convergence
An abstract rewriting system is said to be terminating or noetherian if there is no infinite chain $x\_0\; \backslash rightarrow\; x\_1\; \backslash rightarrow\; x\_2\; \backslash rightarrow\; \backslash 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\; \backslash rightarrow\; b\; \backslash rightarrow\; a\; \backslash rightarrow\; b\; \backslash rightarrow\; \backslash 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.
Theorem (Newman's Lemma): A terminating ARS is confluent if and only if it is locally confluent.
String rewriting systems
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 $(\backslash Sigma,\; R)$ where $\backslash Sigma$ 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 $\backslash rightarrow\_R$ induced by R on $\backslash Sigma^*$ is defined as: for any strings s, and t in $\backslash Sigma^*$ $s\; \backslash rightarrow\_R\; t$ if and only if there exist x, y, u, v in $\backslash Sigma^*$ such that s = xuy, t = xvy, and u R v. Since $\backslash rightarrow\_R$ is a relation on $\backslash Sigma^*$, the pair $(\backslash Sigma^*,\; \backslash rightarrow\_R)$ fits the definition of an abstract rewriting system. Obviously R is subset of $\backslash rightarrow\_R$. If the relation $R$ is symmetric, then the system is called a Thue system.
In a SRS, the reduction relation $\backslash stackrel\{*\}\{\backslash rightarrow\}\_R$ is compatible with the monoid operation, meaning that $x\backslash stackrel\{*\}\{\backslash rightarrow\}\_R\; y$ implies $uxv\backslash stackrel\{*\}\{\backslash rightarrow\}\_R\; uyv$ for all strings x, y, u, v in $\backslash Sigma^*$. Similarly, the reflexive transitive symmetric closure of $\backslash rightarrow\_R$, denoted $\backslash stackrel\{*\}\{\backslash leftrightarrow\}\_R$, is a congruence, meaning it is an equivalence relation (by definition) and it is also compatible with string concatenation. The relation $\backslash stackrel\{*\}\{\backslash leftrightarrow\}\_R$ is called the Thue congruence generated by R. In a Thue system, i.e. if R is symmetric, the rewrite relation $\backslash stackrel\{*\}\{\backslash rightarrow\}\_R$ coincides with the Thue congruence $\backslash stackrel\{*\}\{\backslash leftrightarrow\}\_R$.
The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Since $\backslash stackrel\{*\}\{\backslash leftrightarrow\}\_R$ is a congruence, we can define the factor monoid $\backslash mathcal\{M\}\_R\; =\; \backslash Sigma^*/\backslash stackrel\{*\}\{\backslash leftrightarrow\}\_R$ of the free monoid $\backslash Sigma^*$ by the Thue congruence in the usual manner. If a monoid $\backslash mathcal\{M\}$ is isomorphic with $\backslash mathcal\{M\}\_R$, then the semi-Thue system $(\backslash Sigma,\; R)$ is called a monoid presentation of $\backslash 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 $(\backslash Sigma,\; 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 known as the Post-Markov theorem.^{[12]}
Term rewriting systems
File:Triangle diagram of rewrite rule application.pdf
File:Example term for position, path, depth, match.pdf
A term rewriting system (TRS) is a rewriting system where the objects are terms, or expressions with nested sub-expressions. For example, the system shown under Logic above is a term rewriting system. The terms in this system are composed of binary operators $(\backslash vee)$ and $(\backslash wedge)$ and the unary operator $(\backslash neg)$. Also present in the rules are variables,
these each represent any possible term (though a single variable always represents the same term throughout a single rule).
In contrast to string rewriting systems, whose objects are flat sequences of symbols, the objects a term rewriting system works on, i.e. the terms, form a term algebra. A term can be visualized as a tree of symbols, the set of admitted symbols being fixed by a given signature.
Formal definition
A term rewriting rule is a pair of terms, commonly written as $l\; \backslash longrightarrow\; r$, to indicate that the left hand side $l$ can be replaced by the right hand side $r$. A term rewriting system is a set $R$ of such rules. A rule $l\; \backslash longrightarrow\; r$ can be applied to a term $s$ if the left term $l$ matches some subterm of $s$, that is, if $s\; \backslash mid\_p\; =\; l\; \backslash sigma$
^{[13]}
for some position $p$ in $s$ and some substitution $\backslash sigma$. The result term $t$ of this rule application is then obtained as $t\; =\; s[r\; \backslash sigma]\_p$;
^{[14]}
see picture 1. In this case, $s$ is said to be rewritten in one step, or rewritten directly, to $t$ by the system $R$, formally denoted as $s\; \backslash longrightarrow\_R\; t$, or as $s\; \backslash stackrel\{R\}\{\backslash longrightarrow\}\; t$ by some authors.
If a term $t\_1$ can be rewritten in several steps into a term $t\_n$, that is, if $t\_1\; \backslash longrightarrow\_R\; t\_2\; \backslash longrightarrow\_R\; \backslash ldots\; \backslash longrightarrow\_R\; t\_n$, the term $t\_1$ is said to be rewritten to $t\_n$, formally denoted as $t\_1\; \backslash longrightarrow\_R^+\; t\_n$.
In other words, the relation $\backslash longrightarrow\_R^+$ is the transitive closure of the relation $\backslash longrightarrow\_R$;
often, also the notation $\backslash longrightarrow\_R^*$ is used to denote the reflexive-transitive closure of $\backslash longrightarrow\_R$, that is,
$s\; \backslash longrightarrow\_R^*\; t$ if $s\; =\; t$ or $s\; \backslash longrightarrow\_R^+\; t$.
^{[15]}
A term rewriting given by a set $R$ of rules can be viewed as an abstract rewriting system as defined above, with terms as its objects and $\backslash longrightarrow\_R$ as its rewrite relation.
For example, $x*(y*z)\; \backslash longrightarrow\; (x*y)*z$ is a rewrite rule, commonly used to establish a normal form with respect to the associativity of $*$.
That rule can be applied at the numerator in the term $\backslash frac\{a*((a+1)*(a+2))\}\{1*(2*3)\}$ with the matching substitution $\backslash \{\; x\; \backslash mapsto\; a,\; \backslash ;\; y\; \backslash mapsto\; a+1,\; \backslash ;\; z\; \backslash mapsto\; a+2\; \backslash \}$, see picture 2.
^{[16]}
Applying that substitution to the rule's right hand side yields the term $(a*(a+1))*(a+2)$, and replacing the numerator by that term yields $\backslash frac\{(a*(a+1))*(a+2)\}\{1*(2*3)\}$, which is the result term of applying the rewrite rule.
Altogether, applying the rewrite rule has achieved what is called "using the associativity law for $*$ to $\backslash frac\{a*((a+1)*(a+2))\}\{1*(2*3)\}$" in elementary algebra.
Alternatively, the rule could have been applied again to the denominator of the original term, yielding $\backslash frac\{a*((a+1)*(a+2))\}\{(1*2)*3\}$.
Termination
Beyond section #Termination and convergence, additional subtleties are to be considered for term rewriting systems.
Termination even of a system consisting of one rule with a linear left hand side is undecidable.^{[17]}
Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems.
^{[18]}
The following examples of terminating term rewrite systems are due to Toyama:^{[19]} $f(0,1,x)\; \backslash rightarrow\; f(x,x,x)$ and $g(x,y)\; \backslash rightarrow\; x,\; \backslash ;\; g(x,y)\; \backslash rightarrow\; y$. Their union is a non-terminating system, since $f(g(0,1),g(0,1),g(0,1))\; \backslash rightarrow\; f(0,g(0,1),g(0,1))\; \backslash rightarrow\; f(0,1,g(0,1))\; \backslash rightarrow\; f(g(0,1),g(0,1),g(0,1))\; \backslash rightarrow\; \backslash ldots$. This result disproves a conjecture of Dershowitz,^{[20]} who claimed that the union of two terminating term rewrite systems $R\_1$ and $R\_2$ is again terminating if all left hand sides of $R\_1$ and right hand sides of $R\_2$ are linear, and there are no "overlaps" between left hand sides of $R\_1$ and right hand sides of $R\_2$. All these properties are satisfied by Toyama's examples.
Graph rewriting systems
A generalization of term rewrite systems are graph rewrite systems, operating on graphs instead of (ground-) terms / their corresponding tree representation.
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.
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.
See also
Notes
Further reading
- 316 pages. A textbook suitable for undergraduates.
- Marc Bezem, Jan Willem Klop, Roel de Vrijer ("Terese"), ISBN 0-521-39115-6. 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 preprint of this chapter is freely available from the authors, but it misses the figures.
- Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition, Academic Press, ISBN 0-12-206382-1.
- Sinyor, J.; "The 3x+1 Problem as a String Rewriting System", International Journal of Mathematics and Mathematical Sciences, Volume 2010 (2010), Article ID 458563, 6 pages.
External links
- The Rewriting Home Page
- IFIP Working Group 1.6
- University of Innsbruck
- Termination Portal
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.