Word-hyperbolic groups have real-time word problem

Derek F. Holt

1 Introduction

Let G = ⟨X⟩ be a finitely generated group, let A = X ∪ X^{−1}, and let A^{∗} be the set of all words in A. For u, v ∈ A^{∗}, we denote the image of u in G by \overline{u}. The word problem W_{X}(G) of G with respect to X is defined to be the set \{u ∈ A^{∗} | \overline{u} = 1\}.

We are interested in determining those groups G for which W_{X}(G) lies in some particular formal language class. It is straightforward to show that W_{X}(G) is a regular language if and only if G is finite. A much deeper result, due to Muller and Shupp [Muller and Shupp, 1983, Muller and Shupp, 1985], is that W_{X}(G) is deterministic context-free if and only if it is non-determinsitic context-free if and only if it has a free subgroup of finite index. In [Shapiro, 1994], Shapiro shows among other things that W_{X}(G) is deterministic contextsensitive when G is an automatic group.

In this paper we consider the class of deterministic real-time languages. For a finite alphabet A, a language L ⊆ A^{∗} is said to be real-time recognisable (or just real-time, for short), if it is recognisable by an n-tape deterministic real-time Turing machine, for some integer n ≥ 0. Such a machine consists of a tape containing the input word with the tape-head initially at the beginning of the word, together with n work tapes, which are two way infinite tapes and initially empty. It has a finite number of states, including a unique initial state and a collection of accepting states. On every transition it must read one input symbol and the input tape-head then moves one place to the right. At the same time, each of the work tapes is allowed to write one symbol in its current location, and then move at most one square to the left or right, depending on the state, the input symbol, and the symbols currently being scanned by the work tapes. The word is accepted if the machine is in an accepting state on reaching the end of input. See [Rabin, 1963] or [Rosenberg, 1967] for basic information on real-time languages.

Consider an apparently more general class of languages, in which, for some fixed positive integer m, the work tapes are allowed to perform up to m operations of writing and moving for each input symbol read. We call such a Turing machine m-real-time. By distributing the contents of each work tape evenly across m new work tapes, it is clear that we can construct a real-time Turing machine with nm tapes that recognises the same language. Hence such languages are in fact themselves real-time. So, informally, a language is real-time if and only it can recognised by a computer that reads its input at a constant rate, and stops at the end of its input.

It is known (see, for example, Theorem 2.18 of [Alonso et al, 1991]) that the word problem in word-hyperbolic groups is recognisable in linear time. The main result of this paper (Theorem 3.1) is that W_{X}(G) is a real-time language for this class of groups.

If X and Y are two generating sets for a group G and if W_{X}(G) is realtime then so is W_{Y} (G). To see this, write each generator in Y ∪ Y^{−1} as a word in A^{∗} = (X ∪ X^{−1})^{∗}, and let s be the maximal length of these words. Then we can replace an m-real-time Turing machine for X by an ms-real-time machine for Y, which simply interprets each input letter in Y ∪ Y^{−1} as the corresponding word in A^{∗}. Thus we can talk about the class RG of groups with real-time word problem.

It is then straightforward to show that RG is closed under direct products (since the direct factors can be processed in parallel by separate sets of work tapes), and under finite index subgroups and supergroups. Furthermore, any finitely generated subgroup of a group in RG also lies in RG, because we can simply extend the finite generating set of the subgroup to one of the whole group, and then use the corresponding real-time Turing machine for the whole group.

By putting these ideas together, we get

Theorem 1.1 Suppose that the group H has a finite index subgroup which is a direct product of word-hyperbolic groups. Then any finitely generated subgroup of H has real-time word problem.

It would be intersting to know whether there are any other groups in RG.

2 Word-hyperbolic groups

In this section, we shall summarise the definition and basic properties of word-hyperbolic groups, and prove a result about them that we shall need in the proof of the main theorem. We shall use the multi-author article [Alonso et al, 1991] as our basic reference for word-hyperbolic groups.

