Rewriting system for a group

This article is about a standard (though not very rudimentary) definition in an area related to, but not strictly part of, group theory

Definition

Symbol-free definition

A rewriting system for a group is the following data:

• A set of elements in the group that generate the group (that is, a generating set of the group)
• A set of ordered pairs of words in those elements. These ordered pairs are termed rewrite rules with the property that two words (in the generators and their inverses) are equal if we can reduce both of them to the same word by applying the rewrite rule

Here applying a rewrite rule means replacing a subword of the word that corresponds to the left side of the rewrite rule, by a subword that corresponds to the right side

Note that a rewriting system defines a presentation of the group, where the relations are given by the quotient of the pairs of terms in each rewrite rule. However, a rewriting system has much more structure than a presentation in the sense that there is an explicit direction of replacement from one word to the other.

(Note that in addition to the rewrites explicitly specified, we can use the free group rewrites which replaces the product of any generator and its inverse by the identity element).

Definition with symbols

A rewriting system for a group $G$ is the data $(\Sigma ,R)$ along with the following:

• Let $\Pi =\Sigma \cup \Sigma ^{-1}$ where $\Sigma ^{-1}$ is a copy of $\Sigma$ with each letter replaced by a formal inverse. Then, a monoid homomorphism $h:\Pi \to G$ s uch that $h(a^{-1})=h(a)^{-1}$ for every letter $a\in \Sigma$ In other words, there is a mapping from $\Sigma$ to a group-theoretic generating set for $G$.

• A subset $R\in \Pi \times \Pi$ such that the relations $u=v$ give a presentation for $G$.

Definition in terms of rewriting system

A rewriting system for a group can be viewed as a rewriting system for it as a monoid if we replace the alphabet by the union of its letter and the letters for the inverses, and add the reductions $xx^{-1}\to e$ for every letter $x$ in the bigger alphabet. Here $e$ is the empty word, for the identity element.

Properties

Confluence and normal forms

Further information: Confluent rewriting system

A rewriting system is said to be confluent if whenever $u$ reduces (via sequences of rewrites) to both $v$ and $v'$, there exists a $u'$ to which both $v$ and $v'$ reduce.

If a rewriting system is both confluent and finitely terminating, then it has a normal form. In other words, for every element of the group, there is a unique word representing it with the property that:

• No rewrite can be applied to it
• Given any word for the same element, we can reduce that word via a sequence of rewrites to this word

A group which possesses a confluent rewriting system is termed a confluent group. Clearly confluent groups have a solvable word problem.