Rewriting system

Builds on Binary relation Transitive closure Equivalence relation

Definition

An abstract rewriting system is a pair $(A, \to)$ of a set $A$ and a binary relation $\to$ on $A$ , called the rewrite relation or reduction. For $a, b \in A$ :

$a \to^* b$ means that $b$ is reachable from $a$ in zero or more steps; $\to^*$ is the reflexive and transitive closure of $\to$ ;
$a \leftrightarrow^* b$ means that $a$ and $b$ are related by the smallest equivalence relation containing $\to$ ;
$a$ is a normal form if there is no $c \in A$ with $a \to c$ . Then $b$ is a normal form of $a$ if $a \to^* b$ and $b$ is a normal form.

The system is terminating, or strongly normalizing, if there is no infinite chain $a_0 \to a_1 \to a_2 \to \cdots$ .

Remarks

Example: $A = \set{a, b}^*$ with $u \to v$ when $v$ arises from $u$ by replacing one occurrence of $ba$ by $ab$ . It is terminating, since each step lowers the number of pairs of positions $i < j$ with a $b$ at $i$ and an $a$ at $j$ . The normal forms are the words $a^m b^n$ . Non-example of termination: $A = \set{x, y}$ with $x \to y$ and $y \to x$ , which has the infinite chain $x \to y \to x \to \cdots$ and no normal form. A string rewriting system over an alphabet $\Sigma$ is a set of pairs of words $l \to r$ , inducing $u l v \to u r v$ on $\Sigma^*$ ; a term rewriting system rewrites terms in the same way.

Reading path

To understand this page from the ground up, read these 4 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

Tag	`82N5ZEWENZ`
URI	`m2://82N5ZEWENZ`
Kind	definition
Writing	W0 stub
MSC	68Q42, 03D03
Defines	Rewriting system
Uses	Binary relation, Transitive closure, Equivalence relation
Changed	3 November 2026

Rewriting system

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here