Rewriting#Normal forms, joinability and the word problem

{{Short description|Replacing subterm in a formula with another term}}

In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines,

Joseph Goguen "Proving and Rewriting" International Conference on Algebraic and Logic Programming, 1990 Nancy, France pp 1-24{{cite journal |last1=Sculthorpe |first1=Neil |last2=Frisby |first2=Nicolas |last3=Gill |first3=Andy |title=The Kansas University rewrite engine |journal=Journal of Functional Programming |volume=24 |issue=4 |year=2014 |pages=434–473 |issn=0956-7968 |doi=10.1017/S0956796814000185 |s2cid=16807490 |url=http://irep.ntu.ac.uk/id/eprint/27901/1/PubSub5454_Sculthorpe.pdf |access-date=2019-02-12 |archive-date=2017-09-22 |archive-url=https://web.archive.org/web/20170922234803/http://irep.ntu.ac.uk/id/eprint/27901/1/PubSub5454_Sculthorpe.pdf |url-status=live }} 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{{cite journal|doi=10.1016/0743-1066(92)90047-7|title=The term rewriting approach to automated theorem proving|journal=The Journal of Logic Programming|volume=14|issue=1–2|pages=71–99|year=1992|last1=Hsiang|first1=Jieh|last2=Kirchner|first2=Hélène|last3=Lescanne|first3=Pierre|last4=Rusinowitch|first4=Michaël|doi-access=free}} and declarative programming languages are based on term rewriting.{{cite journal|doi=10.1016/S0743-1066(98)10005-5 |title=Theory and practice of constraint handling rules |journal=The Journal of Logic Programming |volume=37 |issue=1–3 |pages=95–138 |year=1998 |last1=Frühwirth |first1=Thom |doi-access=free }}{{Cite journal | doi=10.1016/S0304-3975(01)00359-0| title=Maude: Specification and programming in rewriting logic| journal=Theoretical Computer Science| volume=285| issue=2| pages=187–243| year=2002| last1=Clavel| first1=M.| last2=Durán| first2=F.| last3=Eker| first3=S.| last4=Lincoln| first4=P.| last5=Martí-Oliet| first5=N.| last6=Meseguer| first6=J.| last7=Quesada| first7=J.F.| doi-access=free}}

Example cases

= Logic =

In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system.{{cite book|author1=Kim Marriott|author2=Peter J. Stuckey|title=Programming with Constraints: An Introduction|url=https://books.google.com/books?id=jBYAleHTldsC&q=%22conjunctive+normal+form%22+%28%22%28rewrite+OR+rewriting%29+%28system+OR+engine%29%22+OR+%22term+rewriting%22%29+-wikipedia&pg=PA436|year=1998|publisher=MIT Press|isbn=978-0-262-13341-8|pages=436–}} For example, the rules 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),$ 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.

For each rule, each variable denotes a subexpression, and the symbol ( $\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 a logical 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.

= 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.{{cite book | author1=Jürgen Avenhaus | author2=Klaus Madlener | contribution=Term Rewriting and Equational Reasoning | pages=1–43 | title=Formal Techniques in Artificial Intelligence | editor=R.B. Banerji | publisher=Elsevier | series=Sourcebook | year=1990 }} Here: Example in sect.4.1, p.24.

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

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

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 =

In linguistics, phrase structure rules, also called rewrite rules, are used in some systems of generative grammar,{{cite book|author=Robert Freidin|title=Foundations of Generative Syntax|url=https://books.google.com/books?id=YPCVQxYmKsgC&q=%22rewrite+rules%22|year=1992|publisher=MIT Press|isbn=978-0-262-06144-5}} 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 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 $\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.

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 systemBook and Otto, p. 10 or abstract rewriting system (abbreviated ARS).Bezem et al., p. 7, An ARS is simply a set A of objects, together with a binary relation → on A called the reduction relation, rewrite relationBezem et al., p. 7 or just reduction.

Many notions and notations can be defined in the general setting of an ARS. $\overset{*}\rightarrow$ is the reflexive transitive closure of $\rightarrow$ . $\leftrightarrow$ is the symmetric closure of $\rightarrow$ . $\overset{*}{\leftrightarrow}$ is the reflexive transitive symmetric closure of $\rightarrow$ . The word problem for an ARS is determining, given x and y, whether $x \overset{*}{\leftrightarrow} y$ . An object x in A is called reducible if there exists some other y in A such that $x \rightarrow y$ ; otherwise it is called irreducible or a normal form. An object y is called a "normal form of x" if $x \stackrel{*}{\rightarrow} y$ , and y is irreducible. If the normal form of x is unique, then this is usually denoted with $x{\downarrow}$ . If every object has at least one normal form, the ARS is called normalizing. $x \downarrow y$ or x and y are said to be joinable if there exists some z with the property that $x \overset{*}{\rightarrow} z \overset{*}{\leftarrow} y$ . An ARS is said to possess the Church–Rosser property if $x \overset{*}{\leftrightarrow} y$ implies $x \downarrow y$ . An ARS is confluent if for all w, x, and y in A, $x \overset{*}{\leftarrow} w \overset{*}{\rightarrow} y$ implies $x \downarrow y$ . An ARS is locally confluent if and only if for all w, x, and y in A, $x \leftarrow w \rightarrow y$ implies $x\mathbin\downarrow y$ . An ARS is said to be terminating or noetherian if there is no infinite chain $x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \cdots$ . A confluent and terminating ARS is called convergent or canonical.

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

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 $(\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 of rewrite rules. The one-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 $u R v$ . 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$ is symmetric, then the system is called a Thue 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 a congruence, meaning it is an equivalence relation (by definition) and it is also compatible with string concatenation. The relation $\overset{*}\underset{R} \leftrightarrow$ is called the Thue congruence generated 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 the presentation of a monoid. Since $\overset{*}{\underset R \leftrightarrow}$ is a congruence, we can define the factor monoid $\mathcal{M}_R = \Sigma^*/\overset{*}{\underset R \leftrightarrow}$ of the free monoid $\Sigma^*$ by the Thue congruence. If a monoid $\mathcal{M}$ is isomorphic with $\mathcal{M}_R$ , then the semi-Thue system $(\Sigma, R)$ is called a monoid presentation of $\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 the empty string, is a presentation of the free group on one generator. If instead the rules are just $\{ ab \rightarrow \varepsilon \}$ , then we obtain a presentation of the bicyclic monoid. Thus semi-Thue systems constitute a natural framework for solving the word problem for 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 the Post–Markov theorem.Martin Davis et al. 1994, p. 178

Term rewriting systems

File:Triangle diagram of rewrite rule application svg.svg

File:Example term for position, path, depth, match svg.svg

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 {{section link||Logic}} above 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 a term algebra. A term can be visualized as a tree of symbols, the set of admitted symbols being fixed by a given signature. As a formalism, term rewriting systems have the full power of Turing machines, that is, every computable function can be defined by a term rewriting system.Dershowitz, Jouannaud (1990), sect.1, p.245

Some programming languages are based on term rewriting. One such example is Pure, a functional programming language for mathematical applications.{{Cite journal |last=Albert |first=Gräf |date=2009 |title=Signal Processing in the Pure Programming Language |url=https://archive.org/details/LAC2009SignalProcessingInThePureProgrammingLanguage_Paper |journal=Linux Audio Conference}}{{Cite web |last=Riepe |first=Von Michael |date=November 18, 2009 |title=Pure – eine einfache funktionale Sprache |url=https://www.heise.de/hintergrund/Rein-ins-Vergnuegen-856225.html |archive-url=https://web.archive.org/web/20110319165239/http://www.heise.de/ix/artikel/Rein-ins-Vergnuegen-856225.html |archive-date=March 19, 2011}}

=Formal definition <span class="anchor" id="Redex"></span>=

A rewrite rule is a pair of terms, commonly written as $l \rightarrow r$ , to indicate that the left-hand side {{math|l}} can be replaced by the right-hand side {{math|r}}. A term rewriting system is a set {{math|R}} of such rules. A rule $l \rightarrow r$ can be applied to a term {{math|s}} if the left term {{math|l}} matches some subterm of {{math|s}}, that is, if there is some substitution $\sigma$ such that the subterm of $s$ rooted at some position {{math|p}} is the result of applying the substitution $\sigma$ to the term {{math|l}}. The subterm matching the left hand side of the rule is called a redex or reducible expression.{{cite web |last1=Klop |first1=J. W. |title=Term Rewriting Systems |url=http://www.cs.tau.ac.il/~nachum/papers/klop.pdf |website=Papers by Nachum Dershowitz and students |publisher=Tel Aviv University |access-date=14 August 2021 |page=12 |archive-date=15 August 2021 |archive-url=https://web.archive.org/web/20210815025906/http://www.cs.tau.ac.il/~nachum/papers/klop.pdf |url-status=live }} The result term {{math|t}} of this rule application is then the result of replacing the subterm at position {{math|p}} in {{math|s}} by the term $r$ with the substitution $\sigma$ applied, 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 \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 be rewritten to $t_n$ , formally denoted as $t_1 \overset{+}\underset{R}\rightarrow t_n$ . In other words, the relation $\overset{+}\underset{R}\rightarrow$ is the transitive closure of the relation $\underset{R}\rightarrow$ ; often, also the notation $\overset{*}\underset{R}\rightarrow$ is used to denote the reflexive-transitive closure of $\underset{R}\rightarrow$ , that is, $s \overset{*}\underset{R}\rightarrow t$ if $s = t$ or {{nobreak| $s \overset{+}\underset{R}\rightarrow t$ .{{cite book| author=N. Dershowitz, J.-P. Jouannaud| title=Rewrite Systems| year=1990| volume=B| pages=243–320| publisher=Elsevier| editor=Jan van Leeuwen| editor-link=Jan van Leeuwen| series=Handbook of Theoretical Computer Science}}; here: Sect. 2.3}} A term rewriting given by a set $R$ of rules can be viewed as an abstract rewriting system as defined above, 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.since applying that substitution to the rule's left hand side $x*(y*z)$ yields the numerator $a*((a+1)*(a+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 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.{{cite book| author=Max Dauchet| chapter=Simulation of Turing Machines by a Left-Linear Rewrite Rule| title=Proc. 3rd Int. Conf. on Rewriting Techniques and Applications| year=1989|volume=355| pages=109–120| publisher=Springer|series=LNCS}}{{cite journal | author=Max Dauchet | title=Simulation of Turing machines by a regular rewrite rule | journal=Theoretical Computer Science | volume=103 | number=2 | pages=409–420 | date=Sep 1992 | doi=10.1016/0304-3975(92)90022-8 | doi-access=free }} Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems.{{cite tech report| author=Gerard Huet, D.S. Lankford| title=On the Uniform Halting Problem for Term Rewriting Systems|date=Mar 1978| number=283| pages=8| institution=IRIA| url=https://www.ens-lyon.fr/LIP/REWRITING/TERMINATION/Huet_Lankford.pdf| access-date=16 June 2013}}

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)) → ... → 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:{{cite book| author=Bernhard Gramlich| chapter=Relating Innermost, Weak, Uniform, and Modular Termination of Term Rewriting Systems| title=Proc. International Conference on Logic Programming and Automated Reasoning (LPAR)| date=Jun 1993| volume=624| pages=285–296| publisher=Springer| editor=Voronkov, Andrei| series=LNAI| chapter-url=http://www.logic.at/staff/gramlich/papers/lpar92.ps.gz| title-link=International Conference on Logic Programming and Automated Reasoning| access-date=2014-06-19| archive-date=2016-03-04| archive-url=https://web.archive.org/web/20160304185714/http://www.logic.at/staff/gramlich/papers/lpar92.ps.gz| url-status=live}} Here: Example 3.3

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

The following two examples of terminating term rewrite systems are due to Toyama:{{cite journal| author=Yoshihito Toyama| title=Counterexamples to Termination for the Direct Sum of Term Rewriting Systems| journal=Inf. Process. Lett.| year=1987| volume=25| issue=3| pages=141–143| url=http://www.nue.ie.niigata-u.ac.jp/toyama/user/toyama/research/paper/journal/counterexamples.pdf| doi=10.1016/0020-0190(87)90122-0| hdl=2433/99946| hdl-access=free| access-date=2019-11-13| archive-date=2019-11-13| archive-url=https://web.archive.org/web/20191113091157/http://www.nue.ie.niigata-u.ac.jp/toyama/user/toyama/research/paper/journal/counterexamples.pdf| url-status=live}}

: $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{align}
& 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{align}$

This result disproves a conjecture of Dershowitz,{{cite book| author=N. Dershowitz| chapter=Termination| title=Proc. RTA| year=1985| volume=220| pages=180–224| publisher=Springer| editor=Jean-Pierre Jouannaud| editor-link=Jean-Pierre Jouannaud| series=LNCS| chapter-url=http://www.cs.tau.ac.il/~nachum/papers/LNCS/Termination.pdf| access-date=2013-06-16| archive-date=2013-11-12| archive-url=https://web.archive.org/web/20131112200935/http://www.cs.tau.ac.il/~nachum/papers/LNCS/Termination.pdf| url-status=live}}; 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.

= Higher-order 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.{{cite book |first1=D. A. |last1=Wolfram |title=The Clausal Theory of Types |date=1993 |publisher=Cambridge University Press |pages=47–50 |doi=10.1017/CBO9780511569906|isbn=9780521395380 |s2cid=42331173 }} Various results about first-order TRSs can be reformulated for HRSs as well.{{cite book |last1=Nipkow |first1=Tobias |last2=Prehofer |first2=Christian |editor1-last=Bibel |editor1-first=W. |editor2-last=Schmitt |editor2-first=P. |title=Automated Deduction - A Basis for Applications. Volume I: Foundations |date=1998 |publisher=Kluwer |pages=399–430 |chapter=Higher-Order Rewriting and Equational Reasoning |chapter-url=https://www21.in.tum.de/~nipkow/pubs/ded-book.html |access-date=2021-08-16 |archive-date=2021-08-16 |archive-url=https://web.archive.org/web/20210816153129/https://www21.in.tum.de/~nipkow/pubs/ded-book.html |url-status=live }}

= Graph rewriting systems =

Graph rewrite systems are another generalization of term 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.

Notes

External links

The [http://rewriting.loria.fr/ Rewriting Home Page]
[https://ifip-wg-rewriting.cs.ru.nl/ IFIP Working Group 1.6]
[http://cl-informatik.uibk.ac.at/~ami/research/rr/index.php Researchers in rewriting] by Aart Middeldorp, University of Innsbruck
[https://www.termination-portal.org/ Termination Portal]
[https://maude.cs.illinois.edu/w/index.php/The_Maude_System Maude System] — a software implementation of a generic term rewriting system.