Automatic groups, subgroups and cosets

Derek F. Holt

Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK. email: dfh@maths.warwick.ac.uk

Abstract

The history, definiton and principal properties os automatic groups and their generalisations to subgroups and cosets are reviewed briefly, mainly from a computational perspective. A result about the asynchronous automaticity of an HNN extension is then proved and applied to an example that was proposed by Mark Sapir.

AMS Classification numbers: Primary: 20F32 Secondary: 20F05

Keywords: Automatic Groups, HNN extensions

Date of submission: 26/08/1997 The concept of an automatic group was introduced in 1986 by Thurston, motivated by some results of Jim Cannon on hyperbolic groups. Much of the basic theory of this important class of groups was developed by David Epstein during the following few years.

In the first section of this paper, we review briefly the history, definition and properties of automatic groups and their generalisation to subgroups and cosets, mainly from a perspective of carrying out efficient computations within such groups and their subgroups. In the second section, we prove a result about the (asynchronous) automaticity of an HNN extension, and use it, together with the results of some machine computations, to prove that a particular group, defined by Mark Sapir, is asynchronously automatic.

1 Definitions and Discussion

1.1 Automatic Groups

In 1986, W. Thurston noticed that some results of J.W. Cannon in [Cannon, 84] about cocompact discrete hyperbolic groups could be reformulated in terms of finite state automata (fsa; this abbreviation will be used for both the singular and plural). This led to the definition of an automatic group.

Definition 1.1 Let G be a group with finite generating set X, let A = X ∪ X^{−1} , and let A′ = A ∪ {$}, where $ ∉ A. Then G is said to be automatic (with respect to X), if there exist fsa W and M_{a} for each a ∈ A, such that (i) W has input alphabet A, and accepts a unique word in A^{∗} mapping onto each element of G. (ii) Each M_{a} has input alphabet A′ × A′, it accepts only padded pairs, and it accepts the padded pair (w^{+}, x^{+}) for w, x ∈ A^{∗} if and only if w, x ∈ L(W) and wa =_{G} x.

Here A^{∗} as usual denotes the set of words in A. For w ∈ A^{∗}, \overline{w} denotes the element of G onto which w maps; for w, x ∈ A^{∗}, we also use w =_{G} x to mean that w, x map onto the same element of G. For w, x ∈ A^{∗}, the associated padded pair (w^{+}, x^{+}) ∈ (A′ × A′)^{∗} is obtained by adjoining symbols $ to the shorter of w and x to make them have equal length. The language of the fsa W is denoted by L(W). For general properties of finite state automata, the user is referred to any textbook on automata or formal language theory, such as [Hopcroft and Ullman, 1979].

In the definition, W is called the word-acceptor and the M_{a} the multiplier automata. The complete collection {W, M_{a}} is known as an automatic structure for G.

The best general reference for the theory of automatic groups is the multi-author book [Epstein et. al., 1992]. In particular, it turns out that the automaticity of G is independent of the choice of generating set X. All finite groups are easily seen to be automatic; in fact the class of automatic groups is invariant under finite variations, such as sub- and super-groups of finite index. It is also closed under direct and free products, and includes, for example, all wordhyperbolic groups, braid groups, Coxeter groups and Artin groups of finite type. All automatic groups have finite presentations.

One important application of automatic structures for groups G is their use for the efficient (quadratic time) solution of the word problem in G. More precisely, the multiplier automata can be used to reduce an arbitrary word in A^{∗} in quadratic time to the G-equivalent word in L(W).

With this aim in mind, a collection of programs was written at Warwick in the late 1980’s for computing automatic structures. These programs take a finite presentation of the group G as input. Currently, they only work for so-called shortlex structures, which are those in which L(W) consists of the lexicographically least amongst the shortest words that map onto each group element. (So W depends upon the order of A as well as on A itself.) Many, but not all, of the known classes of automatic groups are known to possess shortlex structures. The programs are described in some detail in [Epstein, Holt, Rees, 1991] and [Holt, 1995], and more generally in [Epstein et. al., 1992]. The latest version is part of a package called kbmag and is available by anonymous ftp from

ftp.maths.warwick.ac.uk in the directory people/dfh/kbmag2.

There are a number of slightly different, but equivalent definitions of an automatic group in the literature. One common variant is to assume only that W accepts at least one word for each group element, and to have a further two-variable fsa M_{ε} that recognises when two words in L(W) map onto the same element of G. Another possibility is to replace the existence of the multiplier automata and the second hypothesis by the so-called (synchronous) fellow traveller property, defined as follows.