Let G = ⟨X⟩ as before, and let Γ = Γ_{X}(G) be the Cayley graph of G with respect to X. We make Γ into a metric space in the standard manner, by letting all edges have unit length, and defining the distance d(x, y) between any two points of Γ to be the minimum length of paths connecting them. (This includes both the vertices, and points on the edges of Γ.) This makes Γ into a geodesic space, which means that for any x, y ∈ Γ there exist geodesics (i.e. shortest paths) between x and y. A geodesic triangle in Γ consists of three not necessarily distinct points x, y, z together with three geodesic paths u, v, w joining yz, zx and xy, respectively. For g ∈ G, l(g) will denote the length of a geodesic path from the basepoint 1 to g.

There are several equivalent definitions of word-hyperbolicity. The most convenient for us is the following. Let Δ be a geodesic triangle in Γ with vertices x, y, z and edges u, v, w as above. (Hence l(u) = d(y, z), etc.) Let r(x) = (l(v) + l(w) − l(u))/2 and define r(y), r(z) correspondingly. Then r(y) + r(z) = l(u), so any point p on u satisfies either d(p, y) ≤ r(y) or d(p, z) ≤ r(z), and similarly for v and w. Let δ ∈ IR_{+}. Then we say that Δ is δ-thin if, for any r ∈ IR with 0 ≤ r ≤ r(x), the points p and q on v and w with d(p, x) = d(q, x) = r satisfy d(p, q) ≤ δ, and similarly for the points within distance r(y), r(z) of y and z. The group G is called word-hyperbolic if there exists a δ such that all geodesic triangles in Γ are δ-thin. (It turns out that this definition is independent of the generating set X of G, although the minimal value of δ does depend on X.)

Since we can always increase δ, we may assume that δ ∈ ZZ. For the remainder of this article, we shall assume that G = ⟨X⟩ is word-hyperbolic, and that all geodesic triangles are δ-thin for some fixed positive integer δ. Let W = W_{X}(G).

A presentation G = ⟨X | R⟩ of G is called a Dehn presentation if, for any word u ∈ W, u can be shortened within W by using one of the relators v ∈ R. More precisely, there exists v = v_{1}v_{2} ∈ R with l(v_{1}) > l(v_{2}) such that v_{1} is a subword of u, and hence u can be shortened by substituting v_{2}^{−1} for v_{1} in u, and the resulting word will still lie in W. This means of course that u can be reduced to the empty word by repeated substitutions of this kind.

Theorem 2.12 of [Alonso et al, 1991] states that, under our assumption of δ-thinness of geodesic triangles, the set of relators R = {u ∈ W | l(u) ≤ 8δ} is a (finite) set of defining relators of G and G = ⟨X | R⟩ is a Dehn presentation.

For k ∈ IR_{+}, a path p in Γ is called a k-local geodesic, if any subpath of p of length at most k is a geodesic. Thus, if k = 4δ, then a word that does not contain more than half of any relator in R must be a k-local geodesic.

In general, if u is a directed path in Γ and x and y lie on u with x coming before y on u, then u_{x,y} will denote the part of u between x and y. We shall need the following result.

Proposition 2.1 Let k = 4δ, let g ∈ G, and let u be a k-local geodesic from 1 to g with l(u) > 1. then l(g) ≥ l(u)/2 + 1.

The proof uses Lemma 2.14 of [Alonso et al, 1991], which we re-state here for reference.

Lemma 2.2 Let k, g, u be as in the proposition, and let v be a geodesic path from 1 to g. Assume that l(u) ≥ 2δ and l(v) ≥ 2δ. Let s and t be the points on u and v at distance 2δ from g. Then d(s, t) ≤ δ.

Proof of proposition: (The reader will probably need to draw some diagrams to help with the reading of this proof!) The proof is by induction on l(u). If l(u) ≤ k then u is a geodesic and the result is clear (note that k ≥ 4), so we may assume that l(u) > k. Let v be a geodesic path from 1 to g (so l(v) = l(g)).

