Editing Rewriting (section)

===Formal definition <span class="anchor" id="Redex"></span>===
{{Redirect|Redex|the medication|Tadalafil}}
A ''rewrite rule'' is a pair of [[Term (logic)|terms]], commonly written as <math>l \rightarrow r</math>, 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 <math>l \rightarrow r</math> can be ''applied'' to a term {{math|''s''}} if the left term {{math|l}} [[Term (logic)#Operations with terms|matches]] some [[Term (logic)#Operations with terms|subterm]] of {{math|''s''}}, that is, if there is some [[substitution (logic)|substitution]] <math>\sigma</math> such that the subterm of <math>s</math> rooted at some [[Term (logic)#Operations with terms|position]] {{math|''p''}} is the result of applying the substitution <math>\sigma</math> to the term {{math|l}}. The subterm matching the left hand side of the rule is called a '''redex''' or '''reducible expression'''.<ref name=Klop>{{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 }}</ref> The result term {{math|''t''}} of this rule application is then the result of [[Term (logic)#Operations with terms|replacing the subterm]] at position {{math|''p''}} in {{math|''s''}} by the term  <math>r</math> with the substitution <math>\sigma</math> applied, see picture 1. In this case, <math>s</math> is said to be ''rewritten in one step'', or ''rewritten directly'', to <math>t</math> by the system <math>R</math>, formally denoted as <math>s \rightarrow_R t</math>, <math> s \underset{R}\rightarrow t</math>, or as <math>s \overset{R}\rightarrow t</math> by some authors.

If a term <math>t_1</math> can be rewritten in several steps into a term <math>t_n</math>, that is, if <math>t_1 \underset{R}\rightarrow t_2 \underset{R}\rightarrow \cdots \underset{R}\rightarrow t_n</math>, the term <math>t_1</math> is said to be ''rewritten'' to <math>t_n</math>, formally denoted as <math>t_1 \overset{+}\underset{R}\rightarrow t_n</math>. In other words, the relation <math>\overset{+}\underset{R}\rightarrow</math> is the [[transitive closure]] of the relation <math>\underset{R}\rightarrow</math>; often, also the notation <math>\overset{*}\underset{R}\rightarrow</math> is used to denote the [[Closure (mathematics)#Binary relation closures|reflexive-transitive closure]] of <math>\underset{R}\rightarrow</math>, that is, <math>s \overset{*}\underset{R}\rightarrow t</math> if <math>s = t</math> or {{nobreak|<math>s \overset{+}\underset{R}\rightarrow t</math>.<ref>{{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.&nbsp;2.3</ref>}} A term rewriting given by a set <math>R</math> of rules can be viewed as an abstract rewriting system as defined [[#Abstract rewriting systems|above]], with terms as its objects and <math>\underset{R}\rightarrow</math> as its rewrite relation.

For example, <math>x*(y*z) \rightarrow (x*y)*z</math> is a rewrite rule, commonly used to establish a normal form with respect to the associativity of <math>*</math>.
That rule can be applied at the numerator in the term <math>\frac{a*((a+1)*(a+2))}{1*(2*3)}</math> with the matching substitution <math>\{ x \mapsto a, \; y \mapsto a+1, \; z \mapsto a+2 \}</math>, see picture 2.<ref group="note">since applying that substitution to the rule's left hand side <math>x*(y*z)</math> yields the numerator <math>a*((a+1)*(a+2))</math></ref> Applying that substitution to the rule's right-hand side yields the term <math>(a*(a+1))*(a+2)</math>, and replacing the numerator by that term yields <math>\frac{(a*(a+1))*(a+2)}{1*(2*3)}</math>, 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 <math>*</math> to <math>\frac{a*((a+1)*(a+2))}{1*(2*3)}</math>" in elementary algebra. Alternately, the rule could have been applied to the denominator of the original term, yielding <math>\frac{a*((a+1)*(a+2))}{(1*2)*3}</math>.