Rewriting system

Definition

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

• A set $\Sigma$ called the set of generators or the alphabet (its elements are the letters). The set of words (sequences of finite length) is termed $\Sigma ^{*}$.
• A subset $R$ of $\Sigma ^{*}\times \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 $\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 $(\Sigma ,R)$, a reduction for this rewriting system, is a pair $(u,v)\in \Sigma ^{*}\times \Sigma ^{*}$ such that there exist $a,l,b,r\in \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: