Rewriting

For other uses, seeRewriting (disambiguation).

Inmathematics,computer science,andlogic,rewritingcovers a wide range of methods of replacing subterms of aformulawith other terms. Such methods may be achieved byrewriting systems(also known asrewrite systems,rewrite engines,orreduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

Rewriting can benon-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 analgorithmfor changing one term to another, but a set of possible rule applications. When combined with an appropriate algorithm, however, rewrite systems can be viewed ascomputer programs,and severaltheorem proversanddeclarative programming languagesare based on term rewriting.

Example cases

Logic

Inlogic,the procedure for obtaining theconjunctive normal form(CNF) of a formula can be implemented as a rewriting system.The rules of an example of such a system would be:

$\neg \neg A\to A$(double negation 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 symbol ($\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 isequivalentto 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 onnatural numbers. To this end, each such number has to be encoded as aterm. The simplest encoding is the one used in thePeano axioms,based on the constant 0 (zero) and thesuccessor functionS.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.

${\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:

$S(S(0))+S(S(0))$$\;\;{\stackrel {(2)}{\to }}\;\;$$S(\;S(S(0))+S(0)\;)$$\;\;{\stackrel {(2)}{\to }}\;\;$$S(S(\;S(S(0))+0\;))$$\;\;{\stackrel {(1)}{\to }}\;\;$$S(S(S(S(0)))),$

where the rule numbers are given above therewrites-toarrow.

As another example, the computation of 2⋅2 looks like:

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

where the last step comprises the previous example computation.

Linguistics

Inlinguistics,phrase structure rules,also calledrewrite rules,are used in some systems ofgenerative grammar,as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form${\rm {A\rightarrow X}}$,where A is asyntactic categorylabel, such asnoun phraseorsentence,and X is a sequence of such labels ormorphemes,expressing the fact that A can be replaced by X in generating the constituent structure of a sentence. For example, the rule${\rm {S\rightarrow NP\ VP}}$means that a sentence can consist of a noun phrase (NP) followed by averb phrase(VP); further rules will specify what sub-constituents a noun phrase and a verb phrase can consist of, and so on.

Abstract rewriting systems

Main article:Abstract rewriting system

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 anabstract reduction systemorabstract rewriting system(abbreviatedARS).An ARS is simply a setAof objects, together with abinary relation→ onAcalled thereduction relation,rewrite relationor justreduction.

Many notions and notations can be defined in the general setting of an ARS.${\overset {*}{\rightarrow }}$is thereflexive transitive closureof$\rightarrow$.$\leftrightarrow$is thesymmetric closureof$\rightarrow$.${\overset {*}{\leftrightarrow }}$is thereflexive transitive symmetric closureof$\rightarrow$.Theword problemfor an ARS is determining, givenxandy,whether$x{\overset {*}{\leftrightarrow }}y$.An objectxinAis calledreducibleif there exists some otheryinAsuch that$x\rightarrow y$;otherwise it is calledirreducibleor anormal form.An objectyis called a "normal form ofx"if$x{\stackrel {*}{\rightarrow }}y$,andyis irreducible. If the normal form ofxis unique, then this is usually denoted with$x{\downarrow }$.If every object has at least one normal form, the ARS is callednormalizing.$x\downarrow y$orxandyare said to bejoinableif there exists somezwith the property that$x{\overset {*}{\rightarrow }}z{\overset {*}{\leftarrow }}y$.An ARS is said to possess theChurch–Rosser propertyif$x{\overset {*}{\leftrightarrow }}y$implies$x\downarrow y$.An ARS isconfluentif for allw,x,andyinA,$x{\overset {*}{\leftarrow }}w{\overset {*}{\rightarrow }}y$implies$x\downarrow y$.An ARS islocally confluentif and only if for allw,x,andyinA,$x\leftarrow w\rightarrow y$implies$x{\mathbin {\downarrow }}y$.An ARS is said to beterminatingornoetherianif there is no infinite chain$x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots$.A confluent and terminating ARS is calledconvergentorcanonical.

Important theorems for abstract rewriting systems are that an ARS isconfluentiffit has the Church–Rosser property,Newman's lemma(a terminating ARS is confluent if and only if it is locally confluent), and that theword problemfor an ARS isundecidablein general.

String rewriting systems

Main article:String rewriting system

Astring rewriting system(SRS), also known assemi-Thue system,exploits thefree monoidstructure of thestrings(words) over analphabetto extend a rewriting relation,$R$,toallstrings in the alphabet that contain left- and respectively right-hand sides of some rules assubstrings.Formally a semi-Thue system is atuple$(\Sigma,R)$where$\Sigma$is a (usually finite) alphabet, and$R$is a binary relation between some (fixed) strings in the alphabet, called the set ofrewrite rules.Theone-step rewriting relation${\underset {R}{\rightarrow }}$induced by$R$on$\Sigma ^{*}$is defined as: if$s,t\in \Sigma ^{*}$are any strings, then$s{\underset {R}{\rightarrow }}t$if there exist$x,y,u,v\in \Sigma ^{*}$such that$s=xuy$,$t=xvy$,and$uRv$.Since${\underset {R}{\rightarrow }}$is a relation on$\Sigma ^{*}$,the pair$(\Sigma ^{*},{\underset {R}{\rightarrow }})$fits the definition of an abstract rewriting system. Since the empty string is in$\Sigma ^{*}$,$R$is a subset of${\underset {R}{\rightarrow }}$.If the relation$R$issymmetric,then the system is called aThue system.

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

The notion of a semi-Thue system essentially coincides with thepresentation of a monoid.Since${\overset {*}{\underset {R}{\leftrightarrow }}}$is a congruence, we can define thefactor monoid${\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}$of the free monoid$\Sigma ^{*}$by the Thue congruence. If a monoid${\mathcal {M}}$isisomorphicwith${\mathcal {M}}_{R}$,then the semi-Thue system$(\Sigma,R)$is called amonoid presentationof${\mathcal {M}}$.

We immediately get some very useful connections with other areas of algebra. For example, the alphabet$\{a,b\}$with the rules$\{ab\rightarrow \varepsilon,ba\rightarrow \varepsilon \}$,where$\varepsilon$is theempty string,is a presentation of thefree groupon one generator. If instead the rules are just$\{ab\rightarrow \varepsilon \}$,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$(\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 thePost–Markov theorem.

Term rewriting systems

Pic.1:Schematic triangle diagram of application of a rewrite rule$l\longrightarrow r$at position$p$in a term, with matching substitution$\sigma$

Pic.2:Rule lhs term$x*(y*z)$matching in term${\frac {a*((a+1)*(a+2))}{1*(2*3)}}$

Aterm rewriting system(TRS) is a rewriting system whose objects areterms,which are expressions with nested sub-expressions. For example, the system shown under§ Logicabove is a term rewriting system. The terms in this system are composed of binary operators$(\vee )$and$(\wedge )$and the unary operator$(\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 aterm algebra.A term can be visualized as a tree of symbols, the set of admitted symbols being fixed by a givensignature.As a formalism, term rewriting systems have the full power ofTuring machines,that is, everycomputable functioncan be defined by a term rewriting system.

Formal definition

"Redex" redirects here. For the medication, seeTadalafil.

Arewrite ruleis a pair ofterms,commonly written as$l\rightarrow r$,to indicate that the left-hand sidelcan be replaced by the right-hand sider.Aterm rewriting systemis a setRof such rules. A rule$l\rightarrow r$can beappliedto a termsif the left termlmatchessomesubtermofs,that is, if there is somesubstitution$\sigma$such that the subterm of$s$rooted at somepositionpis the result of applying the substitution$\sigma$to the terml.The subterm matching the left hand side of the rule is called aredexorreducible expression.The result termtof this rule application is then the result ofreplacing the subtermat positionpinsby the term$r$with the substitution$\sigma$applied, see picture 1. In this case,$s$is said to berewritten in one step,orrewritten directly,to$t$by the system$R$,formally denoted as$s\rightarrow _{R}t$,$s{\underset {R}{\rightarrow }}t$,or as$s{\overset {R}{\rightarrow }}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}{\underset {R}{\rightarrow }}t_{2}{\underset {R}{\rightarrow }}\cdots {\underset {R}{\rightarrow }}t_{n}$,the term$t_{1}$is said to berewrittento$t_{n}$,formally denoted as$t_{1}{\overset {+}{\underset {R}{\rightarrow }}}t_{n}$.In other words, the relation${\overset {+}{\underset {R}{\rightarrow }}}$is thetransitive closureof the relation${\underset {R}{\rightarrow }}$;often, also the notation${\overset {*}{\underset {R}{\rightarrow }}}$is used to denote thereflexive-transitive closureof${\underset {R}{\rightarrow }}$,that is,$s{\overset {*}{\underset {R}{\rightarrow }}}t$if$s=t$or$s{\overset {+}{\underset {R}{\rightarrow }}}t$.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${\underset {R}{\rightarrow }}$as its rewrite relation.

For example,$x*(y*z)\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${\frac {a*((a+1)*(a+2))}{1*(2*3)}}$with the matching substitution$\{x\mapsto a,\;y\mapsto a+1,\;z\mapsto a+2\}$,see picture 2.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${\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$*$to${\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${\frac {a*((a+1)*(a+2))}{(1*2)*3}}$.

Termination

Termination issues of rewrite systems in general are handled inAbstract 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 alinearleft-hand side is undecidable.Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finitegroundsystems.

The following term rewrite system is normalizing,but not terminating,and not confluent: $${\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:

$f(0,1,x)\rightarrow f(x,x,x)$

and

$g(x,y)\rightarrow x,$

$g(x,y)\rightarrow y.$

Their union is a non-terminating system, since

$${\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 ofDershowitz,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}$arelinear,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.

SeeRewrite orderandPath ordering (term rewriting)for ordering relations used in termination proofs for term rewriting systems.

Higher-order rewriting systems

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

Graph rewriting systems

Graph rewrite systemsare another generalization of term rewrite systems, operating ongraphsinstead of (ground-)terms/ their correspondingtreerepresentation.

Trace rewriting systems

Trace theoryprovides a means for discussing multiprocessing in more formal terms, such as via thetrace monoidand thehistory monoid.Rewriting can be performed in trace systems as well.

See also

• Critical pair (logic)
• Compiler
• Knuth–Bendix completion algorithm
• L-systemsspecify rewriting that is done in parallel.
• Referential transparencyin computer science
• Regulated rewriting
• Interaction Nets

Further reading

• Baader, Franz;Nipkow, Tobias(1999).Term rewriting and all that.Cambridge University Press.ISBN978-0-521-77920-3.316 pages.
• Marc Bezem,Jan Willem Klop,Roel de Vrijer( "Terese" ),Term Rewriting Systems( "TeReSe" ), Cambridge University Press, 2003,ISBN0-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.
• Nachum DershowitzandJean-Pierre Jouannaud"Rewrite Systems",Chapter 6 inJan van Leeuwen(Ed.),Handbook of Theoretical Computer Science,Volume B: Formal Models and Semantics.,Elsevier and MIT Press, 1990,ISBN0-444-88074-7,pp. 243–320. Thepreprintof this chapter is freely available from the authors, but it is missing the figures.
• Nachum Dershowitz andDavid Plaisted."Rewriting",Chapter 9 inJohn Alan RobinsonandAndrei Voronkov(Eds.),Handbook of Automated Reasoning,Volume 1.
• Gérard Huetet 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 inSamson Abramsky,Dov M. GabbayandTom Maibaum(Eds.),Handbook of Logic in Computer Science,Volume 2: Background: Computational Structures.
• David Plaisted."Equational reasoning and term rewriting systems",inDov M. Gabbay,C. J. HoggerandJohn 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. Bookand Friedrich Otto,String-Rewriting Systems,Springer (1993).
• Benjamin Benninghofen, Susanne Kemmerich andMichael M. Richter,Systems of Reductions.LNCS277,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,ISBN0-12-206382-1.

External links

• TheRewriting Home Page
• IFIP Working Group 1.6
• Researchers in rewritingbyAart Middeldorp,University of Innsbruck
• Termination Portal
• Maude System— a software implementation of a generic term rewriting system.