Suppose first that l(v) < 2δ. Let p be the point on u at distance 2δ from g, and let w be a geodesic path from 1 to p. Since l(u) > k, we certainly have l(u_{1,p}) > 2δ. If l(u_{1,p}) ≤ 4δ then u_{1,p} is a geodesic and so l(w) = l(u) > 2δ, and otherwise we have l(w) > 2δ by inductive hypothesis. Thus l(w) > 2δ in either case. Hence, in the geodesic triangle with vertices 1, p, g and edges w, u_{p,g}, v, we have (l(u_{p,g}) + l(w) − l(v))/2 > δ. So, by the definition of δ-thin triangles, there exists ϵ ∈ IR with 0 < ϵ < δ such that, if q and r are the points on w and u_{p,g} at distance δ + ϵ from p, then d(q, r) ≤ δ. Now let s and t be the points on u_{1,p} and w at distance 2δ from p. By Lemma 2.2 applied with p, u_{1,p}, w in place of g, u, v, we have d(s, t) ≤ δ. Now u_{s,r} has length 3δ + ϵ < 4δ and so it is a geodesic by hypothesis. But d(s, r) ≤ d(s, t) + d(t, q) + d(q, r) ≤ 3δ − ϵ, which is a contradiction.

Thus we must have l(v) ≥ 2δ. As in the lemma, let s and t be the points on u and v at distance 2δ from g. Then d(s, t) ≤ δ by Lemma 2.2. Let w be a geodesic path from 1 to s. Now we have l(u_{1,s}) > 2δ > 1, so we can apply our inductive hypothesis to u_{1,s} and we get l(u_{1,s}) = l(u) − 2δ ≤ 2l(w) − 2. Also, l(w) ≤ l(v_{1,t})+d(s, t) ≤ l(v)−δ, and combining these inequalities yields l(u) ≤ 2l(v) − 2, as claimed. □

3 Real-time recognition

In this section, we prove the main result of the article.

Theorem 3.1 Let G = ⟨X⟩ be a word-hyperbolic group in which the triangles in the Cayley graph Γ = Γ_{X}(G) are δ-thin for some positive integer δ. Then the word problem W = W_{X}(G) of G is recognisable by a (96δ − 2)-real-time Turing machine with four work tapes.

Proof: We first describe the operation of the Turing machine M. This is essentially the same as the machines described in [Domanski and Anshel, 1985] or on pages 33–35 of [Alonso et al, 1991], which require just two tapes used as stacks. The problem is that we have to continue reading symbols from the input tape while symbols are being transferred from one stack to another, and we use the other two work tapes to queue this input.

As in the previous section, let R be the set of all relators of G of length at most 2k, where k = 4δ, so that ⟨X | R⟩ is a Dehn presentation of G. We include the inverse relators xx^{−1} in R for all x ∈ A.

We call the input tape T_{0}, and the work tapes T_{1}, T_{2}, T_{3}, T_{4}. At any time during the processing, they will each contain a word w_{i} ∈ A^{∗} (0 ≤ i ≤ 4). The input word w_{0} is of course scanned sequentially, and does not change. On the work tapes, the tape head always points either at the last symbol of w_{i} or at the empty space immediately to its right.

The contents w_{1} of T_{1} will never be allowed to contain a substring equal to more than half of a relator in R. (Whenever this is about to happen, we will make a substitution to prevent it.) Thus w_{1} will always be a k-local geodesic, and in fact it will be equal in G to all or to a prefix of the input word that has been read so far. The tape T_{2} is used to carry out substitutions when reducing the input word, and T_{3} and T_{4} are used to store input read from T_{0} while these substitutions are being carried out.

At any time, the machine M is one of two modes, which we shall call reading mode and substitution mode. The word w_{0} is accepted if and only if after scanning it completely M is in reading mode, and w_{1} is empty.

