J. Symbolic Computation (1998) 11, 1–000

Computing automatic coset systems and subgroup presentations

DEREK F. HOLT AND DARREN F. HURT

Mathematics Institute, University of Warwick, Coventry CV4 7AL, U.K.

(Received 23 April 1998)

The concept of an automatic group can be generalized to a group that is automatic with respect to a specified subgroup. This means that there is a finite state automaton that recognizes a unique word in each coset of the subgroup, and others that essentially recognize the permutation action on these cosets induced by multiplying by a group generator. These automata make it possible to enumerate coset representatives as words in the generators, and to solve the generalized word problem for the subgroup efficiently. Algorithms to construct these automata have been described previously by Redfern. Here we describe improved versions, together with implementation details and some examples of successful calculations. A related algorithm to compute a finite presentation of the subgroup is also described.

1. Introduction

The concept of an automatic coset system was introduced by Ian Redfern in his PhD Thesis (Redfern, 1993). Such a system consists of a group G with finite monoid generating set A, a subgroup H, and finite state automata W (the coset word acceptor) and M_{x} (the coset multipliers), where there is one M_{x} for each x ∈ A, and one for x = ε (which denotes the empty word or string). The alphabet of W is A, and that of the M_{x} is A^{†} × A^{†}, where A^{†} = A ∪ {$}, and $ is used to pad the shorter of the two words being read, to make them of equal length. Let A^{∗} denote the set of words in A and, for each w ∈ A^{∗}, let \overline{w} be its image in G. The defining properties of an automatic coset system are that, for each right coset Hg of H in G, W accepts at least one word w with \overline{w} ∈ Hg, and each M_{x} accepts a pair of words (w_{1}, w_{2}) ∈ A^{∗} × A^{∗} if and only if w_{1} and w_{2} are both accepted by W, and H\overline{w_{1}x} = H\overline{w_{2}}. In particular, if H = 1, then we get the usual definition of an automatic structure for G.

If such an automatic coset system exists, then we say that G is coset automatic with respect to the subgroup H. Redfern shows in his thesis that this property is independent of the generating set A. (The proof is a straightforward adaptation of that for automatic groups (the case H = 1), given in Section 2.4 of Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992.) One reason that automatic coset systems might be useful in practice is that they can be used to solve the generalized word problem for H in G (that is, to decide whether an arbitrary word w in the generators of G lies in H) in time quadratic in the length of w. Again the proof carries over essentially without change from the

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1998 Academic Press Limited

corresponding result for H = 1, which is of course just the word problem for G. This is Theorem 2.3.10 of (Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992).

Apart from these theorems, very few theoretical results have been proved about coset automatic groups. This is in sharp distinction to the situation for automatic groups, for which a substantial and continually growing theory has been developed. Since G is always coset automatic with respect to itself, we cannot say anything about G in full generality, but one might hope to prove results about the quotient group of G modulo the core of H in G (that is, the largest normal subsgroup of G that is contained in H). Is it true that this quotient is necessarily finitely presented, for example?

A shortlex automatic coset system is one in which W accepts precisely one word w for each coset Hg, and this is the least word w in a shortlex ordering of A^{∗} such that \overline{w} ∈ Hg. (In a shortlex ordering, w < x if either w is shorter than x, or w and x have equal lengths and w precedes x in the lexicographical ordering of A^{∗} induced by a specified total ordering of A.) The property of being shortlex coset automatic can depend on the choice of A and on the specified ordering of A; indeed this is the case even when H = 1 (see Section 3.5 of Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992 for an example).

The bulk of Redfern’s thesis is devoted to a description of an algorithm for calculating shortlex automatic coset systems, and to some applications of an implementation of this algorithm (by Redfern himself) to drawing the limit sets of Kleinian groups. (This application is also described in McShane, Parker and Redfern 1994.) He assumes that G is a finitely presented group and that H is a finitely generated subgroup, and the algorithm takes a finite presentation of G together with generators of H as words in the generators of G as input. In principle, it should succeed eventually, subject to these assumptions, whenever G is coset automatic with respect to H. A serious weakness of his algorithm, however, is that he is unable to prove formally that the coset systems he computes are correct.

In this paper, we describe an alternative algorithm, in which we can prove correctness, and with the extra feature that we can compute a finite presentation of H whenever the main algorithm succeeds. It is not so general as Redfern’s, in that it requires extra assumptions (to be discussed later) for it to succeed. On the other hand, it can be proved that it always succeeds in the important case of quasiconvex subgroups of wordhyperbolic groups (see, for example, Gersten and Short, 1994), and we have not found any specific examples in which Redfern’s algorithm succeeds but ours does not. Furthermore, it seems to be considerably faster than Redfern’s in the examples used for the applications to Kleinian groups.

The theory of this algorithm is also described in Chapter 3 of the PhD Thesis of the second author (Hurt, 1996). It has been implemented by the first author as part of his package KBMAG for the Knuth-Bendix algorithm on monoids, and the calculation of automatic structures. This is freely available by anonymous ftp; please e-mail the first author for details.

We shall assume for the remainder of the paper that G is a group defined by a finite monoid presentation on a fixed finite ordered monoid generating set A, with relator set R. We assume also that A is closed under inversion; that is, for each x ∈ A, there is an x′ ∈ A such that xx′ and x′x are in R. Then the words in A^{∗} are totally ordered by the shortlex ordering with respect to the specified ordering of A, and whenever we write u < v, etc., for u, v ∈ A^{∗}, we shall be using this ordering. The image of a word u in G is denoted by ū. A word u is called irreducible if it is the least word that maps onto ū. We assume further that a finite generating set Y of a subgroup H of G is given, where the elements of Y are words in A^{∗}. We shall say that a word u ∈ A^{∗} is H-irreducible if it is the least word of which the image in G lies in the right coset Hū. We denote the identity element of G by 1 and the empty word in A^{∗} by ε.

For the general theory of automatic groups, the reader should consult (Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992). The algorithms for shortlex automatic groups, of which the methods to be presented in this paper are generalizations, are described in (Epstein, Holt, Rees, 1991) and (Holt, 1996). Our notation, and the basic structure of the algorithm descriptions will follow those in (Holt, 1996) fairly closely. We shall assume that the reader has some familiarity with automatic groups and their associated machinery, such as finite state automata, and the use of the padding symbol $ in two-variable automata. As in the earlier papers, if u and v are words in A^{∗}, then we use (u, v)^{†} to denote the pair of words in which the shorter of u and v (if any) has had the padding symbol appended to its end to make the two words have equal length. Then (u, v)^{†} can be regarded as a word in A^{†} × A^{†}, which is the input language of the multiplier automata. In general, a finite state automaton with input alphabet A^{†} × A^{†} will be referred to as a two-variable automaton over A. We shall call it a padded automaton if it accepts only words of the form (u, v)^{†} for u, v ∈ A^{∗}. When considering images in G, $ will always map onto the identity element, 1.

If u, v ∈ A^{∗}, then we shall use u =_{G} v to mean that u and v are equal as elements of G (i.e. ū = v̄), whereas u = v will mean that u and v are equal as words. Similarly, we shall use Hu =_{G} Hv for the coset equality Hū = Hv̄. We denote the length of u ∈ A^{∗} by l(u) and, for t ≥ 0, we define u(t) to be the prefix of u of length t for t ≤ l(u), and u(t) = u for t ≥ l(u). The length l(g) of an element g ∈ G is defined to be the length of the shortest word u ∈ A^{∗} with ū = g.

We need to extend the notion of the word-differences associated with an equation in G, introduced in (Epstein, Holt, Rees, 1991) and (Holt, 1996), to a coset equation. Suppose that u and v are words in A^{∗} satisfying u =_{G} hv for some h ∈ H. We define the set of word-differences associated with this equation to be the set of elements \overline{u(t)}^{−1}h\overline{v(t)} of G, for all t ≥ 0. (Since u(t) and v(t) are ultimately constant, this set is finite.) In particular, the element h ∈ H lies in the word-difference set. The set of word-differences associated with a set of such equations is the union of the sets associated with the individual equations.

The principal extra assumption on which our algorithms depend is the following. There is a global positive constant K (depending only on the fixed input data G, A, and Y), such that whenever u, v ∈ A^{∗} are H-irreducible, x ∈ A, and ux =_{G} hv for some h ∈ H, then the word-differences associated with this equation have length at most K. (Equivalently, there is a finite set D of elements of G, such that all word-differences of all coset equations of this type lie in D.) We shall refer to this condition as the coset fellow traveller property, and we shall prove in the next section that it implies that G is coset automatic with respect to H.

In practice, our programs will not work unless G itself is shortlex automatic. This is not such a big restriction as it may sound, since it is probable that most or all interesting examples have this property anyway. It is proved by Redfern in Chapter 10 of (Redfern, 1993) that both of these assumptions hold for quasiconvex subgroups of word-hyperbolic groups, and in practice they hold for many other examples. The programs can verify the correctness of any automatic coset system that they calculate, and so if this process is successful, then we know that the example is shortlex coset automatic, independently of any general theoretical results.

Chapter 1 of (Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992) is probably the best reference for general results about finite state automata (fsa) in the context of automatic group theory. (Note that the abbreviation fsa will be used for both the singular and the plural.) Two types of fsa will be used in this paper. The first is the standard partial deterministic automaton (pda) (cf Definition 1.2.5 of Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992), in which there is at most one initial state, no epsilon transitions, and at most one transition from a given state with a given alphabet symbol. The second, which we shall call a multiple initial-state partial deterministic automaton (mipda), is the same except that there may be more than one initial state. Of course, for any mipda, one can construct an equivalent pda accepting the same language. This construction is theoretically less expensive than the general determinization process for a non-deterministic automaton, since the state-set of the equivalent pda consists of subsets of the original state-set of size at most the number of initial states, as opposed to all subsets in the general case. In general, for an fsa M, S(M) denotes the state-set of M, and A(M) the set of accept states. The set of initial states will be denoted by I(M), and ι(M) will be the unique initial state of a deterministic automaton. The image of the transition (if any) from a state τ, with label x is denoted by τ^{x}, and L(M) denotes the language accepted by M.

Mipda will arise in the following context, which is a direct generalization of similar constructions of (deterministic) word-difference automata that are described in (Epstein, Holt, Rees, 1991) and (Holt, 1996). In general, a word-difference automaton W D for G is defined to be a two-variable pda or mipda over A for which there is a map α : S(W D) → G such that, for all x, y ∈ A^{†} and all τ ∈ S(W D) for which τ^{(x,y)} is defined, we have α(τ^{(x,y)}) = \overline{x}^{−1}α(τ)\overline{y}.

Let D be the set of word-differences associated with a set of coset equations u =_{G} hv as above, and suppose that D is finite. For such an equation u =_{G} hv, let u = x_{1} … x_{n}, and v = y_{1} … y_{n}, where x_{i}, y_{i} ∈ A^{†}, and the shorter of u and v has been padded by $ symbols to make their lengths equal. Then we define an associated word-difference mipda W D, in which D is the state-set and α is the identity map as follows. The initial states of W D are 1 and the elements h ∈ H that occur in the equations, the (unique) accept state of W D is 1, and the transitions are

\overline{u(i − 1)}^{−1}h\overline{v(i − 1)}^{(x_{i},y_{i})} = \overline{u(i)}^{−1}h\overline{v(i)},

for 1 ≤ i ≤ n, for each of the equations u =_{G} hv under consideration. It is also technically convenient to include the transitions 1^{(x,x)} = 1 for each x ∈ A. This automaton has the property that it accepts (u, v)^{†}, for each of the equations u =_{G} hv. Conversely, for any padded pair of words (u, v)^{†} that W D accepts, we have u =_{G} hv for one of the initial states h. We shall call W D the basic mipda associated with the set of coset equations.

We can also extend W D as follows, without disturbing any the properties mentioned so far. For all x ∈ A, we adjoin the states x̄ to S(W D) if they are not there already. Then, for all τ ∈ S(W D), and (x, y) in A^{†} × A^{†} \ {($, $)}, we adjoin the transition τ^{(x,y)} = x̄^{−1}τȳ whenever x̄^{−1}τȳ ∈ S(W D). We call the resulting fsa the extended mipda associated with the set of coset equations.

In practice, during the course of the algorithms, we will not necessarily be able to reduce words w ∈ A^{∗} to the irreducible representatives of the corresponding elements \overline{w} ∈ G. This means that the states of our word-difference automata will not actually be elements of G but will be words in A^{∗}, and α will be the natural map onto G.

As in (Holt, 1996), if X and Y are two fsa with the same input alphabet, then we denote by X · Y, X′, X ∧ Y and X ∨ Y, fsa with accepted languages L(X)L(Y), A^{∗} \ L(X), L(X) ∩ L(Y) and L(X) ∪ L(Y), respectively. If Z is a two-variable fsa over A then there is an fsa E(Z), with input alphabet A, that accepts u ∈ A^{∗} if and only if there exists v ∈ A^{∗} with (u, v)^{†} ∈ L(Z). There are fairly straightforward algorithms for effectively constructing each of these new automata (and they are all provided in the KBMAG package, both as functions and as standalone programs). See (Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992) for details of these constructions. Again following (Holt, 1996), we denote by GT (“greater than”) a two-variable automaton which, for u, v ∈ A^{∗}, accepts (u, v)^{†} if and only if u > v in our fixed shortlex ordering on A^{∗}.

The minimization procedure for finite state automata plays an important rôle in the implementation of our algorithms. This is a procedure which, given a pda X constructs a pda Y with a minimal number of states such that L(Y) = L(X). (See, for example, Chapter 4.13 of (Aho et. al., 1974) for a description of this procedure.) In fact, it generalizes easily to automata with more than the standard two categories of states (accepting and non-accepting). In our implementation, we have the possibility of defining a finite set L of labels, and attaching a label in L to some of the states in a pda or mipda X over an alphabet A. In fact L is the (not necessarily disjoint) union of L_{I} and L_{A}, the initial and accepting labels. We can construct a pda or mipda Y with the same labelling set, and a minimal number of states subject to the property that, for any word w in A^{∗} and any l_{i} ∈ L_{I}, l_{a} ∈ L_{A}, there is a path for w in Y beginning at a state with label l_{i} and ending at a state with label l_{a} if and only if there is such a path in X. In the applications described in this paper, X and Y will be pda if L_{I} ≤ 1 and mipda if L_{I} > 1, and the distinct initial states will always have distinct labels.

The paper is organized as follows. In Sections 2 and 3, we prove the theoretical results on which the algorithms for computing, respectively, automatic coset systems, and subgroup presentations depend. In Section 4, we describe our algorithm for computing and verifying the correctness of automatic coset systems, and in Section 5, we comment on some of the issues involved in their implementation. In Section 6, we describe our algorithm for computing a presentation of the subgroup H, once the automatic coset system is known. Our current implementation computes this presentation on a set of (monoid) generators of H that is, so to speak, chosen by the computer rather than by the user. More precisely, this is the set of elements h ∈ H that arise in the coset equations ux =_{G} hv, for H-irreducible words u, v ∈ A^{∗} and x ∈ A. It should not be difficult to calculate an alternative presentation on the generators Y of H provided by the user, and we describe briefly how this could be done, but we have not yet implemented this. In the final section, we discuss the performance and results of the programs on some specific examples.

2. Theoretical results on automatic coset systems

We start by proving the result mentioned in the introduction that the coset fellow traveller property guarantees the existence of a shortlex automatic coset system.

Theorem 2.1. Suppose that there is a finite set D of elements of G with the property that, whenever u, v ∈ A^{∗} are H-irreducible, x ∈ A, and ux =_{G} hv with h ∈ H, then the word-differences associated with this equation all lie in D. Then G is shortlex coset automatic with respect to H.

Proof. Let W D be the extended mipda (as defined in Section 1) associated with the set of all coset equations ux =_{G} hv with u, v H-irreducible and x ∈ A. For any H-reducible word w ∈ A^{∗}, if u is its longest H-irreducible prefix and ux its shortest H-reducible prefix, then (ux, v)^{†} ∈ L(W D) for some H-irreducible word v ∈ A^{∗}. By definition of H-irreducible, we have ux > v, and so (ux, v)^{†} is accepted by the fsa W D ∧ GT, and w ∈ L(E(W D ∧ GT) · A^{∗}). Conversely, if w ∈ L(E(W D ∧ GT) · A^{∗}), then (ux, v)^{†} is accepted by W D ∧ GT for some prefix ux of w and some v ∈ A^{∗}, and therefore ux > v, and ux =_{G} hv for some initial state h of W D. Since these initial states are all elements of H, this implies that ux is H-reducible, and therefore w is H-reducible.

We have shown that E(W D ∧ GT) · A^{∗} accepts precisely the set of H-reducible words in A^{∗}, and so its complement W := (E(W D ∧ GT) · A^{∗})′ accepts the set of H-irreducible words, and is the correct word-acceptor for the automatic coset system.

The multiplier automata M_{x} for x ∈ A are constructed in much the same way as for automatic groups (see Definition 2.3.3 of Epstein, Cannon, Holt, Levy, Paterson and Thurston, 1992, Epstein, Holt, Rees, 1991 or Holt, 1996). (Note that, since W accepts a unique word for each coset, we must have L(M_{ε}) = {(w, w)|w ∈ L(W)}.) We first make a slight modification to W, and define a pda W^{†} which is identical to W, except that its input language is A^{†} rather than A, and it has an extra state τ, say, that is accepting, and transitions σ^{$} = τ for all σ ∈ A(W^{†}) (including σ = τ). The mipda M_{x} is defined to have state set S(W^{†}) × S(W^{†}) × S(W D). The initial states are (ι(W^{†}), ι(W^{†}), h) for h ∈ I(W D). For x, y ∈ A^{†} and (σ_{1}, σ_{2}, ρ) ∈ S(M_{x}), the transition (σ_{1}, σ_{2}, ρ)^{(x,y)} is defined to be equal to (σ_{1}^{x}, σ_{2}^{y}, ρ^{(x,y)}) provided all three components are defined, and undefined otherwise. The M_{x} for different x differ from each other only in their accept states; the accept states of M_{x} are all (σ_{1}, σ_{2}, \overline{x}) such that σ_{1}, σ_{2} ∈ A(W^{†}), and at most one of σ_{1} and σ_{2} is equal to τ. (Our definition of W D as the extended mipda associated with a set of coset equations ensures that \overline{x} ∈ S(W D) for all x ∈ A.) Note that our definition of W^{†} ensures that M_{x} is a padded two-variable mipda; that is, it accepts only padded words of the form (u, v)^{†} for u, v ∈ A^{∗}.

It is clear from the construction that, if M_{x} accepts (u, v)^{†} for u, v ∈ A^{∗}, then u and v are accepted by W, and ux =_{G} hv for some initial state h of W D, and so Hux =_{G} Hv. Conversely, suppose that u, v ∈ L(W) and Hux =_{G} Hv. Then u and v are H-irreducible and ux =_{G} hv for some h ∈ H so, by assumption, (ux, v)^{†} is accepted by W D, by a path beginning with the initial state h. Since we are using the shortlex ordering we must have l(v) ≤ l(ux). Let l(ux) = n, and v′ = v(n − 1). Then, when W D reads the word (ux, v)^{†} starting with the state h, let g be the state reached after reading the maximal proper prefix (u, v′). Then, either l(v) < l(ux), in which case v = v′ and g = x̄, or l(v) = l(ux), v = v′y for some y ∈ A, and g = \overline{xy}^{−1}. In the latter case, by the definition of the extended mipda, W D will have a transition g^{($,y)} = x̄. In either case, starting from the state h of W D, we reach the state x̄ after reading (u, v)^{†}. It follows that M_{x} accepts (u, v)^{†}, and so the word-acceptor W and the multipliers M_{x} fulfil the conditions for a automatic coset system, and the proof is complete. □

Note that the initial states of each multiplier automaton M_{x} constructed in the above proof can be labelled by distinct elements h ∈ H, and that if (u, v)^{†} is accepted by M_{x} by a path beginning with an initial state labelled h, then ux =_{G} hv in G. This fact will be important in the construction of the subgroup presentation of H, which will have this set of state-labels as its (monoid) generating set.

Our next result is used to justify the correctness verification (axiom checking) procedure that we use on candidates for our automatic coset system that we construct in the algorithm to be described in Section 3. It is a fairly straightforward generalization of Theorem 2.5 in (Epstein, Holt, Rees, 1991). We recall that G is a finitely presented group with monoid presentation ⟨A|R⟩, and H is a subgroup generated by the set Y of words in A^{∗}.

Theorem 2.2. Let W and M_{x}(x ∈ A) be finite state automata satisfying the following conditions :

(i) W has input alphabet A, and each M_{x} is a two-variable fsa over A. (ii) If (v, w)^{†} ∈ L(M_{x}) for some x ∈ A, then v, w ∈ L(W) and Hvx =_{G} Hw. (iii) L(W) is nonempty and, if x_{1} … x_{n} ∈ L(W) (where x_{i} ∈ A), then x_{1} … x_{n−1} ∈

L(W) and (x_{1} … x_{n−1}$, x_{1} … x_{n}) ∈ L(M_{x_{n}}). (iv) Let w(= w_{0}) ∈ L(W) and x_{1} … x_{n} ∈ R. Then for any w_{n} ∈ L(W), w_{0} = w_{n} if and

only if there exist words w_{1}, …, w_{n−1} ∈ L(W) for which (w_{i−1}, w_{i})^{†} ∈ L(M_{x_{i}}) for 1 ≤ i ≤ n.

(v) Let x_{1} … x_{n} ∈ Y. Then for any w_{n} ∈ L(W), w_{n} = ε if and only if there exist w_{1}, …, w_{n−1} ∈ L(W) with (ε, w_{1})^{†} ∈ L(M_{x_{1}}), …, (w_{n−1}, w_{n})^{†} ∈ L(M_{x_{n}}) (by (iii), L(W) is nonempty and is prefix closed, so ε ∈ L(W)).

Then G is coset automatic with respect to H, and W and the M_{x} form an automatic coset system in which L(W) is prefix closed, and each right coset of H in G has a unique representative in L(W).

Conversely, if the automata W, M_{x} form an automatic coset system for G with respect to H, and L(W) is prefix closed with unique representatives for each right coset, then W, M_{x} satisfy conditions (i) − (v).

Remark: Since L(W) accepts a unique word for each coset of H in G, the equality multiplier M_{ε} of the automatic coset system, which we have not mentioned explicitly in the statement of the theorem, has language {(w, w)|w ∈ L(W)}.

Proof. Suppose that W and M_{x} satisfy the conditions (i)-(v). As stated in the introduction, we are assuming throughout that A is inverse closed; that is, that for each x ∈ A, there is an x′ ∈ A such that xx′, x′x ∈ R. Let w ∈ L(W). Then, given x ∈ A, by (iv), there exists w′ ∈ L(W), with (w, w′)^{†} ∈ L(M_{x}) and (w′, w)^{†} ∈ L(M_{x′}). Let w′′ be any element of L(W) with (w, w′′)^{†} ∈ L(M_{x}). Then we have (w′, w)^{†} ∈ L(M_{x′}) and (w, w′′)^{†} ∈ L(M_{x}). But x′x ∈ R. Hence by (iv), we must have w′′ = w′. Thus, given w ∈ L(W), there exists a unique w′ ∈ L(W) such that (w, w′)^{†} ∈ L(M_{x}). Hence we have a well-defined map μ(x) : L(W) → L(W), such that wμ(x) = w′. Clearly, from the above, we have w′μ(x′) = w, and consequently μ(x′) = μ(x)^{−1}, and μ(x) is a permutation of L(W). We can immediately extend μ to a monoid homomorphism μ : A^{∗} → Sym(L(W)) (the symmetric group on L(W)).

Let x_{1} … x_{n} ∈ R (with x_{i} ∈ A) and w ∈ L(W). Then wμ(x_{1} … x_{n}) = wμ(x_{1}) … μ(x_{n}). Let w_{i} = wμ(x_{1} … x_{i}). Then (w_{i−1}, w_{i})^{†} ∈ L(M_{x_{i}}) and w_{n} = wμ(x_{1} … x_{n}). From (iv), we deduce that w_{n} = w(= w_{0}). Thus μ(r) is the identity permutation for all r ∈ R.

