Rewriting

In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system.[6] 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.[7]

${\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, phrase structure rules, also called rewrite rules, are used in some systems of generative grammar,[8] as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form ${\displaystyle {\rm {A\rightarrow 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 ${\displaystyle {\rm {S\rightarrow NP\ VP}}}$ means that a sentence can consist of a noun phrase (NP) followed by a verb phrase (VP); further rules will specify what sub-constituents a noun phrase and a verb phrase can consist of, and so on.

A rewrite 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 there is some substitution ${\displaystyle \sigma }$ such that the subterm of ${\displaystyle s}$ rooted at some position p is the result of applying the substitution ${\displaystyle \sigma }$ to the term l. The subterm matching the left hand side of the rule is called a redex or reducible expression.[13] The result term t of this rule application is then the result of replacing the subterm at position p in s by the term ${\displaystyle r}$ with the substitution ${\displaystyle \sigma }$ applied, 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{\underset {R}{\rightarrow }}t}$, or as ${\displaystyle s{\overset {R}{\rightarrow }}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}{\underset {R}{\rightarrow }}t_{2}{\underset {R}{\rightarrow }}\cdots {\underset {R}{\rightarrow }}t_{n}}$, the term ${\displaystyle t_{1}}$ is said to be rewritten to ${\displaystyle t_{n}}$, formally denoted as ${\displaystyle t_{1}{\overset {+}{\underset {R}{\rightarrow }}}t_{n}}$. In other words, the relation ${\displaystyle {\overset {+}{\underset {R}{\rightarrow }}}}$ is the transitive closure of the relation ${\displaystyle {\underset {R}{\rightarrow }}}$; often, also the notation ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ is used to denote the reflexive-transitive closure of ${\displaystyle {\underset {R}{\rightarrow }}}$, that is, ${\displaystyle s{\overset {*}{\underset {R}{\rightarrow }}}t}$ if ${\displaystyle s=t}$ or ${\displaystyle s{\overset {+}{\underset {R}{\rightarrow }}}t}$.[14] 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 {\underset {R}{\rightarrow }}}$ 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 2] Applying that substitution to the rule's right-hand side yields the term ${\displaystyle (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}}}$.

Termination issues of rewrite systems in general are handled in Abstract rewriting system#Termination and convergence. For term rewriting systems in particular, the following additional subtleties are to be considered.

Termination even of a system consisting of one rule with a linear left-hand side is undecidable.[15][16] Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems.[17]

The following term rewrite system is normalizing,[note 3] but not terminating,[note 4] and not confluent:[18]

$${\displaystyle {\begin{aligned}f(x,x)&\rightarrow g(x),\\f(x,g(x))&\rightarrow b,\\h(c,x)&\rightarrow f(h(x,c),h(x,x)).\\\end{aligned}}}$$

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

${\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 {\begin{aligned}&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 &\cdots \end{aligned}}}$$

This result disproves a conjecture of Dershowitz,[20] 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.

Higher-order rewriting systems are a generalization of first-order term rewriting systems to lambda terms, allowing higher order functions and bound variables.[21] Various results about first-order TRSs can be reformulated for HRSs as well.[22]

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