In reading mode, w_{2}, w_{3} and w_{4} are all empty, and w_{1} is a k-local geodesic equal in G to the prefix of w_{0} that has been read so far. The tape head of T_{1} points at the next square to the right of w_{1}, ready to write the next symbol. The last k symbols of w_{1} are remembered as part of the state of M, and all of the relators in R are known to M. Thus, on reading the next symbol, M knows whether or not it has just read more than half of some relator in R. If not, then the new symbol is simply transferred to the end of w_{1}, which remains a k-local geodesic. If it has read more than half of some v ∈ R, then if l(v) ≤ 2, the tape-head of T_{1} either remains where it is (if l(v) = 1), or moves one square left and deletes the symbol it finds there (if l(v) = 2), and M remains in reading mode. Otherwise (with one exception) M moves into substitution mode. Since we do not want to go into substitution mode when l(w_{1}) = 1, we make the additional exception that if w_{1} = a ∈ A, and the next input symbol is b, where there is a relator abc ∈ R, then we move the tape head of T_{1} back, write c^{−1} in place of a, move T_{1} forward again, and remain in reading mode.

The processing in substitution mode splits up into a number of phases ϕ_{1}, ϕ_{2}, …, ϕ_{r}. During phase ϕ_{i}, the symbols read from T_{0} are transferred to T_{3} or T_{4}, when i is odd or even, respectively. At the beginning of each phase ϕ_{i} with i > 1, w_{2} is empty, and w_{1} is a k-local geodesic equal in G to the prefix of the input word w_{0} read so far, up to, but not including, the queued input on T_{3} or T_{4}. This queued input needs to be reversed, and when i > 1, phase ϕ_{i} begins by transferring it to T_{2}, which has the desired effect of reversing it. The first phase ϕ_{1}, on the other hand, begins with a substitution, which we shall describe shortly. All of the operations during substitution mode, including this reversing process, take place at 96δ − 2 times the speed at which input is read from w_{0}. We shall assume that an input symbol is always read right at the beginning of each phase, even if it is not immediately due after the end of the previous phase.

After the initial substitution or transferring of queued input to T_{2}, phase ϕ_{i} continues by transferring the symbols in w_{2} to the end of w_{1}, and carrying out substitutions when required. The word w_{2} is of course being transferred in reverse order to T_{1}, and the phase ends when w_{2} is empty. A substitution takes place whenever the next symbol in line to be transferred to the end of w_{1} would cause w_{1} to end with more than half of a relator in v ∈ R, with l(v) > 2.

Suppose v = v_{1}v_{2}, where we want to substitute v_{2}^{−1} for an occurrence of v_{1} in the input word. We first adjoin v_{2}^{−1} in reverse order to the end of w_{2}, and simultaneously move the input head of T_{1} backwards, deleting v_{1} as it moves. Since l(v_{1}) ≤ k + 1 and l(v_{2}) ≤ k − 1, this requires a maximum of k moves of the tape heads of T_{1} and T_{2} (in parallel). (We get k rather than k + 1 because we never actually wrote the (k + 1)-st symbol of v_{1} on T_{1}.) We then transfer k further symbols (or fewer, if we reach the beginning of w_{1}) from the end of w_{1} to the end of w_{2}, reversing the order as we do it. We can then go back to transferring symbols from T_{2} to T_{1}. Of course, this means that the k extra symbols are immediately moved back from where they have just come, but this is necessary in order to locate any further substitutions induced by replacing v_{1} by v_{2}^{−1}. Since l(v_{2}) ≤ k − 1 the substitution writes a maximum of 2k − 1 symbols on to T_{2}, which later have to be transferred to T_{1}. Thus the total cost of each substitution is at most 4k − 1 tape moves on the work tapes.

If, after finishing phase ϕ_{i}, there is at most one queued input symbol on T_{3} or T_{4} and M is not due to read a new input symbol immediately (before doing any further transfers on the work tapes), then M goes back into reading mode and uses one of the remaining available word tape transfers to read the queued symbol. (We need to do this, or we would never get back into reading mode at all! Of course, this may send M immediately back into substitution mode.)

If, at any stage during substitution mode we reach the end of input, then the word is rejected. It is clear that M operates correctly in all other respects. In other words, to complete the proof of Theorem 1, we need only show that if w_{0} does lie in W, then we cannot reach end of input during substitution mode.

