A rewriting system is the following data:
- A set called the set of generators or the alphabet (its elements are the letters). The set of words (sequences of finite length) is termed .
- A subset of . 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 , and the set of relations is simply that obtained by declaring that for any pair .
Also refer rewriting system for a group.
Given a rewriting system , a reduction for this rewriting system, is a pair such that there exist such that , and .
A reduction is said to be the identity reduction if .
Note that just saying does not mean that the reduction is the identity reduction.
The pair is termed the rewrite rule associated with the reduction.
A reduction is typically denoted as . We often write reductions in sequence. For instance, if is a reduction and is a reduction, then we write:
We may even branch out multiple reductions. For instance, if and are reductions, then we can depict this by a diagram with an arrow from to and an arrow from to .
An irreducible word is a word such that the only reduction from it (if any) is the identity reduction.
Properties of rewriting systems
For a full list of properties of rewriting systems, refer:
Free product of monoids
Given a free product of monoids, a rewriting system for the free product can be obtained by simply taking the union of the corresponding generating sets and rewrites, after first disjointifying the alphabets.
Direct product of monoids
Given a direct product of monoids, a rewriting system for the direct product can be obtained as follows:
- First take the rewriting system for the product
- Now introduce a total ordering among the direct factors
- Now introduce rewrites of the form whenever and are letters in the direct factors such that the factor in which lies, come after the factor in which lies.
In other words, these relations help us bubble all the letters of the first factor to the left, the letters of the second factor after that, the letters of the third factor after that, and so on.
A rewriting system for the quotient of a monoid by some congruence can be described if we have a collection of relations generating the congruence. In that case, we simply direct each relation in any way we want and get a collection of rewrites.