For a word w ∈ A^{∗} we denote the length of w by l(w) and, for g ∈ G, l(g) (or more precisely l_{A}(g)) denotes the length of the shortest word w ∈ A^{∗} with \overline{w} = g. For t ≥ 0, w(t) denotes the prefix of w of length t when t ≤ l(w), and w(t) = w for t ≥ l(w). The fellow traveller property asserts that there exists a constant k such that, for all w, x ∈ L(W) and a ∈ A such that wa =_{G} x, and all t ≥ 0, we have l_{A}(\overline{w(t)}^{−1}\overline{x(t)}) ≤ k. In other words, two travellers proceeding at the same speed along the words w and x from the base point in the Cayley graph of G would always remain a bounded distance away from each other.

The fellow-traveller property enables the multiplier automata M_{a} to be defined in a uniform manner (see Definition 2.3.3 of [Epstein et. al., 1992]). Their state set is the set of triples (s_{1}, s_{2}, g), where s_{1}, s_{2} are states of W, and g ∈ G with l(g) ≤ k. The start state is (s_{0}, s_{0}, 1), where s_{0} is the start state of W. For (a_{1}, a_{2}) ∈ A × A, there is a transition from (s_{1}, s_{2}, g) to (t_{1}, t_{2}, h) with label (a_{1}, a_{2}) if and only if there are transitions s_{1} → t_{1} and s_{2} → t_{2} in W with labels a_{1} and a_{2} , respectively, and if a_{1}^{−1}ga_{2} =_{G} h. The state (s_{1}, s_{2}, g) is a success state of M_{a} if and only if s_{1} and s_{2} are success states of W, and g =_{G} a. Thus the M_{a} differ only in their accept states. (We have omitted a technicality from this definition. To deal with the padding symbol, we have to add an extra state to W which is reached when W is in an accept state and the padding symbol is read.) It is clear that the M_{a} behave precisely according to Condition (ii) of Definition 1.1. This method is used to construct the M_{a} in the programs mentioned above.

Note also that it follows from the fellow-traveller property that if g is any fixed element of G and w, x ∈ L(W) with wg =_{G} x, then w and x fellow-travel with constant at most kl_{A}(g).

Finally, we must mention the weaker concept of an asynchronously automatic group, because it will arise in the next section. The definition is the same as before, except that the multiplier automata are allowed to read their two input strings at different rates. More precisely, rather than reading one symbol from each of the two input words at each transition, they read a symbol from one of the two words only, where the choice of which word to read is a function of the state of M_{a}. Of course, when the end of one of the words is reached, the other word must be selected. See Chapter 7 of [Epstein et. al., 1992] for the formal definition. Again there is a corresponding fellow-traveller property, in which the imaginary travellers are allowed to move at different speeds. See [Epstein et. al., 1992] or Section 7, Part II of [Baumslag et al, 1991] for details.

The word problem is still solvable for asynchronously automatic groups, but it is unknown whether this can be done in polynomial time. There are examples known, such as the Baumslag-Solitar groups ⟨x, y | y^{−1}x^{p}y = x^{q} ⟩ with p ≠ q, which are asynchronously automatic but not automatic.

There is a more detailed treatment, with references to the literature, of the synchronous and asynchronous fellow-traveller properties in groups in the article [Rees, 1997] in these proceedings.

1.2 Subgroups

Let L = L(W) be the language of the word-acceptor in an automatic structure of a group G. A subgroup H of G is called L-rational if L ∩ H is a regular language (i.e. the language of an fsa). Such subgroups were studied in [Gersten and Short, 1994], where it is proved that L-rational is equivalent to L-quasiconvex. This means that any prefix of a word in L ∩ H lies within a bounded distance of H in the Cayley graph of G. Such subgroups are always finitely generated.

An algorithm for constructing an fsa W_{H} with language L ∩ H, which takes as input an automatic structure for G and a set of generators for an L-rational subgroup H of G, is described in [Kapovich, 1995]. A practical and efficient version is described in [Hurt, 1996], and an implementation is available in kbmag.

The fsa W_{H} can be used together with the automatic structure to determine whether a given word in A^{∗} lies in H; that is, to solve the generalised word problem for H in G. First use the the multiplier automata to reduce the word to one in L, and then use W_{H} to test whether it lies in H.

1.3 Cosets

