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. The objects of focus for this article include rewriting systems (also known as rewrite systems, rewrite engines 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 theorem provers and declarative programming languages are based on term rewriting.

** Example cases **

** Logic **

In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system. The rules of an example of such a system would be:
:$\backslash neg\backslash neg\; A\; \backslash to\; A$ (double negation 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),$This variant of the previous rule is needed since the commutative law ''A''∨''B'' = ''B''∨''A'' cannot be turned into a rewrite rule. A rule like ''A''∨''B'' → ''B''∨''A'' would cause the rewrite system to be nonterminating.
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, and the symbols each denote a subexpression. In such a system, each rule is chosen so that the left side is equivalent to the right side, and consequently when the left side matches a subexpression, performing a rewrite of that subexpression from left to right maintains logical consistency and value of the entire expression.

** Arithmetic **

Term rewriting systems can be employed to compute arithmetic operations on natural numbers.
To this end, each such number has to be encoded as a term.
The simplest encoding is the one used in the Peano axioms, based on the constant 0 (zero) and the successor function ''S''.
for example, the numbers 0, 1, 2, and 3 are represented by the terms 0, S(0), S(S(0)), and S(S(S(0))), respectively.
The following term rewriting system can then be used to compute sum and product of given natural numbers.
: $\backslash begin\; A\; +\; 0\; \&\backslash to\; A\; \&\; \backslash textrm,\; \backslash \backslash \; A\; +\; S(B)\; \&\backslash to\; S\; (A\; +\; B)\; \&\; \backslash textrm,\; \backslash \backslash \; A\; \backslash cdot\; 0\; \&\backslash to\; 0\; \&\; \backslash textrm,\; \backslash \backslash \; A\; \backslash cdot\; S(B)\; \&\backslash to\; A\; +\; (A\; \backslash cdot\; B)\; \&\; \backslash textrm.\; \backslash end$
For example, the computation of 2+2 to result in 4 can be duplicated by term rewriting as follows:
:$S(S(0))\; +\; S(S(0))$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(\; \backslash ;\; S(S(0))\; +\; S(0)\; \backslash ;\; )$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(\; \backslash ;\; S(S(0))\; +\; 0\; \backslash ;\; ))$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(\; S(S(0))\; )),$
where the rule numbers are given above the ''rewrites-to'' arrow.
As another example, the computation of 2⋅2 looks like:
:$S(S(0))\; \backslash cdot\; S(S(0))$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(0))\; +\; S(S(0))\; \backslash cdot\; S(0)$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(0))\; +\; S(S(0))\; +\; S(S(0)\; \backslash cdot\; 0)$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(0))\; +\; S(S(0))\; +\; 0)$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(0))\; +\; S(S(0))$ $\backslash ;\backslash ;\backslash stackrel\backslash ;\backslash ;$ $S(S(\; S(S(0))\; )),$
where the last step comprises the previous example computation.

** Linguistics **

In linguistics, rewrite rules, also called phrase structure rules, are used in some systems of generative grammar, as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form A → X, where A is a syntactic category label, such as noun phrase or sentence, and X is a sequence of such labels or morphemes, expressing the fact that A can be replaced by X in generating the constituent structure of a sentence. For example, the rule S → NP VP means that a sentence can consist of a noun phrase followed by a verb phrase; further rules will specify what sub-constituents a noun phrase and a verb phrase can consist of, and so on.

** Abstract rewriting systems **

From the above examples, it is 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. (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).Book and Otto, p. 10
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 or just reduction. 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'' = 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. In a sense, ''c'' is 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.
* $\backslash stackrel$ is the transitive closure of $\backslash rightarrow\; \backslash cup\; =$, where = is the identity relation, i.e. $\backslash stackrel$ is the smallest preorder (reflexive and transitive relation) containing $\backslash rightarrow$. It is also called the reflexive transitive closure of $\backslash rightarrow$.
* $\backslash leftrightarrow$ is $\backslash rightarrow\; \backslash cup\; \backslash \; \backslash xrightarrow$, that is the union of the relation → with its converse relation, also known as the symmetric closure of $\backslash rightarrow$.
* $\backslash stackrel$ is the transitive closure of $\backslash leftrightarrow\; \backslash cup\; =$, that is $\backslash stackrel$ is the smallest equivalence relation containing $\backslash rightarrow$. It is also known as the reflexive transitive symmetric closure of $\backslash rightarrow$.

