Next: 3. Relating the Word Up: Relating Rewriting Techniques on Previous: 1. Introduction

# 2. Presentations: Congruences in Monoids and Groups

The book of Lallement [La79] gives a good introduction to congruences and presentations of monoids, while the book of Johnson [Jo76] was used as a source on group presentations.

Let A be a set and a binary relation on A. By we denote the special relation . A binary relation is called an equivalence relation in case it is reflexive (i.e.  ), symmetric (i.e.  ) and transitive (i.e.  ). In the following we assume that is an equivalence relation. For an element we call the set the class of a modulo . Then A is a disjoint union of classes modulo and the set of all such classes modulo is called the quotient of A modulo , denoted by .

A congruence on a monoid is defined as an equivalence relation on the set which is stable under left and right multiplication with elements of . In particular a right (respectively left) congruence on is stable with respect to right (respectively left) multiplication.

Given a congruence on a monoid and an element , we call the congruence class of m. We can define a monoid structure on the set of all congruence classes by setting for . Then is called the quotient of by and the homomorphism induced by is in fact surjective.

Congruences now provide the means to construct presentations of monoids. A set of symbols is called a set of generators for under the mapping , if the extension of to the set of words on defined by , is a homomorphism from onto . If for two words we have we say that satisfies the relation w = w'. The word problem for a monoid now is to decide whether for two words , satisfies the relation w = w'.

Given a set of relations R we say that a word u is directly derivable from an other word v under the relation , if either u = xly and v = xry or u = xry and v = xly for words x,y. We call u derivable from v under R if there exist words such that v= v0, vi+1 is directly derivable from vi for and vn = u. Notice that if u is derivable from v under R, then holds, i.e. u=v is a relation in . We then call the relation a consequence of the relations R. In case all and only relations on are consequences of the relations R we say that is a presentation of defined by . is also called a Thue system in the literature.

Now the easiest way to give a presentation of a monoid is to take the set itself as a generating set and to use the multiplication table of as the defining relations. However this presentation in general will not be finite and other presentations fulfilling additional conditions, e.g. finitely many generators of finitely many relations, are hoped for.

In order to construct a presentation of a monoid one has to

1.
Find a set of generators for . Then can be chosen as the natural inclusion mapping.
2.
Find a set of relations R in such that the smallest congruence containing these relations coincides with the kernel congruence of the extended homomorphism . This kernel congruence is .
In order to use reduction techniques for computations in monoids or groups, presentations are provided with an orientation of the relations and treated as string rewriting systems (for a general reference of the terms and techniques described here see [BoOt93]). For a finite alphabet , again will denote the set of all words over the alphabet where presents the   empty word, i.e., the word of length zero. will denote the identity on . A string rewriting system or semi-Thue system is a pair where T is a subset of . The elements (l,r) of T are called rules and will often be written as . The (single-step) reduction relation on induced by a set of rules T is defined as follows: For any u,v in , if and only if there exist x,y in and (l,r) in T such that and . v is then called a proper descendant of u. The reflexive transitive symmetric closure is denoted by and is called the Thue congruence. If holds then one says that u reduces to v. In case for u there exists no v such that holds, i.e. at least one reduction step must take place, u is called irreducible. An irreducible descendant of u is called a (T-)normal form and is sometimes denoted by . The reduction relation induced by T is called Noetherian if and only if there is no infinite chain . It is called confluent if for all u,v,w in , and imply the existence of z in such that and . A string rewriting system is called convergent or complete if it is both, Noetherian and confluent, i.e., unique normal forms exist.

By Newman's lemma we know that under the hypothesis that a reduction relation is Noetherian, a string rewriting system is confluent if and only if it is locally confluent, i.e., for all u,v,w in , and imply the existence of z in such that and . For finite string rewriting systems the global property of being locally confluent can be localized to enable a finite confluence test. Remember that presentations of monoids can be treated as string rewriting systems and notice that string rewriting systems are in fact presentations of monoids. Hence, in case they are finite, convergent and effective, we can compute'' in the monoid using the irreducible elements as representatives for the monoid elements. The process of trying to turn a Noetherian string rewriting system into a convergent one by resolving the not locally confluent situations is called completion. We will now sketch how a finite string rewriting system presenting a monoid can be completed in case we have a total admissible2 well-founded3 ordering on such that for all we have . This ordering then will be called a completion ordering for T and the completion process transforms into a (not necessarily finite) convergent string rewriting system presenting the same monoid. It is important that in order to check a finite Noetherian string rewriting system T for confluence we only have to look at a finite set of critical situations: for two not necessarily different rules (l1,r1),(l2,r2) in T the set of critical pairs is defined as . Now given a finite string rewriting system with a completion ordering we can specify a completion process as follows:

Procedure: KNUTH BENDIX COMPLETION

height 0.5pt <
height 0.5pt tex2html_comment_mark>

Given: 		 A string rewriting system

,
and a total well-founded admissible ordering .
[2ex]

;

;
while

do

;
% Remove an element using a fair strategy
for all  critical pairs

do
%

=

%

;

;
% normal.form(z,

Since the word problem for arbitrary string rewriting systems is undecidable,
this procedure
in general will not terminate.
Nevertheless, using a fair4
strategy to remove elements from the set B, it
always enumerates a convergent string rewriting system based on the completion
ordering
presenting the same
monoid as the input system.

Next: 3. Relating the Word
Up: Relating Rewriting Techniques on
Previous: 1. Introduction

|  ZCA Home  |
Reports  |