It is possible to generalise the concept of an automatic group from a notion about the elements of the group to one about the cosets of a given subgroup H of G. This has been carried out by two doctoral students of the author (see [Redfern, 1993] and [Hurt, 1996]). The definition is as follows.

Definition 1.2 Let G be a group with finite generating set X, let A = X ∪ X^{−1} , A′ = A ∪ {$}, and let H be a subgroup of G. Then G is said to be coset automatic with respect to H, if there exist fsa W, and M_{a} for each a ∈ A, such that:

(i) W has input alphabet A, and accepts a unique word in each right coset of H in G; (ii) Each M_{a} has input alphabet A′ × A′, it accepts only padded pairs, and it accepts the padded pair (w^{+}, x^{+}) for w, x ∈ A^{∗} if and only if w, x ∈ L(W) and H\overline{wa} = Hx̄.

Here W is called the coset word-acceptor and the M_{a} the coset multiplier automata. The complete collection {W, M_{a}} is known as an automatic coset system for the pair (G, H). Again the existence of such a system turns out to be independent of the generating set X of G. It is proved in [Redfern, 1993] that if L is the language of the shortlex automatic structure of a word-hyperbolic group G (or even the set of all geodesics in the Cayley graph of G), and if the subgroup H is L-quasiconvex, then G is coset automatic with respect to H. In [Hurt, 1996] the converse is proved for wordhyperbolic groups, although we shall see from the example in the next section that the converse does not hold in general. An interesting application to the drawing of limit sets of Kleinian groups is described in [McShane et. al., 1994]. An algorithm for computing automatic coset systems in the shortlex case was first described in [Redfern, 1993], and was implemented by him as a standalone program. It has the disadvantage that it is not usually possible to prove conclusively that the system computed is correct. A different approach is described in [Hurt, 1996]. This does enable the output to be proved correct, but it requires an additional hypothesis, to be described below, for it to work at all. It has the further advantage that it has an optional extension to compute a finite presentation for the subgroup H of G after the automatic coset system has been found. This second algorithm, together with the subgroup presentation facility, has been implemented and is available in kbmag. The theory, implementation details and performance statistics can also be found in [Holt and Hurt, 1997]. These algorithms provide an alternative method to that described in the previous subsection for solving the generalised word problem for H in G. The given word in w ∈ A^{∗} is reduced (in quadratic time, using the coset multiplier automata) to the unique word w′ in the language of the coset word-acceptor for which H\overline{w} = H\overline{w′}. Then w ∈ H if and only if w′ is the empty word. The two methods of solving the generalised word problem are to some extent complementary to each other, since there can exist L-quasiconvex subgroups that are not coset automatic and vice versa, although the two concepts are equivalent in word-hyperbolic groups. The additional hypothesis required for the algorithm developed by Hurt is the following generalisation of the fellow traveller condition. Let {W, M_{a}} be the shortlex automatic coset system for (G, H) that we are trying to compute. Then, if (w^{+}, x^{+}) ∈ L(M_{a}) for some a ∈ A, there exists h ∈ H such that wa =_{G} hx. The hypothesis is that there exists a constant k ≥ 0 such that for all such w, x, a and h, and all t ≥ 0, we have l_{A}(\overline{w(t)}^{−1}h\overline{x(t)}) ≤ k. In particular, taking t = 0, we get l_{A}(h) ≤ k, and so in all such equations, only a finite number of elements h occur.

One step in the algorithm is to define the states of the M_{a} as triples (s_{1}, s_{2}, g), as in the automatic group case, but now the initial states are (s_{0}, s_{0}, h), where s_{0} is the initial state of W, and h is one of the elements of H occurring in the above equations. So the M_{a} are in fact constructed initially as nondeterministic automata with multiple initial states,

If the hypothesis holds, then we shall say that G is strongly coset automatic with respect to H, and call {W, M_{a}} a strong automatic coset system for (G, H). It is proved in [Hurt, 1996] that word-hyperbolic groups are always strongly coset automatic with respect to their quasiconvex subgroups. It is easy to construct examples in which the hypothesis does not hold, by choosing H to be normal in G, in which case G coset automatic with respect to H is equivalent to G/H automatic, but we do not know of any example in which Core_{G}(H) = 1.

2 HNN extensions and an example

For the application to be described in this section, we need to strengthen the hypothesis defined at the end of the preceding section for strong automatic coset systems.