Consequently μ induces a well defined homomorphism μ̄ : G → Sym(L(W)). By (v), we have εμ(w) = ε for all w ∈ Y, and so εμ̄(h) = ε for all h ∈ H.

Let Ω be the set of right cosets of H in G, and define a map α : L(W) → Ω by α(w) = H\overline{w}. Suppose Hg ∈ Ω, and let x_{1} … x_{n} ∈ A^{∗}, with x_{1} … x_{n} =_{G} g. Let v_{i} = εμ(x_{1} … x_{i}). Then (v_{i−1}, v_{i})^{†} ∈ L(M_{x_{i}}). By (ii), Hv_{i−1}x_{i} =_{G} Hv_{i}. Thus Hv_{n} =_{G} Hx_{1} … x_{n} =_{G} Hg, and so α(v_{n}) = Hg and α is a surjective map.

Suppose that x_{1} … x_{n} and y_{1} … y_{m} are elements of L(W) with the same image Hg under α. By (iii), we have ε, x_{1}, x_{1}x_{2},…,x_{1} … x_{n} ∈ L(W) and (x_{1} … x_{i−1}, x_{1} … x_{i})^{†} ∈ L(M_{x_{i}}) for i = 1, …, n. Thus εμ(x_{1} … x_{n}) = x_{1} … x_{n}. Similarly, we get εμ(y_{1} … y_{m}) = y_{1} … y_{m}.

Now Hx_{1} … x_{n} =_{G} Hg =_{G} Hy_{1} … y_{m}. Thus (\overline{x_{1} … x_{n}})(\overline{y_{1} … y_{m}})^{−1} ∈ H. As we saw above, εμ̄(h) = ε for all h ∈ H, so we have

x_{1} … x_{n} = εμ̄(\overline{x_{1} … x_{n}}) = εμ̄(\overline{y_{1} … y_{m}}) = y_{1} … y_{m}.

Consequently α is a bijection and L(W) contains a unique representative for each coset, and is prefix closed due to (iii). Now, if v, w ∈ L(W) and Hvx =_{G} Hw for some x ∈ A, we know that there exists a unique w′ ∈ L(W) with (v, w′)^{†} ∈ L(M_{x}). For this w′, we have (by (ii)) Hvx =_{G} Hw′. So w′ is a representative in L(W) of the coset H\overline{vx}. By uniqueness, we deduce that w = w′, so that (v, w)^{†} ∈ L(M_{x}) as desired. Thus we have proved that the automata form an automatic structure for G with respect to H.

The fact that an automatic coset system for G with respect to H which is prefixclosed and has unique representatives satisfies (i)-(v) follows easily from the definition of an automatic coset system. □

3. Theoretical results on subgroup presentations

3.1. the composite automaton

The definition of the composite of two or more (padded) two-variable automata over the same alphabet is given in (Epstein, Holt, Rees, 1991) and (Holt, 1996). Composite automata are used in our algorithms in the verification of hypothesis (iv) of Theorem 2.2, and in the construction of defining relators for the subgroup H. In order to justify the latter process, we need to consider precisely how these composites are constructed, specifically in the case where the given automata are mipda.

Let M_{1}, …, M_{k} be padded two-variable pda or mipda over A. We define the composite language of M_{1}, …, M_{k} to be the set of all padded pairs (u, v)^{†} such that there exist u_{1}, …, u_{k−1} ∈ A^{∗} with (u, u_{1})^{†} ∈ L(M_{1}), (u_{1}, u_{2})^{†} ∈ L(M_{2}), …, (u_{k−1}, v)^{†} ∈ L(M_{k}). A corresponding composite fsa C that accepts this language is constructed as a nondeterministic automaton, as follows. (For the theoretical treatment, it is easier to allow C to be non-deterministic. In the implementation it will need to be made deterministic, and we will discuss this question in Sections 5 and 6.)

We start by adjoining transitions labeled ($, $) from σ to σ, for all accept states σ of each M_{i}. The state set of C is defined to be S(M_{1}) × S(M_{2}) × … × S(M_{k}), with initial state set I(M_{1}) × I(M_{2}) × … × I(M_{k}), and accept state set A(M_{1}) × A(M_{2}) × … × A(M_{k}). The transitions are defined as follows. For (x, y) ∈ A^{†} × A^{†}, and states σ_{i}, τ_{i} ∈ S(M_{i})(1 ≤ i ≤ k), there is a transition (σ_{1}, …, σ_{k})^{(x,y)} = (τ_{1}, …, τ_{k}), whenever there exist x_{i} ∈ A^{†}(0 ≤ i ≤ k) with x_{0} = x and x_{k} = y, and transitions σ_{i}^{(x_{i−1},x_{i})} = τ_{i} for 1 ≤ i ≤ k. In order to make C accept the correct padded words in A^{†} × A^{†}, we need to make a slight modification to its set A(C) of accept states. First we adjoin to A(C) all states from which a state in A(C) can be reached by repeated application of ($, $) (and we need to do this repeatedly until no further accept states are found). We then remove from C all transitions labeled ($, $). With this modification, it is easy to see that C accepts precisely the required composite language.

For example, in the case k = 2, if (x, xy) ∈ L(M_{1}) and (xy, x) ∈ L(M_{2}), then the modification to the accept states of C is necessary to ensure that (x, x) ∈ L(C). Similarly, if (xy, x) ∈ L(M_{1}) and (x, x) ∈ L(M_{2}), then the initial ($, $) transitions adjoined to the M_{i} are necessary to ensure that (xy, x) ∈ L(C).

3.2. subgroup presentations

Assume now that G satisfies the hypotheses of Theorem 2.1 (and so it is coset automatic with respect to H), and that W is the coset word-acceptor, and M_{x} are the coset multiplier mipda, as constructed in the proof of that theorem. Then, if w = x_{1} … x_{k} is a word in A^{∗}, we shall denote the composite automaton of M_{x_{1}}, …, M_{x_{k}} by M_{w}. It is easy to see that, for u, v ∈ A^{∗}, M_{w} accepts (u, v)^{†} if and only if u, v ∈ L(W) and Huw =_{G} Hv. Furthermore, from the remark following the proof of Theorem 2.1, we see that if this is the case, and u_{i} ∈ A^{∗}(0 ≤ i ≤ k, u_{0} = u, u_{k} = v) are the (necessarily unique) words such that M_{x_{i}} accepts (u_{i−1}, u_{i})^{†}, for 1 ≤ i ≤ k, where an accepting path in M_{x_{i}} begins with an initial state of M_{x_{i}} labelled h_{i}, then uw =_{G} h_{1}h_{2} … h_{k}v.

We call an initial state of a mipda active, if some path in the mipda starting from that state leads to an accept state. Let K be the set of labels of all active initial states of all of the M_{x}, except for 1. An active initial state of a composite multiplier M_{w}, with w as above, has the form (σ_{1}, …, σ_{k}), where σ_{i} is an active initial state of M_{x_{i}}. Let h_{i} be the label of σ_{i}. Then the label in K^{∗} for the initial state (σ_{1}, …, σ_{k}) is computed from the sequence (h_{1}, h_{2}, …, h_{k}) by omitting any h_{i} = 1 and then multiplying the remaining h_{i}. Let S be the set of all labels of all active initial states of the automata M_{w} for w ∈ R (the set of defining monoid relators of G).

Theorem 3.1. With the above notation, ⟨K|S⟩ is a monoid presentation of H.

Proof. This is proved by applying the standard Reidemeister-Schreier process as described, for example, in Section 1 of Chapter 9 of (Johnson, 1990), to the subgroup H of G. We apply this process to the given presentation ⟨A|R⟩ of G. We are assuming that this is both a group and a monoid presentation of G, but for the purpose of the Reidemeister-Schreier application, we are treating it as a group presentation. The language L(W) of the word-acceptor W is a Schreier transversal for H in G, and so our generating set

K = \{\overline{ux} \overline{v}^{−1}|u, v ∈ L(W), x ∈ A, \overline{ux} ∈ Hv̄, \overline{ux} ≠ \overline{v}\}

