In this chapter we shall discuss techniques for describing and manipulating finitely generated subgroups of a group F which is the free product of a finite number of cyclic groups. An important special case occurs when F is a free group, that is, when all of the cyclic free factors of F are infinite. Many questions about finitely generated subgroups of F can be answered with standard methods of automata theory. However, there is another approach called coset enumeration, which is normally more efficient. Coset enumeration is the next in our collection of major group-theoretic procedures. Only an introduction to coset enumeration is presented in this chapter. It is considered in more detail in Chapter 5.

One of the reasons that we can give a nice treatment of finitely generated subgroups of a free product of cyclic groups is that free products of cyclic groups make up a class of groups which have confluent rewriting systems of a particularly simple form. These rewriting systems are discussed in the first section.

Niladic rewriting systems

Let (X, R) be a monoid presentation. We shall say that R is niladic if every element of R has the form (L, ε), where |L| ≥ 2. The condition on the length of L is purely technical. If (x, ε) is in R for some x in X, then using a Tietze transformation we can delete x from X and from each element of R and obtain another presentation for the same monoid.