Rewriting

In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system.[5] The rules of an example of such a system would be:

${\displaystyle \neg \neg A\to A}$ (double negation elimination)

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

${\displaystyle \neg (A\lor B)\to \neg A\land \neg B}$

${\displaystyle (A\land B)\lor C\to (A\lor C)\land (B\lor C)}$ (distributivity)

${\displaystyle A\lor (B\land C)\to (A\lor B)\land (A\lor C),}$[note 1]

where the symbol (${\displaystyle \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.

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.[6]

${\displaystyle {\begin{aligned}A+0&\to A&{\textrm {(1)}},\\A+S(B)&\to S(A+B)&{\textrm {(2)}},\\A\cdot 0&\to 0&{\textrm {(3)}},\\A\cdot S(B)&\to A+(A\cdot B)&{\textrm {(4)}}.\end{aligned}}}$

For example, the computation of 2+2 to result in 4 can be duplicated by term rewriting as follows:

${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(\;S(S(0))+S(0)\;)}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(S(\;S(S(0))+0\;))}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle 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:

${\displaystyle S(S(0))\cdot S(S(0))}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))\cdot S(0)}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+S(S(0)\cdot 0)}$ ${\displaystyle \;\;{\stackrel {(3)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+0)}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {\textrm {s.a.}}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

where the last step comprises the previous example computation.

In linguistics, rewrite rules, also called phrase structure rules, are used in some systems of generative grammar,[7] 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.

An object x in A is called reducible if there exists some other y in A such that ${\displaystyle x\rightarrow y}$; otherwise it is called irreducible or a normal form. An object y is called a normal form of x if ${\displaystyle x{\stackrel {*}{\,\rightarrow \,}}y}$, and y is irreducible. If x has a unique normal form, then this is usually denoted with ${\displaystyle x{\downarrow }}$. In example 1 above, c is a normal form, and ${\displaystyle 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 to be joinable if there exists some z with the property that ${\displaystyle x{\stackrel {*}{\,\rightarrow \,}}z{\stackrel {*}{\,\leftarrow \,}}y}$. From this definition, it is apparent that one may define the joinability relation as ${\displaystyle {\stackrel {*}{\,\rightarrow }}\circ {\stackrel {*}{\,\leftarrow }}}$, where ${\displaystyle \circ }$ is the composition of relations. Joinability is usually denoted, somewhat confusingly, also with ${\displaystyle \downarrow }$, but in this notation the down arrow is a binary relation, i.e. we write ${\displaystyle x\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 ${\displaystyle {\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 ${\displaystyle {\stackrel {*}{\leftrightarrow }}}$. The word problem for an ARS is undecidable in general.

An ARS is said to possess the Church–Rosser property if ${\displaystyle x{\stackrel {*}{\,\leftrightarrow \,}}y}$ implies ${\displaystyle x\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;[12] hence the name of the property.[13] (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 ${\displaystyle (A,\rightarrow )}$ is said:

• confluent if for all w, x, and y in A, ${\displaystyle x{\stackrel {*}{\,\leftarrow \,}}w{\stackrel {*}{\,\rightarrow \,}}y}$ implies ${\displaystyle x\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, ${\displaystyle x\leftarrow w\rightarrow y}$ implies ${\displaystyle x\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.[14]

Corollary.[15] In a confluent ARS if ${\displaystyle x{\stackrel {*}{\,\leftrightarrow \,}}y}$ then

• If both x and y are normal forms, then x = y.
• If y is a normal form, then ${\displaystyle 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.[16] 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 ${\displaystyle 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 [note 2] 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 ${\displaystyle a\rightarrow b,\;b\rightarrow a,\;a\rightarrow c,\;b\rightarrow d}$ is locally confluent, but not confluent, as ${\displaystyle c}$ and ${\displaystyle d}$ are equivalent, but not joinable.[17]

An abstract rewriting system is said to be terminating or noetherian if there is no infinite chain ${\displaystyle 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 ${\displaystyle 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.

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

A term rewriting rule is a pair of terms, commonly written as ${\displaystyle l\rightarrow 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 ${\displaystyle l\rightarrow r}$ can be applied to a term s if the left term l matches some subterm of s, that is, if ${\displaystyle s|_{p}=l\sigma }$ for some position p in s and some substitution ${\displaystyle \sigma }$.[note 3] The result term t of this rule application is then obtained as ${\displaystyle t=s[r\sigma ]_{p}}$;[note 4] see picture 1. In this case, ${\displaystyle s}$ is said to be rewritten in one step, or rewritten directly, to ${\displaystyle t}$ by the system ${\displaystyle R}$, formally denoted as ${\displaystyle s\rightarrow _{R}t}$, ${\displaystyle s\,{\xrightarrow[{R}]{}}\,t}$, or as ${\displaystyle s\,{\xrightarrow {R}}\,t}$ by some authors.

If a term ${\displaystyle t_{1}}$ can be rewritten in several steps into a term ${\displaystyle t_{n}}$, that is, if ${\displaystyle t_{1}\,{\xrightarrow[{R}]{}}\,t_{2}\,{\xrightarrow[{R}]{}}\,\ldots \,{\xrightarrow[{R}]{}}\,t_{n}}$, the term ${\displaystyle t_{1}}$ is said to be rewritten to ${\displaystyle t_{n}}$, formally denoted as ${\displaystyle t_{1}\,{\xrightarrow[{R}]{+}}\,t_{n}}$. In other words, the relation ${\displaystyle {\xrightarrow[{R}]{+}}}$ is the transitive closure of the relation ${\displaystyle {\xrightarrow[{R}]{}}}$; often, also the notation ${\displaystyle {\xrightarrow[{R}]{*}}}$ is used to denote the reflexive-transitive closure of ${\displaystyle {\xrightarrow[{R}]{}}}$, that is, ${\displaystyle s\,{\xrightarrow[{R}]{*}}\,t}$ if s = t or ${\displaystyle s\,{\xrightarrow[{R}]{+}}\,t}$.[19] A term rewriting given by a set ${\displaystyle R}$ of rules can be viewed as an abstract rewriting system as defined above, with terms as its objects and ${\displaystyle {\xrightarrow[{R}]{}}}$ as its rewrite relation.

For example, ${\displaystyle x*(y*z)\rightarrow (x*y)*z}$ is a rewrite rule, commonly used to establish a normal form with respect to the associativity of ${\displaystyle *}$. That rule can be applied at the numerator in the term ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$ with the matching substitution ${\displaystyle \{x\mapsto a,\;y\mapsto a+1,\;z\mapsto a+2\}}$, see picture 2.[note 5] 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 ${\displaystyle {\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 "applying the associativity law for ${\displaystyle *}$ to ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$" in elementary algebra. Alternately, the rule could have been applied to the denominator of the original term, yielding ${\displaystyle {\frac {a*((a+1)*(a+2))}{(1*2)*3}}}$.

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.[20] Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems. [21]

The following term rewrite system is normalizing,[note 6] but not terminating,[note 7] and not confluent:[22]

${\displaystyle f(x,x)\rightarrow g(x),}$

${\displaystyle f(x,g(x))\rightarrow b,}$

${\displaystyle h(c,x)\rightarrow f(h(x,c),h(x,x)).}$

The following two examples of terminating term rewrite systems are due to Toyama:[23]

${\displaystyle f(0,1,x)\rightarrow f(x,x,x)}$

and

${\displaystyle g(x,y)\rightarrow x,}$

${\displaystyle g(x,y)\rightarrow y.}$

Their union is a non-terminating system, since ${\displaystyle f(g(0,1),g(0,1),g(0,1))\rightarrow f(0,g(0,1),g(0,1))\rightarrow f(0,1,g(0,1))\rightarrow f(g(0,1),g(0,1),g(0,1))\rightarrow \ldots }$. This result disproves a conjecture of Dershowitz,[24] who claimed that the union of two terminating term rewrite systems ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$ is again terminating if all left-hand sides of ${\displaystyle R_{1}}$ and right-hand sides of ${\displaystyle R_{2}}$ are linear, and there are no "overlaps" between left-hand sides of ${\displaystyle R_{1}}$ and right-hand sides of ${\displaystyle 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.

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