is precisely the set of Schreier generators for H used in the Reidemeister-Schreier presentation. (This is not strictly speaking correct, since the set of Schreier generators is really the set of formal symbols g_{u,x,v}, with u, v ∈ L(W), x ∈ A, \overline{ux} ∈ Hv̄, ux ≠ v. This set will be infinite if |G : H| is infinite. However, we are using the set of images in H of the g_{u,x,v} as generators, and we are assuming that this set is finite. This merely amounts to applying Tietze transformations to the formal Reidemeister-Schreier presentation to replace all generators that are equal in H by a single generator.)

We obtain the relators in the Reidemeister-Schreier presentation by rewriting words of the form uwu^{−1}, for u ∈ L(W) and w ∈ R, as words in the Schreier generators. To do this, we let w = x_{1} … x_{k} with x_{i} ∈ A and, for 0 ≤ i ≤ k, let u_{i} be the representative of the coset H\overline{uw(i)} in L(W). (So u_{0} = u and, since w is a relator, u_{k} = u.) Then the resulting relator is formally the word

g_{u_{0},x_{1},u_{1}}g_{u_{1},x_{2},u_{2}} … g_{u_{k−1},x_{k},u_{k}},

where a term is omitted if u_{i−1}x_{i} = u_{i}. However, since we are using the images in H as generators, we are writing this as h_{1}h_{2} … h_{k}, where u_{i−1}x_{i} =_{G} h_{i}u_{i}, and we omit h_{i} if it is equal to 1.

It is clear from the discussion above, that this word h_{1}h_{2} … h_{k} is precisely the label of the active initial state from which (u, u) is accepted by the composite automaton M_{w}. Conversely, for any active initial state of M_{w} there is, by definition, some word-pair (u, v)^{†} accepted by M_{w} that starts at this state and, since w is a relator, we must have u = v. Then rewriting the word uwu^{−1} will yield the label of this state as a relator. Thus ⟨K|S⟩ is a group presentation of the subgroup H.

To show that it is a monoid presentation, we make use of our assumption that, for any generator x ∈ A, there is an x′ ∈ A such that xx′, x′x ∈ R. Thus, for each generator h ∈ K, we have ux =_{G} hv for some u, v ∈ L(W), x ∈ A, and then vx′ =_{G} h′u, where h′ ∈ K, and h′ is equal to the inverse of h in H. Then rewriting the words uxx′u^{−1} and vx′xv^{−1} yields the relators hh′, h′h ∈ S. So it is easy to obtain a group presentation in the usual sense (not closed under inversion) of H if required, by removing generators h′ and replacing them by h^{−1} wherever they occur in relators. □

4. The algorithm to calculate a shortlex automatic coset system

Roughly speaking, the idea of the algorithm is to construct a finite set D of elements of G that we hope satisfies the hypotheses of Theorem 2.1, and then use D to construct candidates for the word-acceptor and multiplier automata for G, following the method described in the proof of Theorem 2.1. Finally, we check the correctness of these automata by using Theorem 2.2.

There are three problems with this basic idea. Firstly, our method of finding worddifferences, which uses the Knuth-Bendix procedure, cannot always produce a set D satisfying the required hypotheses, for reasons that will become clear shortly. Secondly, we need some practical methods of finding new elements to adjoin to D if the resulting automata turn out to be incorrect. Thirdly, our elements of D will have to be words in A^{∗} rather than elements of G.

We shall assume that the reader has some familiarity with the Knuth-Bendix algorithm as applied to monoid presentations. There is some discussion of this in (Epstein, Holt, Rees, 1991) and a very detailed account, together with discussions of implementations, in Chapters 1–3 of (Sims, 1994). In particular, the application of Knuth-Bendix to finitely presented groups with a specified subgroup, which is what is required in our algorithm, is described in Section 2.8 of that book.

