# Rewriting system

## Contents

## Definition

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.

## Terminology

### Reduction

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 .

### 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:

Category:Properties of rewriting systems

## =Constructs

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

### Quotient

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.