Definition 2.1 Let {W, M_{a}} be a strong automatic coset system for (G, H) with respect to the generating set X of G. Let Y be a finite set of generators of H, and let B = Y ∪ Y^{−1} . Then Y is said to be efficient with respect to {W, M_{a}} if, for any w, x ∈ L(W) and any b ∈ B, h ∈ H such that wb =_{G} hx, we have either h = 1 or h ∈ B.

We are not currently aware of any particular situations under which an efficient generating set could be shown to exist; it would be interesting to investigate this question. In specific examples of automatic coset systems that we have calculated with the programs, it is often possible to observe directly from the calculation that a particular Y is efficient. The concept is useful to us here, because it enables us to prove the following result about HNN extensions, which can then be applied to a specific example. Note that a rather different condition under which an HNN extension of an automatic group is asynchronously automatic has been proved by Shapiro in [Shapiro], and results of a similar nature for amalgamated free products are proved in [Baumslag et al, 1991].

Theorem 2.2 Let {W, M_{a}} be a strong automatic coset system for (G, H), let G = ⟨X | R⟩ be a finite presentation of G, and suppose that H has the efficient generating set Y . Suppose also that H is automatic, and let α be an automorphism of H such that α(Y) = Y .

Then the HNN extension

K = ⟨X, z | R, z^{−1}yz = α(y) (y ∈ Y)⟩

is asynchronously automatic.

Proof: Let T be a right transversal for H in G. Then by the normal form theorem for HNN extensions (see, for example, Theorem 2.1 (II), page 182 of [Lyndon, Shupp, 77]), each element of g ∈ K has a unique expression of the form

k = ht_{1}z^{n_{1}}t_{2}z^{n_{2}} … t_{r}z^{n_{r}},

where h ∈ H, t_{i} ∈ T, n_{i} ∈ ZZ , t_{i} ∉ H for i > 1 and n_{i} ≠ 0 for i < r.

We use this normal form in the natural manner to construct a regular language L_{K} for K on the alphabet A ∪ B ∪ {z^{±1}} where, as before, A = X ∪ X^{−1} and B = Y ∪ Y^{−1} . We are assuming that H is automatic, so we can use the language L_{H} of the word-acceptor from an associated automatic structure with alphabet B to obtain a word w_{h} ∈ L_{H} for the element h ∈ H in the normal form. For T we choose the image in G of L(W), and to represent t_{i}, we choose the unique word w_{i} ∈ L(W) with \overline{w_{i}} = t_{i}. This clearly yields a regular language L_{K} mapping bijectively onto K.

We now have to show how to construct the asynchronous multiplier automata M_{c} for c ∈ A ∪ B ∪ {z^{±1}}. Since this is fairly routine, we describe the construction in outline only. Suppose that u, v ∈ L_{K} and uc =_{K} v, and let the HNN normal form of k = \overline{u} be ht_{1}z^{n_{1}}t_{2}z^{n_{2}} … t_{r}z^{n_{r}}, as above. If c = z or z^{−1} , then the HNN normal form for kc in K is just ht_{1}z^{n_{1}} … t_{r}z^{n_{r}±1} , and it is easy to construct M_{c}. So suppose c ∈ A ∪ B. We shall suppose that n_{r} ≠ 0 and omit the details of the case n_{r} = 0, which are similar. There exist words c_{1} ∈ B^{∗} and c_{2} ∈ L(W) such that c =_{G} c_{1}c_{2} . Let l_{B}(c_{1}) = k. Then, from the assumptions that the generating set Y of H is efficient and that α(Y) = Y , it follows that the HNN normal form in K for kc is

kc = h′t′_{1}z^{n_{1}}t′_{2}z^{n_{2}} … t′_{r}z^{n_{r}} \overline{c_{2}},

where there are elements x_{i}, y_{i} ∈ H (1 ≤ i ≤ r), all having B -length at most k, such that z^{n_{r}} \overline{c_{1}} = y_{r}z^{n_{r}}, t_{i}y_{i} = x_{i}t′_{i} for 1 ≤ i ≤ r, z^{n_{i}}x_{i+1} = y_{i}z^{n_{i}} for 1 ≤ i < r, and hx_{1} = h′. Thus we have u = w_{h}w_{1}z^{n_{1}} … w_{r}z^{n_{r}} and v = w_{h′}w′_{1}z^{n_{1}} … w′_{r}z^{n_{r}}c_{2} , where w_{h}, w_{h′} ∈ L_{H} map onto h, h′ ∈ H, and w_{i}, w′_{i} ∈ L(W) map onto t_{i}, t′_{i} ∈ T for 1 ≤ i ≤ r.