The Knuth-Bendix algorithm works with equations, or rewriting rules u → v, in the group, and deduces new equations from the initial ones. In such a rule, we have u > v in some specified ordering on strings of the input alphabet. We use the input alphabet A∪{#}, where # is a symbol that represents the subgroup H of G. The most convenient ordering on words to use is a so-called wreath product ordering (see pages 46–50 of Sims, 1994), in which # has a smaller level than the symbols in A, all of which have the same level, and the shortlex ordering is used for words in A^{∗}. The rules that occur are of two types, the group rules, w → z, which represent equalities w =_{G} z between group elements, and the coset rules, #u → #v, which represent coset equalities Hu =_{G} Hv. Here u, v, w and z are all words in A^{∗}. As initial rules, we take w → ε, for the defining monoid relators w ∈ R of G, and #u → # for the words u ∈ Y that generate H. Note that the generators in A have inverses, and so can be cancelled on the left or right in rules, but # has no inverse, and does not cancel.

A word w ∈ A^{∗} or #u ∈ #A^{∗} is called irreducible if w or u is, respectively, the least word in the ordering that maps onto \overline{w} in G, or the least word such that ū lies in the coset Hū. (In other words, using the terminology introduced in the introduction, w or u is respectively irreducible or H-irreducible.) A group rewriting rule w → z is called minimal if z is irreducible, and w is reducible, but all of its proper prefixes and suffixes are irreducible. Similarly, a coset rewriting rule #u → #v is called minimal if v is Hirreducible, and u is H-reducible, but all of its proper prefixes are H-irreducible and all of its proper suffixes are irreducible. It can be shown (see Section 2.8 of Sims, 1994 for details) that the Knuth-Bendix algorithm eventually computes the set of all minimal rules. Since this set is usually infinite, the algorithm will not terminate in general, but it is guaranteed that any particular minimal rule will eventually be output if it is run for long enough. The procedure may also produce some non-minimal rules on the way. These will eventually be recognized as being non-minimal, and discarded, but at any given time, the current set of live rules may contain some non-minimal rules.

The problem with this approach arises from the fact that, to generate the complete set D of word-differences required for Theorem 2.1, we need all equations of the form Hux =_{G} Hv, where u and v are H-irreducible. Unfortunately, the Knuth-Bendix algorithm will not necessarily produce all of the related rewriting rules #ux → #v, since the word ux may have proper suffixes that are reducible in G, which would mean that the rule was not minimal.

Following (Holt, 1996), we shall say that a word-difference pda or mipda W D for G satisfies the property P_{1}, if it accepts all pairs (twx, tz)^{†} and (ux, v)^{†} where, respectively, wx → z and #ux → #v are minimal rewriting rules, and t is any word in A^{∗}. Our algorithm will only work if this associated set of word-differences is finite. If we assume that G and H satisfy the coset fellow traveller property, as defined in the introduction, then there will only be finitely many word-differences coming from the minimal coset equations Hux =_{G} Hv. To be certain that there will be only finitely many from the minimal group equations wx =_{G} z, we need to make the additional assumption that G itself is shortlex automatic. From what we have already said, it is clear that, if this set of word-differences is indeed finite then, if we run the Knuth-Bendix procedure for long enough, sufficient rewriting rules will be output such that the associated set of word-differences will contain this complete set, and then the basic word-difference mipda associated with these equations, as defined in the introduction, will satisfy P_{1}. (It may also contain extra word-differences, since, at any given time, some of the rewriting rules may not be minimal.)

We shall say that a word-difference pda or mipda W D for G satisfies the property P_{2}, if it accepts all pairs (u, v)^{†} for which ux =_{G} hv with h ∈ H, u and v are H-irreducible, and x ∈ A or x = ε. The extended word-difference mipda associated with the set of all such equations ux =_{G} hv (cf proof of Theorem 2.1) satisfies P_{2}.

We can now describe the complete algorithm, which is a direct generalization of that described in (Holt, 1996) for shortlex automatic groups G.

Step 1. Construct word-difference mipda W D_{1} and W D_{2} for G, which we hope satisfy P_{1} and P_{2}, respectively. Step 2. Construct a candidate for the coset word-acceptor W. Step 3. Construct mipda candidates for the multipliers M_{x}, for all x ∈ A. If, during this construction, we find distinct words u and v in A, both accepted by W, with Hu =_{G} Hv, then modify W D_{1} and return to Step 2. Step 4. Determinize the M_{x}; that is, construct pda that accept the same language. Step 5. Check correctness of the M_{x} assuming the correctness of W. If incorrect, modify W D_{2} and return to Step 3. Step 6. Check correctness of W and M_{x}. If incorrect, return to Step 1 (or give up!).

We shall now give more details of each of these steps, from a theoretical viewpoint. Implementation issues will be discussed in the following section. Step 1 is just the Knuth-Bendix procedure, which we have already discussed. Since this procedure normally runs forever by default, it needs to be interrupted at some stage, and the word-difference machines W D_{1} and W D_{2} computed and output. These are essentially the basic and extended mipda calculated from the current set of reduction rules. However, since we cannot be certain that a word is irreducible or H-irreducible at this point, their states will not necessarily correspond to distinct elements in G. In fact, their states are words in A^{∗} that cannot be reduced by using the current set of reduction rules, and the map α (see definition of word-difference machine in the introduction) is the natural map onto G. Of course ε will always be one of these states (and indeed an initial state and the unique accept state), and to conform with the technical condition of property P_{1} that W D_{1} should accept the group reduction rules preceded by the prefix (t, t) for any t ∈ A^{∗}, we adjoin transitions ε^{(x,x)} = ε for all x ∈ A to W D_{1} if necessary.

In Step 2, we construct W using the standard finite state automaton operation

W = (E(W D_{1} ∧ GT) · A^{∗})′,

where GT is the “greater than” automaton for the shortlex ordering, as defined in the introduction. Expressed in words, W accepts w ∈ A^{∗} if and only if it does not have a prefix u such that there exists v ∈ A^{∗} with u > v and (u, v)^{†} accepted by W D_{1}. Note that our construction of W D_{1} (and formulation of the property P_{1}) ensure that if (w, z)^{†} is accepted by W D_{1} where w → z is a reduction in G, then (tw, tz)^{†} is also accepted by W D_{1} for any word t ∈ A^{∗}, and so reductions in G occurring in the middle of words are recognized by W D_{1}. (The coset reductions of the form #ux → #v can only occur on prefixes of words.) It is thus clear that, if W D_{1} really does have property P_{1}, then W will accept precisely the set of H-irreducible words; in other words, it will be correct. (In practice, we often use W D_{2} in place of W D_{1} in the construction of W. This will be discussed in the next section.)

Step 3 is done following the recipe described in the proof of Theorem 2.1. The words u and v referred to in Step 3 can arise if there is some minimal reduction rule w → z or #u → #v that was not found by the Knuth-Bendix procedure, so (w, z)^{†} or (u, v)^{†} is not accepted by W D_{1}, but it does happen to be accepted by W D_{2}. (There is no particular reason to expect this to occur, but in practice it seems to be quite common.) In that case, we simply modify W D_{1} so that it does accept this missing reduction rule, and return to Step 2. (If, however, we are using W D_{2} rather than W D_{1} to construct W, then this situation will never occur when Step 3 is executed immediately after Step 2. It can still occur though, if Step 3 is executed after returning from Step 5 with an updated version of W D_{2}. In that case, we simply return to Step 3 without updating W D_{1}.)

Step 4 is a routine operation on finite state automata. We observe at this stage that we can use W D_{1} or W D_{2} to reduce any word u ∈ A^{∗} to a word v ∈ L(W) with Hu =_{G} Hv. To do this, we examine all prefixes u′ of u, and by using a systematic search of the relevant W D_{i}, we look for words v′ with (u′, v′)^{†} ∈ L(W D_{i}) and u′ > v′. If we locate such pairs, then we substitute v′ for u′ in u and repeat until we find no new reductions. We must then have u ∈ L(W). We call this process coset word reduction using W D_{i}. If we used W D_{2} to construct W, then we must also use it for coset word reduction (since some of the required substitutions might not be accepted by W D_{1}). However, word reduction is often quicker using W D_{1}.

To explain Step 5, suppose that W is correct but one or more of the M_{x} is not correct. From the construction of M_{x}, it is clear that, if M_{x} accepts (u, v)^{†}, then W accepts u and v, and Hux =_{G} Hv. Thus, there exist words u and v in A^{∗} such that W accepts u and v and Hux =_{G} Hv, but M_{x} does not accept (u, v)^{†}. But then, since v is the unique word accepted by W that lies in the coset Hux (given that W is correct), M_{x} cannot accept (u, w)^{†} for any w ∈ A^{∗}. So we can test for this, by constructing the automata W ∧E(M_{x})′ for each x ∈ A, and we do this in Step 5. If all of these automata have empty accepted language and W is correct, then the M_{x} must also be correct, and we proceed to Step 6 for the complete verification. Otherwise, we find some explicit words u that are not accepted by some W ∧ E(M_{x})′, and we let v be the reduction of ux (using coset word reduction, as described above); then W accepts v and Hux =_{G} Hv. Since M_{x} does not accept (u, v), there must be prefixes u(k) and v(k) of u and v of the same length, such that there is no word representing \overline{u(k)}^{−1}h\overline{v(k)} in S(W D_{2}), where h = \overline{ux} \overline{v}^{−1}. We therefore adjoin reduced words for all such elements and their inverses to S(W D_{2}), and then recalculate W D_{2} itself, and return to Step 3.

The final correctness verification (Step 6) is performed by verifying the hypotheses (i)-(v) of Theorem 2.2. If we succeed in this, then the correctness of W and the M_{x} follows from this theorem. In fact our constructions of W and the M_{x} ensure that the hypotheses (i)-(iii) hold automatically. Hypothesis (iv) is checked by constructing the composite multiplier automata M_{w} (as defined at the beginning of Section 3) for the relators w ∈ R of G, and verifying that they are equal to the identity multiplier M_{ε}, which has language {(w, w)|w ∈ L(W)}.

For hypothesis (v), we only need to check that the composite automata M_{y} for y ∈ Y accept (ε, ε). (If hypotheses (i)-(iv) are true, then we already know that, for any u ∈ A^{∗}, there is a unique word v ∈ A^{∗} such that (u, v)^{†} ∈ L(M_{y}).) This almost follows from the constructions, given that #y → # was one of the initial reduction rules, in the Knuth-Bendix procedure, but it seems difficult to prove it formally. However, to verify it, we do not need to construct M_{y} explicitly. Suppose y = x_{1} … x_{n}, let w_{0} = ε and, for 1 ≤ i ≤ n, let w_{i} be the unique word in L(W) such that (w_{i−1}, w_{i})^{†} ∈ L(M_{x_{i}}). Then we can calculate the w_{i} easily by carrying out coset reduction on w_{i−1}x_{i}, as described above, and to verify hypothesis (v) we need only check that w_{n} = ε for each y ∈ Y.

5. Implementation Issues

In this section, we shall discuss some of the issues involved in implementing the six steps of the algorithm described in Section 4, and mention some of the decisions taken in the KBMAG package.

We shall not go into details about implementing the Knuth-Bendix procedure, since this question has been extensively treated in Chapters 1–3 of (Sims, 1994), and most of the nontrivial ideas involved in our own program are derived from that source. The only additional point worth making is that it appears to be definitely advantageous to give priority to those reduction rules that give rise to new word-differences, when deciding which rules to use for overlap searching. Giving priority to shorter rules, on the other hand, does not seem to make much difference. These are purely heuristic remarks, based on the examples that we have run.

The main problem for us in Step 1 is to decide when to halt the Knuth-Bendix procedure. Roughly speaking, we want to stop when no new word-differences have appeared for some time. This decision is complicated by the fact that in some larger examples there can be very long gaps between successive appearances of new word-differences. Another technical difficulty is that the existence of some non-minimal reduction rules in the current set of rules can mean that some word-differences can appear and then disappear again, sometimes repeatedly. In our implementation, the program can either be run in verbose mode, when it delivers regular reports on the current number of word-differences, and the user can then halt it interactively when this appears to have stabilized, or it can be given its own internal halting criteria. The default for this is that the total number of reduction rules should have doubled, with no new word-difference appearing, but this factor can be set by the user using a command-line option. If the procedure is halted with a few essential word-differences still missing, then this is not always disastrous, since the remaining steps in the procedure have the capability of finding missing worddifferences. However, this usually seems to have the effect that they take longer to run and require more space than when run with the correct complete set of word-differences. (In other words, experience shows that these procedures run most smoothly when given the correct input data. There is no obvious theoretical reason why this should be the case, but it is perhaps not surprising. In fact several of the steps involve determinizing non-deterministic automata, which is a process with exponential complexity, and so, in a sense, it is only by good fortune that the algorithms turn out to be practical at all!)

The construction in Step 2 could be performed by piecing together our basic procedures for the logical operations on automata. In practice we have written a single procedure that does it all at once, which turns out to be considerably more efficient. (It can take advantage of a few technical conditions that would not necessarily hold for general automata, such as the fact that, in a minimal reduction rule u → v or #u → #v, we have l(u) = l(v), l(v) + 1 or l(v) + 2. This depends of course on the fact that we are using the shortlex ordering on A^{∗}.) We have also discovered through experience that, in many examples, the complete algorithm runs faster if we use W D_{2} in place of W D_{1} in the construction of W, even though this usually makes Step 2 itself slower, since W D_{2} contains many more transitions than W D_{1}, most of which are theoretically unnecessary for the correct construction of W. The reason that the complete algorithm can become faster with W D_{2} is that it often performs fewer returns to Step 2 from Step 3 in that case. In fact KBMAG now uses W D_{2} by default, although the user can elect to use W D_{1}, and there are some examples where the algorithm only completes at all if we use W D_{1}.

Turning to Step 3, from the proof of Theorem 2.1, we notice that the multiplier automata M_{x} all have the same states and transitions, and differ only in their accept states. We make use of this fact in the implementation, by computing and storing a single generalized multiplier automaton M_{G}, that has labeled states, as described in the introduction. The initial labels L_{I} will be the empty word ε and the reduced words in A^{∗} representing the initial states h ∈ H, and the accepting labels will be the generators x ∈ A and ε. Then the accept states of M_{x} will be precisely those with label x. Our implementation ensures that the only word pairs (u, v)^{†} that lead from an initial state to ε are (u, u) for all u ∈ L(W). (This is because, whenever we discover such a pair with u ≠ v, then we abort the construction of M_{G}, and return to Step 2.) We can then perform the minimization operation on M_{G} while maintaining these state labels, as described in the introduction. Experience shows that this generalized minimized multiplier has very few more states than the individual minimized multipliers. It is in any case completely straightforward to construct the individual multipliers from M_{G} if required.

Another point about our implementation of Step 3 is that we do not necessarily abort the construction of M_{G} with the first appearance of an equation Hu =_{G} Hv for u, v ∈ L(W). Instead, we continue and store up to a specified number of such rules (a few hundred works quite well in practice), and then abort the construction and use these stored rules to update W D_{1}.

Step 4 is performed on the generalized minimized multiplier M_{G}. We did experiment with an alternative strategy of determinizing W D_{2} before constructing the M_{x} in Step 3, so the M_{x} were constructed as pda, but this turned out to be very inefficient, since the determinized version of W D_{2} tended to have a huge number of states.

For Step 5, we have coded the construction of the W ∧ E(M_{x})′ as a single function that takes W and the (minimized) generalized multiplier M_{G} as input, so it is effectively calculating all of these test automata simultaneously, and it will notice (and abort if required) whenever a word is found that is accepted by any of these automata. This is another big advantage that is gained by using M_{G} rather than the individual M_{x}. (This feature applies equally well to the calculation of shortlex automatic structures for groups G (with no subgroup involved), and represents an improvement of our latest package KBMAG over the original Warwick Automata package that was described in (Epstein, Holt, Rees, 1991) and (Holt, 1996).) As in Step 3, we store up to a specified number of words accepted by some W ∧ E(M_{x})′, then abort the construction and update W D_{2}.

The main computational problem in Step 6 is the construction of composite automata M_{w} for words w ∈ A^{∗}, as described in Section 3.1. Note that all of the composite automata concerned here have a unique initial state (they are pda), since the mipda versions of the M_{x} were converted to pda in Step 4. Let us denote the language of M_{w} by L_{w}. It is clear that, if we define a multiplication operation on such languages L_{w} by

L_{w_{1}}L_{w_{2}} = {(u, v)^{†}|∃t ∈ A^{∗}, (u, t)^{†} ∈ L_{w_{1}}, (t, v)^{†} ∈ L_{w_{2}}},

then this operation is associative, and the product L_{w_{1}}L_{w_{2}} is equal to L_{w_{1}w_{2}}. Furthermore, L_{ε} = L(M_{ε}) = {(w, w)|w ∈ L(W)} is an identity element, and so the set of all such languages forms a monoid.

Verifying hypothesis (iv) of Theorem 2.2 involves checking the equality of two such languages. Since we are working with automata rather than languages, we call two fsa equivalent if they have the same language, and we need to find a canonical member of each equivalence class, so that we can use these to check for equality between their languages. Fortunately there is a standard way of doing this. The composite automata in Section 3.1 were defined as nondeterministic automata. First we we need to determinize them, then minimize them, and finally permute their states so that they appear in order when we scan the transition table. This provides the required canonical representative. (In fact, in our implementations, the final step of permuting the states is unnecessary, since the minimization procedure puts the states into the desired order already.)

It turns out to be most efficient to construct only composites of two automata at a time, and to determinize and minimize the result, before repeating the construction. In fact, our implementation is described very simply, recursively, as follows. Let w = w_{1}w_{2}, where |l(w_{1})−l(w_{2})| ≤ 1. If l(w_{1}) > 1, then construct M_{w_{1}}, determinize it and minimize it, and similarly for w_{2}. Then construct M_{w} as the composite of M_{w_{1}} and M_{w_{2}}, determinize it and minimize it. In practice, we perform the construction and determinization together, by storing the states of the composite of automata M_{u} and M_{v} as subsets of S(M_{u})×S(M_{v}).

We can make Step 6 a little more efficient as follows. First, we compute M_{w} for the inverse monoid relators w = xx′ ∈ R, and check that they are all equal to M_{ε}. If this is the case, then we know that the monoid of composite languages described above is a group in which L_{x} and L_{x′} are mutual inverses. It then follows that, if w = w_{1}w_{2} is a long relator, and w′_{2} is the word obtained from w_{2} by reversing it and replacing every letter x by x′, then L_{w} = L_{ε} if and only if L_{w_{1}} = L_{w′_{2}}. It is usually quicker to check this latter condition, since it avoids the final (and slowest) stage of calculating L_{w} itself.

6. The algorithm to compute a subgroup presentation

6.1. subgroup presentations on the schreier generators

Assuming that we have already computed and verified the correctness of the automatic coset system for G with respect to H, to construct a subgroup presentation we need only calculate the generators K and relators S as defined in Section 3.2.

The principal operation involved here is the formation of composite automata M_{u} for words u ∈ A^{∗}. The difference from the construction of composites described above for verifying correctness of the automatic coset system, is that we now need to construct the composites as mipda. In other respects, the implementation is similar, in that we construct composites recursively, by splitting the word u roughly in half as u = u_{1}u_{2}. We then construct M_{u_{1}} and M_{u_{2}}, determinize their transition tables and minimize them (while maintaining the labels of their initial states, in the manner described in the introduction), and then construct the composite M_{u} of M_{u_{1}} and M_{u_{2}}, and determinize its transition table and minimize it.

To obtain K and S, we need to be able to locate the active initial states of a mipda, as defined in Section 3.2. This is done by a routine search of the transition table, to see whether any path starting from a particular initial state can lead to success. In the implementation, we remove any inactive initial states from the list of initial states. Having done that, we remove all states of the mipda that cannot be reached from a path starting at an active initial state, in order to make the mipda accessible.

We start the procedure by locating the active initial states of our generalized multiplier mipda M_{G} that was constructed in Step 3 of the main algorithm described in Section 4. (We are assuming that that algorithm was run successfully to completion, so we know that M_{G} is correct.) We then relabel these states with suitable symbols, since they form the generating set K for H. The initial state set of the composite mipda of the mipda M_{u} and M_{v} is, in general, equal to I(M_{u}) × I(M_{v}), and we label such an initial state (σ_{1}, σ_{2}) as w_{1} ∗ w_{2}, where w_{1}, w_{2} are the labels of σ_{1}, σ_{2}, respectively. This has the effect that the labels of the (active) initial states of the mipda composites M_{w} for w ∈ R are words in K, and so we obtain the required set S of defining relators for H as the set of these labels coming from all w ∈ R.

As is the case with subgroup presentations computed with current Reidemeister-Schreier implementations for finite index subgroups, the resulting presentation tends to be very highly redundant, but it is easily simplified, by using Tietze transformations. In our implementation, the subgroup presentation ⟨K|S⟩ is output in the format of the GAP system, so that it can be easily read into GAP and simplified, if required.

6.2. subgroup presentations on the user generators

It might be desirable to be able to construct a presentation for H using the given set Y as generators, rather than the set K of Schreier generators. In principle, this could be done quite easily, although we have not yet implemented it completely. Since Y is actually a set of words, we need to introduce a new set of symbols Y′, disjoint from X and in one-one correspondence with Y.

All that we need to do is to compute sets E_{K,Y} and E_{Y,K} of equations in G that respectively express the generators in K as words in Y, and vice versa. We then use E_{K,Y} to rewrite the words in S and the equations E_{Y,K} as words (or equations) in the generators Y, and it follows directly from the theory of Tietze transformations that the resulting relators and equations define a presentation for H on Y.

To compute E_{Y,K} we simply carry out coset reduction using W D_{1} or W D_{2}, as described in Section 4, on the words y ∈ Y. Since y ∈ H, y will reduce to the empty word, but we can keep track of the initial states of W D_{i} (which correspond to the generators K) that occur in the course of the reduction, and the result will be to rewrite y as a word in K^{∗}.

Computing E_{K,Y} is less straightforward, but we have already implemented this part. We need to run the Knuth-Bendix procedure in Step 1 of the main algorithm using an extended generating set, which includes the set Y′ mentioned above, of new symbols, in one-one correspondence with Y. These all have the same level as #, which is less than that of the symbols in A, in the wreath product ordering on the complete set of symbols. The initial coset reduction rules #y → #, for y ∈ Y, are replaced by #y → y′#, where y′ ∈ Y′ corresponds to y ∈ Y and, in the coset reduction rules computed by the Knuth-Bendix process, #u → #v is replaced by #u → t#v, for some word t in Y^{′∗}. Since the elements \overline{uv}^{−1} ∈ H coming from these rules are precisely the generators K derived from the M_{x}, the words t provide the required rewriting of the elements of K as words in Y′.

There is an additional complication in that some of the generators in K may not come directly from the Knuth-Bendix procedure, but may appear during the iterations through Steps 2–5 of the main procedure. However, at the point when a new generator in K is introduced, there is always enough information present to write it as a word in the existing generators, and so this should not present a problem. Since this process has not yet been implemented, however, there seems little to be gained by going into further details at this stage.

7. Examples

In this final section, we describe the performance of our algorithms on three examples. The programs were run on a SparcStation 20 running Solaris 2, with 256 Megabytes RAM, and using the C-compiler gcc. In general, the axiom checking process (Step 6) requires the most time and space in the algorithm for computing automatic coset systems, but calculating the subgroup presentation usually requires even more resources. The reason is that, in both cases, the bulk of the time is taken up with computing composite multipliers M_{w} for words w ∈ A^{∗} and, in general, the longer the word w, the more resources this will require. When we compute a subgroup presentation, we have to calculate the full composite multipliers M_{w} for the group relators w, whereas, as we saw in Section 5, to verify a group relator w in Step 6, we do not need to compute M_{w} itself, but only M_{w_{1}} and M_{w_{2}}, where w_{1} and w_{2} are about half as long as w.

The examples described in (Redfern, 1993) that were used for the drawings of circle packings are all either subgroups of free groups or of various Coxeter groups. All of these completed very quickly for us. For example, for the group

G = ⟨a, b, c, d | a^{2}, b^{2}, c^{2}, d^{2}, (ab)^{4}, (ac)^{3}, (ad)^{2}, (bc)^{4}, (bd)^{4}, (cd)^{4}⟩

with the subgroup H = ⟨b, c, d⟩, which Redfern refers to as “Full Tetrahedron”, Steps 1–5 of the algorithm in Section 4 took a total of 4 seconds (it goes once back round the loop from Step 5 – Step 3), Step 6 (axiom checking) took 6 seconds, and calculating the subgroup presentation took 7 seconds. The word-difference machine W D_{2} has 40 states, the word-acceptor W has 46 states, and the generalized multiplier M_{G} has 192 states as a mipda and 185 states after determinization. The subgroup presentation comes out on three generators, which are in fact b, c and d, with the same relators as those in the original presentation of G that involve b, c and d. (This could have been predicted from the general theory of Coxeter groups.)

The other two examples are not quite so easy. For our second example, we take the Fibonacci group F (2, 8) with the presentation

G = ⟨a, b, c, d, e, f, g, h |
ab = c, bc = d, cd = e, de = f, ef = g, fg = h, gh = a, ha = b⟩

which, like all F (2, 2n) for n ≥ 4 is known to be word-hyperbolic, with the subgroup H = ⟨a, e⟩. Step 1 of the algorithm took 30 seconds, and produced W D_{2} with 89 worddifferences. Steps 2–5 took 20 seconds, with no looping, where W has 228 states, and M_{G} has 1978 states as mipda and 1944 states as pda. Step 6 took 173 seconds, requiring about 5.5 Megabytes of space. Computing the subgroup presentation took about 4300 seconds, and about 15 Megabytes of memory. The presentation comes out on 28 monoid generators (that is, 14 group generators), which simplifies to a free group of rank 2, and so in fact H must be a free group on its defining generators a and e.

For our final example, we take the group

G = ⟨x, y, z | [x, [x, y]] = z, [y, [y, z]] = x, [z, [z, x]] = y⟩,

where the commutator [u, v] is defined to be u^{−1}v^{−1}uv. This was proposed by Heineken several years ago as a possible candidate for a finite group with a balanced cyclic presentation. However, we were able to show, using KBMAG, that it is shortlex automatic (in fact, it is even word-hyperbolic), and its generators have infinite order, so it cannot be finite. We used this group as input to our subgroup programs, with the subgroup H = ⟨[x, y], [y, z], [z, x]⟩. Step 1 took 105 seconds, and W D_{2} has 279 states. Steps 2–5 took 58 seconds, with no looping, where W has 58 states, and M_{G} has 2520 states as mipda and 2536 states as pda. Step 6 took 399 seconds, using 7 Megabytes of space. Computing the subgroup presentation took about 2800 seconds, and used up to 27 Megabytes. The presentation has 10 monoid generators (that is, 5 group generators), which simplifies to a free group of rank 3, and so again H must be a free group on its defining generators.

We have run the program on many other examples, including some where |G : H| is finite. This typically takes rather longer than the straightforward application of the Reidemeister-Schreier algorithm, but it serves as a useful check on the correctness of our programs, since we have an alternative method of doing the same computation in these cases.

References

Aho, A.V., Hopcroft, J.E., Ullman, J.D. (1974). The Design and Analysis of Computer Algorithms,

Addison-Wesley, Reading, MA. Epstein, David B.A., Cannon, J.W., Holt, D.F., Levy, S., Patterson, M.S., Thurston, W. (1992). Word

Processing in Groups, Jones and Bartlett. Epstein, D.B.A., Holt, D.F., Rees, S.E. (1991). The use of Knuth-Bendix methods to solve the word

problem in automatic groups. J. Symbolic Computation 12, 397–414. Gersten, S.M., Short, H.B. (1991). Rational Subgroups Of Biautomatic Groups. Ann. Math. 134, 125–

158. Holt, D.F. (1996). The Warwick automatic groups software. In Geometrical and Computational Per-

spectives on Infinite Groups. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 25, ed. Gilbert Baumslag et. al., 69–82.

Hurt, D.F. (1996). The Use of Knuth-Bendix Methods and Automatic Coset Systems for Solving the Generalized Word Problem and Finding Subgroup Presentations. PhD Thesis, University of Warwick.

Johnson, D.L. (1990). Presentations of Groups. London Math. Soc. Student Texts 15, Cambridge Uni-

versity Press. McShane, G., Parker, J., Redfern, I. (1994). Drawing Limit Sets of Kleinian Groups Using Finite State

Automata. Experimental Mathematics 3, 153–172. Redfern, I.D. (1993). Automatic Coset Systems. PhD Thesis, University of Warwick. Sims, Charles C. (1994). Computation with Finitely Presented Groups. Encyclopedia of mathematics

48, Cambridge University Press.