Rewriting system

Definition

A rewriting system $(\mathrm{\Sigma },R)$ is the following data:

• A set $\mathrm{\Sigma }$ called the set of generators or the alphabet (its elements are the letters). The set of words (sequences of finite length) is termed ${\mathrm{\Sigma }}^{*}$.
• A subset $R$ of ${\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$. Each element of this subset is termed a rewrite

Every rewriting system gives a presentation of a monoid as follows: the generating set is simply $\mathrm{\Sigma }$, and the set of relations is simply that obtained by declaring that $u=v$ for any pair $(u,v)\in R$.

Terminology

Reduction

Given a rewriting system $(\mathrm{\Sigma },R)$, a reduction for this rewriting system, is a pair $(u,v)\in {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$ such that there exist $a,l,b,r\in {\mathrm{\Sigma }}^{*}$ such that $(l,r)\in R$, $u=alb$ and $v=arb$.

A reduction is said to be the identity reduction if $l=r$.

Note that just saying $u=v$ does not mean that the reduction is the identity reduction.

The pair $(l,r)$ is termed the rewrite rule associated with the reduction.

A reduction $(u,v)$ is typically denoted as $u\to v$. We often write reductions in sequence. For instance, if $(u,v)$ is a reduction and $(v,w)$ is a reduction, then we write:

$u\to v\to w$

We may even branch out multiple reductions. For instance, if $(u,v_1)$ and $(u,v_2)$ are reductions, then we can depict this by a diagram with an arrow from $u$ to $v_1$ and an arrow from $u$ to $v_2$.

Irreducible word

An irreducible word is a word such that the only reduction from it (if any) is the identity reduction.

Facts

Properties of rewriting systems

For a full list of properties of rewriting systems, refer: