Term rewriting for equational theories
Builds on Term algebraSubstitutionIdentityEquational theoryBirkhoff's completeness theorem
Definition
Let be a signature and a set of variables. Let be the set of terms of over , as in the term algebra. A term rewriting system is a set of pairs of terms, written and called rules. Each rule must satisfy two conditions: is not a variable, and every variable of occurs in . For terms , one writes if there are a rule in and a substitution with the following property. The term contains as a subterm, and is obtained from by replacing one occurrence of it by . Let be the smallest equivalence relation that contains . The system presents the equational theory if, for all terms , one has if and only if belongs to . The system is convergent if:
- it is terminating: there is no infinite chain ;
- it is confluent: if and , then and for some term .
Remarks
By Birkhoff's completeness theorem, a system presents the theory axiomatised by the identities . If is convergent, each term has a unique normal form , a term with no further rewrite step. Then is in the theory if and only if . For a finite convergent system, this decides the equational theory. Example: is convergent: each step shortens the term, and the only overlap, in , rewrites to in both ways. So holds in the theory of an involution exactly when and have the same parity. Non-example: presents the theory of a commutative operation but is not terminating, since . 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
- no evidence level
- Equational logic concept
- Equational theory concept
- Identity concept
- Substitution concept
- Term algebra concept
- Birkhoff's completeness theorem statement
- Term rewriting for equational theories definition
Further reading
- Web https://en.wikipedia.org/wiki/Rewriting, Term rewriting systems
About this page
| Tag | HHNJT9CBEJ |
|---|---|
| URI | m2://HHNJT9CBEJ |
| Kind | definition |
| Writing | W0 stub |
| MSC | 68Q42, 08B05, 03B35 |
| Defines | Term rewriting for equational theories |
| Uses | Term algebra, Substitution, Identity, Equational theory, Birkhoff's completeness theorem |
| Changed | 2 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.