For this purpose, let c = 4k − 1 = 16δ − 1 be the maximum number of work tape moves needed to process each substitution, let σ = 6c + 4 be the speed of work tape operations (relative to the speed of reading w_{0}) and let τ = σ/2. Suppose that during phase ϕ_{i}, s_{i} substitutions are carried out, and r_{i} input symbols are read and queued. Let l be the length of w_{1} when we go into substitution mode. Then from the definition of M, we must have l > 1. Finally, let l_{0} = l(\overline{w_{1}}) when we go into substitution mode, and let l_{i} = l(\overline{w_{1}}) at the end of phase ϕ_{i}.

Since w_{1} is always a k-local geodesic, it follows from Proposition 2.1 that l_{0} ≥ l/2 + 1. After phase ϕ_{i}, a total of 1 + r_{1} + … r_{i−1} further generators have been moved onto the end of w_{1}, and so we have l_{i} ≥ l/2 − ρ_{i−1}, where ρ_{i} = r_{1} + … + r_{i}. To complete the proof of the theorem, it clearly suffices to show that l_{i} > 0 for all i or, equivalently, that ρ_{i} < l/2.

We prove this by induction on i, and by setting ρ_{0} = 0, we can start the induction at i = 0. So assume that, for some i, we know that ρ_{i−1} < l/2. Then, after phase ϕ_{i}, the word w_{1} on T_{1} is a reduction of the original w_{1} of length l, followed by 1 + ρ_{i−1} further generators. By inductive assumption, this reduced word has length at least 1, and since every substitution reduces the length of the word by at least 1, we must have

(∗) s_{1} + … s_{i} ≤ l + ρ_{i−1}.

Now each substitution has a cost of at most c work tape moves, and transferring the r_{i−1} symbols from T_{3} or T_{4} to T_{2} and then to T_{1} in phase ϕ_{i} has a cost of 2r_{i−1} work tape moves. We therefore have r_{i} < (cs_{i}+2r_{i−1})/σ+1 (where the +1 arises from the fact that r_{i} is an integer, and we read an input symbol right at the beginning of each phase). Thus, we have

(∗∗) r_{i} ≤ (cs_{i} + 2r_{i−1})/τ

except possibly when r_{i} = 1, and we do not have to read a new symbol from T_{0} immediately following phase ϕ_{i}. But in that situation, we go immediately back into reading mode on completing ϕ_{i}, so we can effectively assume that (∗∗) holds in all cases.

Now summing (∗∗) over i and using (∗), we get the recurrence relation ρ_{i} < (cl + (c + 2)ρ_{i−1})/τ, which implies

ρ_{i} < cl(1 + (c + 2)/τ + … + ((c + 2)/τ)^{i−1})/τ < cl/(τ − c − 2) = l/2,

since τ = 3c + 2. This completes the induction, and the proof of the theorem.

References

[Alonso et al, 1991] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro and H. Short, “Notes on word-hyperbolic groups”, in E. Ghys, A. Haefliger and A. Verjovsky, eds., “Proceedings of the Conference “Group Theory from a Geometric Viewpoint” held in I.C.T.P., Trieste, March 1990, World Scientific, Singapore, 1991.

[Muller and Shupp, 1983] D. E. Muller and P. E. Shupp, “Groups, the theory of ends, and context-free languages”, J. Comp. System Sci. 26 (1983), 295–310.

[Muller and Shupp, 1985] D. E. Muller and P. E. Shupp, “The theory of ends, pushdown automata, and second-order logic”, Theoretical Comp. Sci. 37 (1985), 51–75.

[Rabin, 1963] Michael O. Rabin, “Real time computation”, Israel J. Math 1 (1963) 203–211.

[Domanski and Anshel, 1985] Domanski, B.; Anshel, M. “The complexity of Dehn’s algorithm for word problems in groups”, J. Algorithms 6 (1985), 543–549.

[Rosenberg, 1967] A. Rosenberg, “Real-Time Definable Languages”, J. Assoc. Comput. Mach. 14 (1967) 645–662.

[Shapiro, 1994] , “A note on context-sensitive languages and word problems” International J. of Alg. and Comput. 4 (1994), 493–497.