Math 2.0

Computer science Definition

Term rewriting for equational theories

Builds on Term algebraSubstitutionIdentityEquational theoryBirkhoff's completeness theorem

Definition

Let σ\sigma be a signature and XX a set of variables. Let T(X)T(X) be the set of terms of σ\sigma over XX, as in the term algebra. A term rewriting system is a set RR of pairs (l,r)(l, r) of terms, written l→rl \to r and called rules. Each rule must satisfy two conditions: ll is not a variable, and every variable of rr occurs in ll. For terms s,ts, t, one writes s→Rts \to_R t if there are a rule l→rl \to r in RR and a substitution τ\tau with the following property. The term ss contains τ(l)\tau(l) as a subterm, and tt is obtained from ss by replacing one occurrence of it by τ(r)\tau(r). Let ↔R∗\leftrightarrow_R^* be the smallest equivalence relation that contains →R\to_R. The system RR presents the equational theory EE if, for all terms s,ts, t, one has s↔R∗ts \leftrightarrow_R^* t if and only if s≈ts \approx t belongs to EE. The system RR is convergent if:

  1. it is terminating: there is no infinite chain t0→Rt1→Rt2→R⋯t_0 \to_R t_1 \to_R t_2 \to_R \cdots;
  2. it is confluent: if t→R∗ut \to_R^* u and t→R∗vt \to_R^* v, then u→R∗wu \to_R^* w and v→R∗wv \to_R^* w for some term ww.

Remarks

By Birkhoff's completeness theorem, a system RR presents the theory axiomatised by the identities {l≈r:(l→r)∈R}\set{l \approx r : (l \to r) \in R}. If RR is convergent, each term tt has a unique normal form nf⁡(t)\operatorname{nf}(t), a term with no further rewrite step. Then s≈ts \approx t is in the theory if and only if nf⁡(s)=nf⁡(t)\operatorname{nf}(s) = \operatorname{nf}(t). For a finite convergent system, this decides the equational theory. Example: R={f(f(x))→x}R = \set{f(f(x)) \to x} is convergent: each step shortens the term, and the only overlap, in f(f(f(x)))f(f(f(x))), rewrites to f(x)f(x) in both ways. So fm(x)≈fn(x)f^m(x) \approx f^n(x) holds in the theory of an involution exactly when mm and nn have the same parity. Non-example: R={x⋅y→y⋅x}R = \set{x \cdot y \to y \cdot x} presents the theory of a commutative operation but is not terminating, since a⋅b→b⋅a→a⋅b→⋯a \cdot b \to b \cdot a \to a \cdot b \to \cdots. The Knuth–Bendix completion procedure tries to turn a set of identities into an equivalent convergent system.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Equational logic concept
  2. Equational theory concept
  3. Identity concept
  4. Substitution concept
  5. Term algebra concept
  6. Birkhoff's completeness theorem statement
  7. Term rewriting for equational theories definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Rewriting, Term rewriting systems
About this page
TagHHNJT9CBEJ
URIm2://HHNJT9CBEJ
Kinddefinition
WritingW0 stub
MSC68Q42, 08B05, 03B35
DefinesTerm rewriting for equational theories
UsesTerm algebra, Substitution, Identity, Equational theory, Birkhoff's completeness theorem
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.