** 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\; y$, and ''y'' is irreducible. If ''x'' has a ''unique'' normal form, then this is usually denoted with $x$. In example 1 above, ''c'' is a normal form, and $c\; =\; a\; =\; b$. 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\; z\; \backslash stackrel\; y$. From this definition, it is apparent that one may define the joinability relation as $\backslash stackrel\; \backslash circ\; \backslash stackrel$, 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 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$? 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$. 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 $x\; \backslash stackrel\; y$ implies $x\; \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; hence the name of the property. (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\; w\; \backslash stackrel\; y$ implies $x\; \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 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.
Corollary. In a confluent ARS if $x\; \backslash stackrel\; y$ then
* If both ''x'' and ''y'' are normal forms, then .
* If ''y'' is a normal form, then $x\; \backslash stackrel\; 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. 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\; y$. This definition, found in Book and Otto, is equivalent to common one given here in a confluent system, but it is more inclusive i.e. it considers more objects as a normal form of ''x'' than our definition 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.

** 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 system 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 xrightarrow/math>\; induced\; by$ R$on$ \backslash Sigma^*$is\; defined\; as:\; for\; any\; strings$ s,\; t\; \backslash in\; \backslash Sigma^*$$ s\; \backslash ,\backslash xrightarrow,\; t$if\; and\; only\; if\; there\; exist$ x,\; y,\; u,\; v\; \backslash in\; \backslash Sigma^*$such\; that$ s\; =\; xuy$,$ t\; =\; xvy$,\; and$ u\; R\; v$.\; Since$ \backslash xrightarrow/math>\; is\; a\; relation\; on$ \backslash Sigma^*$,\; the\; pair$ (\backslash Sigma^*,\; \backslash xrightarrow$fits\; the\; definition\; of\; an\; abstract\; rewriting\; system.\; Obviously$ R$is\; a\; subset\; of$ \backslash xrightarrow/math>.\; If\; the\; relation$ R$issymmetric,\; then\; the\; system\; is\; called\; a\; Thue\; system.\; In\; a\; SRS,\; the\; reduction\; relation$ \backslash xrightarrow/math>\; is\; compatible\; with\; the\; monoid\; operation,\; meaning\; that$ x\; \backslash ,\backslash xrightarrow,\; y$implies$ uxv\; \backslash ,\backslash xrightarrow,\; uyv$for\; all\; strings$ x,\; y,\; u,\; v\; \backslash in\; \backslash Sigma^*$.\; Similarly,\; the\; reflexive\; transitive\; symmetric\; closure\; of$ \backslash xrightarrow/math>,\; denoted$ \backslash overset$,\; is\; acongruence,\; meaning\; it\; is\; anequivalence\; relation(by\; definition)\; and\; it\; is\; also\; compatible\; with\; string\; concatenation.\; The\; relation$ \backslash overset$is\; called\; the\; Thue\; congruence\; generated\; by$ R$.\; In\; a\; Thue\; system,\; i.e.\; if$ R$is\; symmetric,\; the\; rewrite\; relation$ \backslash xrightarrow/math>\; coincides\; with\; the\; Thue\; congruence$ \backslash overset$.\; The\; notion\; of\; a\; semi-Thue\; system\; essentially\; coincides\; with\; thepresentation\; of\; a\; monoid.\; Since$ \backslash overset$is\; a\; congruence,\; we\; can\; define\; the\; factor\; monoid$ \backslash mathcal\_R\; =\; \backslash Sigma^*/\backslash overset$of\; the\; free\; monoid$ \backslash Sigma^*$by\; the\; Thue\; congruence\; in\; theusual\; manner.\; If\; a\; monoid$ \backslash mathcal$isisomorphicwith$ \backslash mathcal\_R$,\; then\; the\; semi-Thue\; system$ (\backslash Sigma,\; R)$is\; called\; amonoid\; presentationof$ \backslash mathcal$.\; We\; immediately\; get\; some\; very\; useful\; connections\; with\; other\; areas\; of\; algebra.\; For\; example,\; the\; alphabet\; with\; the\; rules\; ,\; where\; \epsilon \; is\; theempty\; string,\; is\; a\; presentation\; of\; thefree\; groupon\; one\; generator.\; If\; instead\; the\; rules\; are\; just\; ,\; then\; we\; obtain\; a\; presentation\; of\; thebicyclic\; monoid.\; Thus\; semi-Thue\; systems\; constitute\; a\; natural\; framework\; for\; solving\; theword\; problemfor\; monoids\; and\; groups.\; In\; fact,\; every\; monoid\; has\; a\; presentation\; of\; the\; form$ (\backslash Sigma,\; R)$,\; i.e.\; it\; may\; 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.$$$$$$

** Term rewriting systems **

A term rewriting system (TRS) is a rewriting system whose objects are ''terms'', which are expressions with nested sub-expressions. For example, the system shown under ' 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, which 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 sequences of symbols, the objects of a term rewriting system 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 rightarrow\; r$, to indicate that the left-hand side can be replaced by the right-hand side . A term rewriting system is a set of such rules. A rule $l\; \backslash rightarrow\; r$ can be applied to a term if the left term matches some subterm of , that is, if $s|\_p\; =\; l\; \backslash sigma$ for some position in and some substitution $\backslash sigma$.here, $s\; \backslash mid\_p$ denotes the subterm of $s$ rooted at position , while $l\; \backslash sigma$ denotes the result of applying the substitution $\backslash sigma$ to the term The result term of this rule application is then obtained as $t\; =\; s\backslash sigmap$;here, $s\backslash sigmap$ denotes the result of replacing the subterm at position in by the term $r\; \backslash sigma$ 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 rightarrow\_R\; t$, $s\; \backslash ,\backslash xrightarrow,\; t$, or as $s\; \backslash ,\backslash xrightarrow\backslash ,\; 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 ,\backslash xrightarrow,\; t\_2\; \backslash ,\backslash xrightarrow,\; \backslash ldots\; \backslash ,\backslash xrightarrow,\; t\_n$, the term $t\_1$ is said to be rewritten to $t\_n$, formally denoted as $t\_1\; \backslash ,\backslash xrightarrow,\; t\_n$. In other words, the relation $\backslash xrightarrow/math>\; is\; thetransitive\; closureof\; the\; relation$ \backslash xrightarrow/math>;\; often,\; also\; the\; notation$ \backslash xrightarrow/math>\; is\; used\; to\; denote\; thereflexive-transitive\; closureof$ \backslash xrightarrow/math>,\; that\; is,$ s\; \backslash ,\backslash xrightarrow,\; t$if\; or\; A\; term\; rewriting\; given\; by\; a\; set$ R$of\; rules\; can\; be\; viewed\; as\; an\; abstract\; rewriting\; system\; as\; definedabove,\; with\; terms\; as\; its\; objects\; and$ \backslash xrightarrow/math>\; as\; its\; rewrite\; relation.\; For\; example,$ x*(y*z)\; \backslash rightarrow\; (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$with\; the\; matching\; substitution$ \backslash $,\; see\; picture\; 2.since\; applying\; that\; substitution\; to\; the\; rule\text{\'}s\; left\; hand\; side$ x*(y*z)$yields\; the\; numerator$ a*((a+1)*(a+2))$Applying\; that\; substitution\; to\; the\; rule\text{\'}s\; right-hand\; side\; yields\; the\; term\; ,\; and\; replacing\; the\; numerator\; by\; that\; term\; yields$ \backslash frac$,\; which\; is\; the\; result\; term\; of\; applying\; the\; rewrite\; rule.\; Altogether,\; applying\; the\; rewrite\; rule\; has\; achieved\; what\; is\; called\; "applying\; the\; associativity\; law\; for$ *$to$ \backslash frac$"\; in\; elementary\; algebra.\; Alternately,\; the\; rule\; could\; have\; been\; applied\; to\; the\; denominator\; of\; the\; original\; term,\; yielding$ \backslash frac$.$$$$$

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. Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems. The following term rewrite system is normalizing,i.e. for each term, some normal form exists, e.g. ''h''(''c'',''c'') has the normal forms ''b'' and ''g''(''b''), since ''h''(''c'',''c'') → ''f''(''h''(''c'',''c''),''h''(''c'',''c'')) → ''f''(''h''(''c'',''c''),''f''(''h''(''c'',''c''),''h''(''c'',''c''))) → ''f''(''h''(''c'',''c''),''g''(''h''(''c'',''c''))) → ''b'', and ''h''(''c'',''c'') → ''f''(''h''(''c'',''c''),''h''(''c'',''c'')) → ''g''(''h''(''c'',''c''),''h''(''c'',''c'')) → ... → ''g''(''b''); neither ''b'' nor ''g''(''b'') can be rewritten any further, therefore the system is not confluent but not terminating,i.e., there are infinite derivations, e.g. ''h''(''c'',''c'') → ''f''(''h''(''c'',''c''),''h''(''c'',''c'')) → ''f''(''f''(''h''(''c'',''c''),''h''(''c'',''c'')) ,''h''(''c'',''c'')) → ''f''(''f''(''f''(''h''(''c'',''c''),''h''(''c'',''c'')),''h''(''c'',''c'')) ,''h''(''c'',''c'')) → ... and not confluent: :$f(x,x)\; \backslash rightarrow\; g(x),$ :$f(x,g(x))\; \backslash rightarrow\; b,$ :$h(c,x)\; \backslash rightarrow\; f(h(x,c),h(x,x)).$ The following two examples of terminating term rewrite systems are due to Toyama: :$f(0,1,x)\; \backslash rightarrow\; f(x,x,x)$ and :$g(x,y)\; \backslash rightarrow\; x,$ :$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,; here: p.210 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. See Rewrite order and Path ordering (term rewriting) for ordering relations used in termination proofs for term rewriting systems.

** 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

* Critical pair (logic) * Knuth–Bendix completion algorithm * L-systems specify rewriting that is done in parallel. * Referential transparency in computer science * Regulated rewriting * Rho calculus

** Notes **

** References **

** Further reading **

* 316 pages. A textbook suitable for undergraduates.
* Marc Bezem, Jan Willem Klop, Roel de Vrijer ("Terese"), ''Term Rewriting Systems'' ("TeReSe"), Cambridge University Press, 2003, . 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.
* Nachum Dershowitz and Jean-Pierre Jouannaudbr>"Rewrite Systems"

Chapter 6 in Jan van Leeuwen (Ed.), ''Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics.'', Elsevier and MIT Press, 1990, , pp. 243–320. The preprint of this chapter is freely available from the authors, but it is missing the figures. * Nachum Dershowitz and David Plaisted

"Rewriting"

Chapter 9 in John Alan Robinson and Andrei Voronkov (Eds.), ''Handbook of Automated Reasoning, Volume 1''. * Gérard Huet et Derek Oppen

Equations and Rewrite Rules, A Survey

(1980) Stanford Verification Group, Report N° 15 Computer Science Department Report N° STAN-CS-80-785 * Jan Willem Klop. "Term Rewriting Systems", Chapter 1 in Samson Abramsky, Dov M. Gabbay and Tom Maibaum (Eds.), ''Handbook of Logic in Computer Science, Volume 2: Background: Computational Structures''. * David Plaisted

"Equational reasoning and term rewriting systems"

in Dov M. Gabbay, C. J. Hogger and John Alan Robinson (Eds.), ''Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 1''. * Jürgen Avenhaus and Klaus Madlener. "Term rewriting and equational reasoning". In Ranan B. Banerji (Ed.), ''Formal Techniques in Artificial Intelligence: A Sourcebook'', Elsevier (1990). ; String rewriting * Ronald V. Book and Friedrich Otto, ''String-Rewriting Systems'', Springer (1993). * Benjamin Benninghofen, Susanne Kemmerich and Michael M. Richter, ''Systems of Reductions''. LNCS 277, Springer-Verlag (1987). ; Other * Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) ''Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition'', Academic Press, .

** External links **

* Th

Rewriting Home Page

IFIP Working Group 1.6

Researchers in rewriting

by Aart Middeldorp, University of Innsbruck

Termination Portal

{{Authority control Category:Formal languages Category:Logic in computer science Category:Mathematical logic Category:Rewriting systems

Formal definition

A term rewriting rule is a pair of terms, commonly written as $l\; \backslash rightarrow\; r$, to indicate that the left-hand side can be replaced by the right-hand side . A term rewriting system is a set of such rules. A rule $l\; \backslash rightarrow\; r$ can be applied to a term if the left term matches some subterm of , that is, if $s|\_p\; =\; l\; \backslash sigma$ for some position in and some substitution $\backslash sigma$.here, $s\; \backslash mid\_p$ denotes the subterm of $s$ rooted at position , while $l\; \backslash sigma$ denotes the result of applying the substitution $\backslash sigma$ to the term The result term of this rule application is then obtained as $t\; =\; s\backslash sigmap$;here, $s\backslash sigmap$ denotes the result of replacing the subterm at position in by the term $r\; \backslash sigma$ 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 rightarrow\_R\; t$, $s\; \backslash ,\backslash xrightarrow,\; t$, or as $s\; \backslash ,\backslash xrightarrow\backslash ,\; 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 ,\backslash xrightarrow,\; t\_2\; \backslash ,\backslash xrightarrow,\; \backslash ldots\; \backslash ,\backslash xrightarrow,\; t\_n$, the term $t\_1$ is said to be rewritten to $t\_n$, formally denoted as $t\_1\; \backslash ,\backslash xrightarrow,\; t\_n$. In other words, the relation $\backslash xrightarrow/math>\; is\; thetransitive\; closureof\; the\; relation$ \backslash xrightarrow/math>;\; often,\; also\; the\; notation$ \backslash xrightarrow/math>\; is\; used\; to\; denote\; thereflexive-transitive\; closureof$ \backslash xrightarrow/math>,\; that\; is,$ s\; \backslash ,\backslash xrightarrow,\; t$if\; or\; A\; term\; rewriting\; given\; by\; a\; set$ R$of\; rules\; can\; be\; viewed\; as\; an\; abstract\; rewriting\; system\; as\; definedabove,\; with\; terms\; as\; its\; objects\; and$ \backslash xrightarrow/math>\; as\; its\; rewrite\; relation.\; For\; example,$ x*(y*z)\; \backslash rightarrow\; (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$with\; the\; matching\; substitution$ \backslash $,\; see\; picture\; 2.since\; applying\; that\; substitution\; to\; the\; rule\text{\'}s\; left\; hand\; side$ x*(y*z)$yields\; the\; numerator$ a*((a+1)*(a+2))$Applying\; that\; substitution\; to\; the\; rule\text{\'}s\; right-hand\; side\; yields\; the\; term\; ,\; and\; replacing\; the\; numerator\; by\; that\; term\; yields$ \backslash frac$,\; which\; is\; the\; result\; term\; of\; applying\; the\; rewrite\; rule.\; Altogether,\; applying\; the\; rewrite\; rule\; has\; achieved\; what\; is\; called\; "applying\; the\; associativity\; law\; for$ *$to$ \backslash frac$"\; in\; elementary\; algebra.\; Alternately,\; the\; rule\; could\; have\; been\; applied\; to\; the\; denominator\; of\; the\; original\; term,\; yielding$ \backslash frac$.$$$$$

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. Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems. The following term rewrite system is normalizing,i.e. for each term, some normal form exists, e.g. ''h''(''c'',''c'') has the normal forms ''b'' and ''g''(''b''), since ''h''(''c'',''c'') → ''f''(''h''(''c'',''c''),''h''(''c'',''c'')) → ''f''(''h''(''c'',''c''),''f''(''h''(''c'',''c''),''h''(''c'',''c''))) → ''f''(''h''(''c'',''c''),''g''(''h''(''c'',''c''))) → ''b'', and ''h''(''c'',''c'') → ''f''(''h''(''c'',''c''),''h''(''c'',''c'')) → ''g''(''h''(''c'',''c''),''h''(''c'',''c'')) → ... → ''g''(''b''); neither ''b'' nor ''g''(''b'') can be rewritten any further, therefore the system is not confluent but not terminating,i.e., there are infinite derivations, e.g. ''h''(''c'',''c'') → ''f''(''h''(''c'',''c''),''h''(''c'',''c'')) → ''f''(''f''(''h''(''c'',''c''),''h''(''c'',''c'')) ,''h''(''c'',''c'')) → ''f''(''f''(''f''(''h''(''c'',''c''),''h''(''c'',''c'')),''h''(''c'',''c'')) ,''h''(''c'',''c'')) → ... and not confluent: :$f(x,x)\; \backslash rightarrow\; g(x),$ :$f(x,g(x))\; \backslash rightarrow\; b,$ :$h(c,x)\; \backslash rightarrow\; f(h(x,c),h(x,x)).$ The following two examples of terminating term rewrite systems are due to Toyama: :$f(0,1,x)\; \backslash rightarrow\; f(x,x,x)$ and :$g(x,y)\; \backslash rightarrow\; x,$ :$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,; here: p.210 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. See Rewrite order and Path ordering (term rewriting) for ordering relations used in termination proofs for term rewriting systems.

See also

* Critical pair (logic) * Knuth–Bendix completion algorithm * L-systems specify rewriting that is done in parallel. * Referential transparency in computer science * Regulated rewriting * Rho calculus

Chapter 6 in Jan van Leeuwen (Ed.), ''Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics.'', Elsevier and MIT Press, 1990, , pp. 243–320. The preprint of this chapter is freely available from the authors, but it is missing the figures. * Nachum Dershowitz and David Plaisted

"Rewriting"

Chapter 9 in John Alan Robinson and Andrei Voronkov (Eds.), ''Handbook of Automated Reasoning, Volume 1''. * Gérard Huet et Derek Oppen

Equations and Rewrite Rules, A Survey

(1980) Stanford Verification Group, Report N° 15 Computer Science Department Report N° STAN-CS-80-785 * Jan Willem Klop. "Term Rewriting Systems", Chapter 1 in Samson Abramsky, Dov M. Gabbay and Tom Maibaum (Eds.), ''Handbook of Logic in Computer Science, Volume 2: Background: Computational Structures''. * David Plaisted

"Equational reasoning and term rewriting systems"

in Dov M. Gabbay, C. J. Hogger and John Alan Robinson (Eds.), ''Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 1''. * Jürgen Avenhaus and Klaus Madlener. "Term rewriting and equational reasoning". In Ranan B. Banerji (Ed.), ''Formal Techniques in Artificial Intelligence: A Sourcebook'', Elsevier (1990). ; String rewriting * Ronald V. Book and Friedrich Otto, ''String-Rewriting Systems'', Springer (1993). * Benjamin Benninghofen, Susanne Kemmerich and Michael M. Richter, ''Systems of Reductions''. LNCS 277, Springer-Verlag (1987). ; Other * Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) ''Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition'', Academic Press, .

Rewriting Home Page

IFIP Working Group 1.6

Researchers in rewriting

by Aart Middeldorp, University of Innsbruck

Termination Portal

{{Authority control Category:Formal languages Category:Logic in computer science Category:Mathematical logic Category:Rewriting systems