The multiplier M_{c} proceeds by reading the words w_{h} and w_{h′} in parallel at the same rate, then the z^{n_{1}} together, then t_{1} and t′_{1} together, and so on. If either of w_{h} or w_{h′} is longer than the other, then it will wait at the end of the shorter one until the longer word has been read, and similarly for t_{i} and t′_{i}. (This explains why M_{c} needs to be asynchronous. Although |l(w_{h}) − l(w_{h′})| and |l(t_{i})−l(t′_{i})| are all bounded, there is no bound on r, and so one of the two tapes of the input of M_{c} may conceivably get indefinitely ahead of the other; indeed, we have verified that this really can happen in the example below.)

Of course, if either of the two words input to M_{c} is not in L_{K}, or if they do not both have the same pattern with respect to the occurrences of z, then they are rejected. Otherwise, if after t transitions, M_{c} has read ϕ(t) symbols from u and ψ(t) from v, then the element g(t) = \overline{u(ϕ(t))}^{−1}\overline{v(ψ(t))} of K is remembered as a function of the state of M_{c}. As in the synchronous case, it is sufficient to show that l(g(t)) is bounded.

There are four essentially different situations that occur as the words u, v are read.

(i) u(ϕ(t)) and v(ψ(t)) are prefixes of w_{h} and _{h′}, where |ϕ(t) − ψ(t)| is bounded. Then the the boundedness of l(g(t)) from the automaticity of H, and the fact that hx_{1} = h′ with l(x_{1}) ≤ k.

(ii) u(ϕ(t)) = w_{h}w_{1}z^{n_{1}} … w_{i}(s_{1}) for some i and some prefix w_{i}(s_{1}) of w_{i}, and v(ψ(t)) = w_{h′}w′_{1}z^{n_{1}} … w′_{i}(s_{2}), where |s_{1} − s_{2}| is bounded. Then g(t) = \overline{w_{i}(s_{1})}^{−1}x_{i}\overline{w′_{i}(s_{2})}, and its boundedness follows from the assumptions that l_{B}(x_{i}) ≤ k and that {W, M_{a}} is a strong automatic coset system for (G, H).

(iii) u(ϕ(t)) = w_{h}w_{1}z^{n_{1}} … w_{i}z^{m_{1}} for some i and some m_{1} ≤ n_{i}, and v(ψ(t)) = w_{h′}w′_{1}z^{n_{1}} … w′_{i}z^{m_{2}} , where |m_{1} − m_{2}| ≤ 1. Then g(t)z^{−m_{1}}y_{i}z^{m_{2}} , and its boundedness follows from l_{B}(y_{i}) ≤ k and the assumption that α(Y) = Y .

(iv) ϕ(t) > l(u) and ψ(t) ≥ l(v) − l(c_{2}). Then l(g(t)) ≤ l(c_{2}) which is clearly bounded.

This completes the proof of the theorem. □

As an application, we shall use this theorem together with the results of some machine computations that were done with kbmag, to prove that the group defined by the presentation

⟨ a, b, r, t, x, z |
xaxa = t, bxbx = t, bbtaa = t, a^{−1}br = ra^{−1}b, zt = tz, btaz = zbta ⟩

is asynchronously automatic.

This group, which we shall denote by K, was originally proposed by Mark Sapir as a possible building block in his attempts to construct groups with given Dehn functions. However, he later found a different approach to his problem, and so the example is no longer relevant from that viewpoint. He had hoped that it could be proven automatic, but the methods we have been discussing in this paper only appear to be sufficient to prove it asynchronously automatic.

The computer programs could make no progress with the presentation as given above, but matters improved after manipulating it a little. Eliminating t = bxbx, we get

⟨ a, b, r, x, z | xaxa = bxbx, bbxbxaa = xbx,
a^{−1}br = ra^{−1}b, zbxbx = bxbxz, bbxbxaz = zbbxbxa ⟩.

Now, putting u = xa and v = bx, and eliminating a = x^{−1}u = v^{−1}bu and x = b^{−1}v, we get

⟨ u, v, b, r, z | u^{2} = v^{2}, bvbuv^{−1}bu = b^{−1}v^{2},
u^{−1}b^{−1}vbr = ru^{−1}b^{−1}vb, zv^{2} = v^{2}z, bvbuz = zbvbu ⟩.

