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$.

Facts

Properties of rewriting systems

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