Inmathematics,computer science, andlogic,rewriting covers a wide range of methods of replacing subterms of aformula with other terms. Such methods may be achieved byrewriting systems (also known asrewrite systems,rewrite engines,^[1][2] orreduction systems). In their most basic form, they consist of a set of objects, plusrelations 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 analgorithm 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 ascomputer programs, and severaltheorem provers^[3] anddeclarative programming languages are based on term rewriting.^[4][5]

Inlogic, the procedure for obtaining theconjunctive normal form (CNF) of a formula can be implemented as a rewriting system.^[6] For example, the rules of such a system would be:

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

${\displaystyle \mathrm{\neg }(A\wedge B)\to \mathrm{\neg }A\vee \mathrm{\neg }B}$ (De Morgan's laws)

${\displaystyle \mathrm{\neg }(A\vee B)\to \mathrm{\neg }A\wedge \mathrm{\neg }B}$

${\displaystyle (A\wedge B)\vee C\to (A\vee C)\wedge (B\vee C)}$ (distributivity)

${\displaystyle A\vee (B\wedge C)\to (A\vee B)\wedge (A\vee C),}$^{[note 1]}

For each rule, eachvariable denotes a subexpression, and the symbol (${\displaystyle \to }$) indicates that an expression matching the left hand side of it can be rewritten to one matching the right hand side of it. In such a system, each rule is alogical equivalence, so performing a rewrite on an expression by these rules does not change the truth value of it. Other useful rewriting systems in logic may not preserve truth values, see e.g.equisatisfiability.

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

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 notation above each arrow indicates the rule used for each rewrite.

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{\text{s.a.}}{\to }}$${\displaystyle S(S(S(S(0)))),}$

where the last step comprises the previous example computation.

Inlinguistics,phrase structure rules, also calledrewrite rules, are used in some systems ofgenerative grammar,^[8] as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form${\displaystyle \mathrm{A}\to \mathrm{X}}$, where A is asyntactic category label, such asnoun phrase orsentence, 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${\displaystyle \mathrm{S}\to \mathrm{N}\mathrm{P}\mathrm{V}\mathrm{P}}$ 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.

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 system^[9] orabstract rewriting system (abbreviatedARS).^[10] An ARS is simply a setA of objects, together with abinary relation → onA called thereduction relation,rewrite relation^[11] or justreduction.^[9]

Many notions and notations can be defined in the general setting of an ARS.${\displaystyle \stackrel{\ast }{\to }}$ is thereflexive transitive closure of${\displaystyle \to }$.${\displaystyle \leftrightarrow }$ is thesymmetric closure of${\displaystyle \to }$.${\displaystyle \stackrel{\ast }{\leftrightarrow }}$ is thereflexive transitive symmetric closure of${\displaystyle \to }$. Theword problem for an ARS is determining, givenx andy, whether${\displaystyle x\stackrel{\ast }{\leftrightarrow }y}$. An objectx inA is calledreducible if there exists some othery inA such that${\displaystyle x\to y}$; otherwise it is calledirreducible or anormal form. An objecty is called a "normal form ofx" if${\displaystyle x\stackrel{\ast }{\to }y}$, andy is irreducible. If the normal form ofx is unique, then this is usually denoted with${\displaystyle x\downarrow }$. If every object has at least one normal form, the ARS is callednormalizing.${\displaystyle x\downarrow y}$ orx andy are said to bejoinable if there exists somez with the property that${\displaystyle x\stackrel{\ast }{\to }z\stackrel{\ast }{\leftarrow }y}$. An ARS is said to possess theChurch–Rosser property if${\displaystyle x\stackrel{\ast }{\leftrightarrow }y}$ implies${\displaystyle x\downarrow y}$. An ARS isconfluent if for allw,x, andy inA,${\displaystyle x\stackrel{\ast }{\leftarrow }w\stackrel{\ast }{\to }y}$ implies${\displaystyle x\downarrow y}$. An ARS islocally confluent if and only if for allw,x, andy inA,${\displaystyle x\leftarrow w\to y}$ implies${\displaystyle x\downarrow y}$. An ARS is said to beterminating ornoetherian if there is no infinite chain${\displaystyle x_0\to x_1\to x_2\to \cdots }$. A confluent and terminating ARS is calledconvergent orcanonical.

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

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

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

The notion of a semi-Thue system essentially coincides with thepresentation of a monoid. Since${\displaystyle \stackrel{\ast }{\underset{R}{\leftrightarrow }}}$ is a congruence, we can define thefactor monoid${\displaystyle {\mathcal{M}}_R={\mathrm{\Sigma }}^{\ast }/\stackrel{\ast }{\underset{R}{\leftrightarrow }}}$ of the free monoid${\displaystyle {\mathrm{\Sigma }}^{\ast }}$ by the Thue congruence. If a monoid${\displaystyle \mathcal{M}}$ isisomorphic with${\displaystyle {\mathcal{M}}_R}$, then the semi-Thue system${\displaystyle (\mathrm{\Sigma },R)}$ is called amonoid presentation of${\displaystyle \mathcal{M}}$.

We immediately get some very useful connections with other areas of algebra. For example, the alphabet${\displaystyle \{a,b\}}$ with the rules${\displaystyle \{ab\to \epsilon ,ba\to \epsilon \}}$, where${\displaystyle \epsilon }$ is theempty string, is a presentation of thefree group on one generator. If instead the rules are just${\displaystyle \{ab\to \epsilon \}}$, then we obtain a presentation of thebicyclic monoid. Thus semi-Thue systems constitute a natural framework for solving theword problem for monoids and groups. In fact, every monoid has a presentation of the form${\displaystyle (\mathrm{\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.^[12]

Aterm rewriting system (TRS) is a rewriting system whose objects areterms, which are 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${\displaystyle (\vee )}$ and${\displaystyle (\wedge )}$ and the unary operator${\displaystyle (\mathrm{\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 function can be defined by a term rewriting system.^[13]

Some programming languages are based on term rewriting. One such example is Pure, a functional programming language for mathematical applications.^[14][15]

Arewrite rule is a pair ofterms, commonly written as${\displaystyle l\to r}$, to indicate that the left-hand sidel can be replaced by the right-hand sider. Aterm rewriting system is a setR of such rules. A rule${\displaystyle l\to r}$ can beapplied to a terms if the left termlmatches somesubterm ofs, that is, if there is somesubstitution${\displaystyle \sigma }$ such that the subterm of${\displaystyle s}$ rooted at somepositionp is the result of applying the substitution${\displaystyle \sigma }$ to the terml. The subterm matching the left hand side of the rule is called aredex orreducible expression.^[16] The result termt of this rule application is then the result ofreplacing the subterm at positionp ins by the term${\displaystyle r}$ with the substitution${\displaystyle \sigma }$ applied, see picture 1. In this case,${\displaystyle s}$ is said to berewritten in one step, orrewritten directly, to${\displaystyle t}$ by the system${\displaystyle R}$, formally denoted as${\displaystyle s{\to }_{R}t}$,${\displaystyle s\underset{R}{\to }t}$, or as${\displaystyle s\stackrel{R}{\to }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}{\to }{t}_2\underset{R}{\to }\cdots \underset{R}{\to }{t}_n}$, the term${\displaystyle t_1}$ is said to berewritten to${\displaystyle t_n}$, formally denoted as${\displaystyle t_1\stackrel{+}{\underset{R}{\to }}{t}_n}$. In other words, the relation${\displaystyle \stackrel{+}{\underset{R}{\to }}}$ is thetransitive closure of the relation${\displaystyle \underset{R}{\to }}$; often, also the notation${\displaystyle \stackrel{\ast }{\underset{R}{\to }}}$ is used to denote thereflexive-transitive closure of${\displaystyle \underset{R}{\to }}$, that is,${\displaystyle s\stackrel{\ast }{\underset{R}{\to }}t}$ if${\displaystyle s=t}$ or${\displaystyle s\stackrel{+}{\underset{R}{\to }}t}$.^[17] A term rewriting given by a set${\displaystyle R}$ of rules can be viewed as an abstract rewriting system as definedabove, with terms as its objects and${\displaystyle \underset{R}{\to }}$ as its rewrite relation.

For example,${\displaystyle x\ast (y\ast z)\to (x\ast y)\ast z}$ is a rewrite rule, commonly used to establish a normal form with respect to the associativity of${\displaystyle \ast }$.That rule can be applied at the numerator in the term${\displaystyle \frac{a\ast ((a+1)\ast (a+2))}{1\ast (2\ast 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\ast (a+1))\ast (a+2)}$, and replacing the numerator by that term yields${\displaystyle \frac{(a\ast (a+1))\ast (a+2)}{1\ast (2\ast 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 \ast }$ to${\displaystyle \frac{a\ast ((a+1)\ast (a+2))}{1\ast (2\ast 3)}}$" in elementary algebra. Alternately, the rule could have been applied to the denominator of the original term, yielding${\displaystyle \frac{a\ast ((a+1)\ast (a+2))}{(1\ast 2)\ast 3}}$.

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 alinear left-hand side is undecidable.^[18][19] Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finiteground systems.^[20]

The following term rewrite system is normalizing,^{[note 3]} but not terminating,^{[note 4]} and not confluent:^[21]

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

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

and

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

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

Their union is a non-terminating system, since

This result disproves a conjecture ofDershowitz,^[23] 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}$ arelinear, 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.

SeeRewrite order andPath 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 tolambda terms, allowing higher order functions and bound variables.^[24] Various results about first-order TRSs can be reformulated for HRSs as well.^[25]

Graph rewrite systems are another generalization of term rewrite systems, operating ongraphs instead of (ground-)terms / their correspondingtree representation.

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

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

• Baader, Franz;Nipkow, Tobias (1999).Term rewriting and all that. Cambridge University Press.ISBN 978-0-521-77920-3. 316 pages.
• Marc Bezem,Jan Willem Klop,Roel de Vrijer ("Terese"),Term Rewriting Systems ("TeReSe"), Cambridge University Press, 2003,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.
• Nachum Dershowitz andJean-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,ISBN 0-444-88074-7, pp. 243–320. Thepreprint of this chapter is freely available from the authors, but it is missing the figures.
• Nachum Dershowitz andDavid Plaisted."Rewriting", Chapter 9 inJohn Alan Robinson andAndrei 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 inSamson Abramsky,Dov M. Gabbay andTom 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. Hogger andJohn 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 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,ISBN 0-12-206382-1.

Look uprewriting in Wiktionary, the free dictionary.

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

• Formal languages
• Logic in computer science
• Mathematical logic
• Rewriting systems

• Articles with short description
• Short description is different from Wikidata