Finally, using u^{2} = v^{2} to simplify the second relation , we get

⟨ u, v, b, r, z | u^{2} = v^{2}, bvbu = b^{−1}ub^{−1}v,
u^{−1}b^{−1}vbr = ru^{−1}b^{−1}vb, zu^{2} = u^{2}z, zbvbu = bvbuz ⟩,

This is now visibly an HNN extension of the group

G = ⟨ u, v, b, r | u^{2} = v^{2}, bvbu = b^{−1}ub^{−1}v, u^{−1}b^{−1}vbr = ru^{−1}b^{−1}vb ⟩.

with respect to the subgroup H = ⟨ u^{2}, bvbu ⟩, where H is centralised by the new generator z. (In fact G is itself an HNN extension with extra generator r, but we shall not make use of that fact.)

Running the automatic coset system program from kbmag on the subgroup H of G verifies that G is strongly coset automatic with respect to H. (The coset word acceptor has 302 states, and the coset multiplers about 1400 states.) The presentation of H computed by the program proves that H is free of rank 2, and so it is certainly automatic. The programs can also be used to verify that the set Y = {u^{2}, bvbu^{−1}} is an efficient generating set for H. (Briefly, this is done by constructing the multiple initial state multiplier automata for the elements u^{2} and bvbu^{−1} . The elements of H corresponding to the initial states of these automata can then be inspected from the output, and it turns out that these are just the identity and elements of B = Y ∪ Y^{−1} .) We can now deduce from the theorem that Sapir’s group K is asynchronously automatic.

As a final remark about this example, it turns out (again using calculations carried out by kbmag) that the subgroup H is not L-quasiconvex, where L is the language of the word-acceptor of the shortlex automatic structure of G. The element (bub^{−1}v^{−1})^{n}(b^{−1}vbu^{−1})^{n} of L lies in H for all n ≥ 0, but the coset representative of (bub^{−1}v^{−1})^{n} in the language of the coset word acceptor is b^{2n}.

References

[Baumslag et al, 1991] G. Baumslag, S.M. Gersten, M. Shapiro and H. Short, “Automatic groups and amalgams” J. of Pure and Applied Algebra 76 (1991), 229-316.

[Cannon, 84] J.W. Cannon, “The combinatorial structure of cocompact discrete hyperbolic groups”, Geom. Dedicata 16 (1984), 123–148.

[Epstein et. al., 1992] David B. A. Epstein J.W. Cannon, D. F. Holt, S. Levy, M. S. Patterson and W. Thurston, Word Processing in Groups, Jones and Bartlett, 1992.

[Epstein, Holt, Rees, 1991] D. B. A. Epstein, D. F. Holt and S. E. Rees, “The use of Knuth-Bendix methods to solve the word problem in automatic groups”, J. Symbolic Computation 12 (1991), 397–414.

[Gersten and Short, 1994] S. M. Gersten, H. B. Short, “Rational Subgroups Of Biautomatic Groups”, Ann. Math. 134 (1991), 125–158.

[Holt, 1995] Derek F. Holt, “The Warwick automatic groups software”, in Geometrical and Computational Perspectives on Infinite Groups DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 25, ed. Gilbert Baumslag et. al., 1995, 69–82.

[Holt and Hurt, 1997] Derek F. Holt and Darren F. Hurt, “Computing automatic coset systems and subgroup presentations”, submitted to J. Symbolic Computation.

[Hopcroft and Ullman, 1979] John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.

[Hurt, 1996] Darren F. Hurt, 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, 1996.

[Kapovich, 1995] Ilya Kapovich, “Detecting quasiconvexity: algorithmic aspects”, in: Geometric and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 25, ed. Gilbert Baumslag et. al., 1995, 91–99.

[Lyndon, Shupp, 77] R.C. Lyndon and P.E. Shupp, Combinatorial Group Theory, Springer-Verlag, Berlin-Heidelberg-New York, 1977.

[McShane et. al., 1994] G. McShane, J. Parker and I. Redfern, “Drawing Limit Sets of Kleinian Groups Using Finite State Automata”, Experimental Mathematics 3 (1994), 153–172.

[Redfern, 1993] I. D. Redfern, Automatic Coset Systems, PhD Thesis, University of Warwick, 1993.

[Rees, 1997] Sarah Rees, “Hairdressing in groups: a survey of combings and formal languages”, these proceedings.

[Shapiro] , M. Shapiro, “Graph products of automatic groups”, unpublished.