The aim of this chapter is very briefly to give some historical background and some basic definitions needed to make the rest of this manual intelligible to the non-specialist. A detailed introduction to the theory of small overlap conditions is well beyond the scope of this manual, but we provide some references which can be followed up by the reader seeking a more detailed understanding.
Small overlap conditions are a natural semigroup- and monoid-theoretic analogue of the small cancellation conditions studied in combinatorial group theory. They were introduced and extensively studied in the thesis of Remmers [Rem71]; he developed a geometric theory of small overlap semigroups and monoids (see also [Rem80]) based on a semigroup-theoretic analogue of the van Kampen diagrams employed by group theorists [LS77].
Remmers showed that if a presentation satisfies the condition C(3) then the ratio of the lengths of equivalent words is bounded by a constant dependent only on the presentation. In particular, equivalence classes for such presentations are finite, which immediately gives a theoretical decision algorithm for the word problem by exhaustive enumeration. An accessible exposition of some of Remmers' results can be found in the book of Higgins [Hig92].
For practical purposes, exhaustive enumeration of equivalence classes is not a feasible approach to the word problem, since these classes can be exponential in the size of their elements, and it is not clear from Remmers' work whether there is a more tractable solution. However, recent research of Kambites [Kam07] has yielded a highly practical (linear time) algorithm for the word problem of any presentation satisfying the slightly stronger condition C(4). An implementation of this algorithm forms the core of the SmallOverlap package.
We assume the reader to be familiar with finitely presented monoids and semigroups. Suppose we have a fixed monoid or semigroup presentation. A relation word is a word over the generators which forms one side of a relation in the presentation. A piece of the presentation is a word which occurs as a factor of two different relation words, or as a factor of one relation word in two different places. (We make the convention that the empty word is always a piece; this is necessary to facilitate a uniform treatment of the free monoid as a small overlap monoid.)
Let n be a positive integer. The presentation is said to satisfy C(n) if no relation word can be written as a product of strictly fewer than n pieces. The small overlap class of the presentation is the smallest positive integer n such that the presentation satisfies C(n), or infinity if the presentation satisfies C(n) for all n, or 0 if the presentation does not satisfy C(n) for any n.
Now let R be a relation word. If the presentation satisfies the condition C(1) then there is a unique relation word T such that R = T or T = R is a relation in the presentation. T is called the complement relation word of R.
The maximal piece prefix of the relation word R is the (possibly empty) longest prefix of R which is a piece. Similarly, the maximal piece suffix of R is the longest suffix of R which is a piece. If the presentation satisfies C(3) then the maximal piece prefix and maximal piece suffix clearly cannot meet, so r admits a factorisation
r = XYZ
where X is the maximal piece prefix, Z is the maximal piece suffix, and Y is a non-empty word, called the middle word of R. If moreover the presentation satisfies the stronger condition C(4), then the middle word Y is not a piece.
generated by GAPDoc2HTML