Groups that do and do not have growing context-sensitive word problem

Derek F. Holt, Sarah Rees and Michael Shapiro

July 23, 2008

Abstract

We prove that a group has word problem that is a growing contextsensitive language precisely if its word problem can be solved using a non-deterministic Cannon’s algorithm (the deterministic algorithms being defined by Goodman and Shapiro in [6]). We generalise results of [6] to find many examples of groups not admitting non-deterministic Cannon’s algorithms. This adds to the examples of Kambites and Otto in [7] of groups separating context-sensitive and growing contextsensitive word problems, and provides a new language-theoretic separation result.

1 Introduction

The purpose of this note is to extend the results in Sections 6 and 7 of [6]. That article described a linear time algorithm, which we call Cannon’s algorithm, which generalised Dehn’s algorithm for solving the word problem of a word-hyperbolic group. Many examples of groups that possess such an algorithm were provided, alongside proofs that various other groups do not.

The Cannon’s algorithms described in [6] are deterministic, but there was some brief discussion at the end of Section 1.3 of [6] of non-deterministic generalisations, and the close connections between groups with non-deterministic Cannon’s algorithms and those with growing context-sensitive word problem. (Non-deterministic Cannon’s algorithms and growing context-sensitive languages are defined in Section 2 below.) It was clear that an appropriate modification of the theorems in Section 7 of [6] should imply that various groups, including direct products F_{m} × F_{n} of free groups with m > 1 and n ≥ 1 and other examples mentioned below, had word problems that were context-sensitive but not growing context-sensitive. We provide that modification in this paper.

Our examples are not the first to separate context-sensitive and growing context-sensitive word problem. For F_{m} × F_{n} with m, n > 1 has recently been proved context-sensitive but not growing context-sensitive by Kambites and Otto in [7], using somewhat different methods; they failed to resolve this question for F_{m} × F_{1} = F_{m} × ℤ with m > 1, which is now covered by our result. And our result has further application, since, according to [7, Section 7], the fact that F_{2} × F_{1} does not have growing context sensitive word problem implies that the class of growing context-sensitive languages is properly contained in the language class L(OW−auxPDA(poly, log)). We refer the reader to [7] for a definition of this class, and for citations.

In Section 2 of this article, we provide definitions of the classes of contextsensitive and growing context-sensitive languages, and of non-deterministic Cannon’s algorithms. We then show in Theorem 3 that the set of formal languages defined by non-deterministic Cannon’s algorithms is the same as the set of growing context-sensitive languages that contain the empty word. Hence the word problem for a group can be solved using a non-deterministic Cannon’s algorithm precisely if it is a growing context-sensitive language.

Two different versions of Cannon’s algorithms, known as incremental and non-incremental, are defined in [6], and both of these are deterministic. In [6, Proposition 2.3] it is shown that the language of an incremental Cannon’s algorithm is also the language of a non-incremental Cannon’s algorithm. In [7, Theorem 3.7], it is shown that the class of languages defined by non-incremental Cannon’s algorithms is exactly the class of Church-Rosser languages. It is pointed out in [7] (following Theorems 2.5 and 2.6) that the class of Church-Rosser languages is contained in the class of growing context-sensitive languages. It follows that every group with an incremental or non-incremental Cannon’s algorithm also has a non-deterministic Cannon’s algorithm. (This is not obvious, because replacing a deterministic algorithm with a non-deterministic algorithm with the same reduction rules could conceivably result in extra words reducing to the empty word.) In particular, all of the examples shown in [6] to have (incremental) Cannon’s algorithms have growing context-sensitive word problem.

It follows from the (known) fact that the class of growing context-sensitive languages is closed under inverse homomorphism that the property of a finitely generated group having growing context-sensitive word problem does not depend on the choice of finite semigroup generating set of G. Some other closure properties of the class of growing context-sensitive groups are mentioned at the end of Section 2.

In Section 3, we generalise Theorems 7.1 and 7.2 of [6] to prove that there does not exist a non-deterministic Cannon’s algorithm for a group satisfying the hypotheses of those theorems; that is, we prove the following.

Theorem 1 Let G be a group that is generated as a semigroup by the finite set G, and suppose that, for each n ≥ 0, there are sets S_{1}(n), S_{2}(n) in G satisfying

(1) each element of S_{i}(n) can be represented by a word over G of length at most n,

(2) there are constants α_{0} > 0, α_{1} > 1 such that for infinitely many n, |S_{i}(n)| ≥ α_{0}α_{1}^{n}, and

(3) each element of S_{1}(n) commutes with each element of S_{2}(n).

Then G cannot have a non-deterministic Cannon’s algorithm over any finite semigroup generating set.

Theorem 2 Let G be a group that is generated as a semigroup by the finite set G, and suppose that, for each n ≥ 0, there are sets S_{1}(n), S_{2}(n) in G satisfying

(1) each element of S_{i}(n) can be represented by a word over G of length at most n,

(2) there are constants α_{0} > 0, α_{1} > 1, α_{2} > 0 such that for all sufficiently large n, |S_{1}(n)| ≥ α_{0}α_{1}^{n} and |S_{2}(n)| ≥ α_{2}n, and

(3) each element of S_{1}(n) commutes with each element of S_{2}(n).

Then G cannot have a non-deterministic Cannon’s algorithm over any finite semigroup generating set.

As a corollary we see that a group G satisfying the conditions of Theorem 1 or 2 cannot have word problem that is a growing context-sensitive language.

Theorems 7.1 and 7.2 of [6] are followed by a number of further theorems and corollaries (numbered 7.3 – 7.12), which provide a wide variety of examples of groups that satisfy the criteria of Theorems 7.1 or 7.2 and hence have no deterministic Cannon’s algorithm. These examples include F_{2} × ℤ, braid groups on three or more strands, Thompson’s group F, Baumslag-Solitar groups ⟨a, t, | ta^{p}t^{−1} = a^{q}⟩ with p ≠ ±q, and the fundamental groups of various types of closed 3-manifolds. We can conclude immediately from our Theorems 1 or 2 that none of these examples have non-deterministic Cannon’s algorithms or growing context sensitive word problems.

Note that a number of these examples, such as F_{2} × ℤ and braid groups [5], are known to be automatic and hence to have context-sensitive word problem [8].

On the other hand the article [6] gives a wealth of examples of groups that do have Cannon’s algorithms, and hence have growing context-sensitive word problems. These include word-hyperbolic, nilpotent and many relatively hyperbolic groups.

We would like to acknowledge the contribution of Oliver Goodman, many of whose ideas are visible in the arguments of this paper.

2 Growing context-sensitive languages and nondeterministic Cannon’s algorithms

We start with the necessary definitions. A phrase-structured grammar is a quadruple (N, X, σ, P), where N and X are finite sets known respectively as the non-terminals and terminals, σ ∈ N is the start symbol, and P is the set of productions. The productions have the form u → v with u ∈ 𝔸^{+} \ X^{+} and v ∈ 𝔸^{∗}, where 𝔸 := N ∪ X.

The grammar is context-sensitive if |u| ≤ |v| for all productions u → v. It is growing context-sensitive if, in addition, for all productions u → v, σ does not occur in v and either u = σ or |u| < |v|.

As is customary, to allow for the possibility of having the empty word ϵ in a (growing) context-sensitive language (defined below), we also allow there to be a production σ → ϵ, provided that σ does not occur in the right hand side of any production.

For u, v ∈ A^{∗}, we write u →^{∗} v if we can derive v from u by applying a finite sequence of productions to the substrings of u. The language of the grammar is the set of words w ∈ X^{∗} with σ →^{∗} w. A growing context-sensitive language (GCSL) is a language defined by a growing context-sensitive grammar (GCSG).

There is some information on this class of languages in [1]. Other possibly relevant references are [3] and [4]. It is proved in [2] that the GCSLs form an abstract family of languages which implies, in particular, that they are closed under inverse homomorphisms and intersection with regular languages. This in turn implies that the property of the word problem of a finitely generated group G being a GCSL is independent of the choice of finite generating set for G, and that this property is inherited by finitely generated subgroups of G.

A non-deterministic Cannon’s Algorithm (NCA) is defined to be a triple (X, 𝔸, R), where X ⊆ 𝔸 are finite alphabets, and R is a set of rules of the form v → u with u, v ∈ A^{∗} and |v| > |u|. For a non-deterministic Cannon’s Algorithm, we drop the restriction imposed in [6] for the deterministic case that no two rules are allowed to have the same left hand sides. We allow some of the rules v → u to be anchored on the left, on the right, or on both sides, which means that they can only be applied to the indicated subword v in words of the form vw, wv, and v, respectively, for words w ∈ 𝔸^{∗}. The language of the NCA is defined to be the set of words w ∈ X^{∗} with w →^{∗} ϵ.

The similarity between GCSGs and NCAs is obvious – replacing the productions u → v of the former by rules v → u of the latter almost provides a correspondence between them. Apart from the reversed direction of the derivations, there are two principal differences. The first is that in a GCSG the derivations start with σ, whereas with a NCA the significant chains of substitutions end with the empty word ϵ. The second is that NCAs may have anchored rules, whereas the definition of a GCSG does not allow for the possibility of anchored productions.

These differences turn out not to be critical, and in this section we shall prove the following result.

Theorem 3 Let L be a language over a finite alphabet X with ϵ ∈ L. Then L is growing context-sensitive if and only it is defined by a non-deterministic Cannon’s Algorithm.

To handle the anchoring problem, let us define an extended GCSG to be one in which some of the productions u → v may be left anchored, right anchored, or left and right anchored, which means that they can only be applied to the indicated subword u in words of the form uw, wu or u, respectively, for words w ∈ 𝔸^{∗}. Note that we do not allow productions with u = σ to be anchored, and neither is there any need to do so, because they can only be used as the initial productions in derivations of words in the language.

The following proposition tells us that allowing anchored productions does not augment the class of GCSLs.

Proposition 4 If a language L ⊆ X^{∗} is the language defined by an extended GCSG, then L is also defined by a standard GCSG.

Proof: Suppose L is defined by the extended GCSG (N, X, σ, P) and let 𝔸 := N ∪ X.

We first replace the grammar by one in which u ∈ N^{+} for all productions u → v. In other words, no terminal occurs in the left hand side of any production.

To do this, we introduce a new set X̃ of non-terminals in one-one correspondence with X. For a word w ∈ A^{∗}, let w̃ be the result of replacing every terminal x in w by its corresponding non-terminal x̃. We replace each production u → v by a collection of productions of the form ũ → v′, where v′ ranges over all possible words obtained by replacing some of the terminals x that occur in v by their corresponding non-terminals x̃. This achieves the desired effect without altering the language of the grammar.

After making that change, we introduce three new sets of non-terminals, ^N, N^and ^N^, each in one-one correspondence with N. For a word w ∈ 𝔸^{+}, we define ^w as follows. Let w = xv with x ∈ 𝔸, v ∈ 𝔸^{∗}. If x ∈ N \ {σ}, then we set ^w = (^x)v, where ^x is the symbol in ^N that corresponds to x. Otherwise, if x ∈ X ∪ {σ}, we set ^w = w. We define w^and ^w^ similarly. (Note that the new symbols in ^N^are only needed here when |w| = 1.)

Now each production of the grammar of the form σ → v is replaced by σ → ^v^. For each non-anchored production u → v with u ≠ σ, we keep this production and also introduce new (non-anchored) productions ^u → ^v, u^→ v^, and ^u^→ ^v^. Each left anchored production u → v is replaced by the two productions ^u → ^v and ^u^→ ^v^, and similarly for right anchored productions. A left and right anchored production u → v is replaced by the single production ^u^→ ^v^.

The effect of these changes is that the symbols in ^N can only occur as the leftmost symbol of a word in a derivation starting from σ and, similarly, those in N^can only occur as the rightmost symbol. Conversely, in any word w ≠ σ that occurs in such a derivation, if the leftmost symbol of w is a non-terminal then it lies in ^N, and similarly for the rightmost symbol. The symbols in ^N^can only arise as the result of an initial derivation of the form σ → ^v^with |v| = 1. So the productions that were initially anchored can now only be applied in a production at the left or right hand side of the word, and so we have effectively replaced anchored productions by nonanchored ones that behave in the same way. Hence the language defined by this grammar is the same as that defined by the original grammar. □

A natural question that arises at this point is whether anchored rules in a NCA can be dispensed with in a similar fashion. The following simple example shows that this is not possible. Let X = {x}. Then L := {x} is the language of the NCA with 𝔸 = X and the single rule x → ϵ that is left and right anchored. A NCA without anchored rules recognising L would have to contain the rule x → ϵ, but then L would also contain x^{n} for all n > 0. However, the proof of Theorem 3 that follows shows that we can make do with non-anchored rules together with left and right anchored rules of the form v → ϵ.

Proof of Theorem 3: Suppose that L ⊆ X^{∗} is the language defined by the GCSG (N, X, σ, P) and that ϵ ∈ L. We define a NCA (X, 𝔸, R) with 𝔸 = X ∪ N \ {σ}, where the rules R are derived from the productions P as follows. Productions of the form σ → v with v ≠ ϵ are replaced by rules v → ϵ anchored on both sides. All productions u → v with u ≠ σ are replaced by the rule v → u. It is easily seen that derivations of words in L using P correspond exactly, but in reverse order, to reductions of words to ϵ using R, so the language of (X, 𝔸, R) is equal to L.

Conversely, suppose that L is the language of the NCA (X, 𝔸, R). Then we define an extended GCSG (N, X, σ, P) as follows. We introduce σ as a new symbol and put N := (𝔸 \ X) ∪ X̃ ∪ {σ} where X̃ is a set of non-terminals in one-one correspondence with X. Given a rule, v → u ∈ R, we will want to consider a collection of productions ũ → ṽ, where ũ and ṽ range over all words gotten by replacing X letters with X̃ letters subject only to the requirement that ũ ∉ X^{∗}. We refer to this collection of rules by \overline{u → v}.

We produce the set of productions P as follows. We make σ → ϵ a production of P, and the remaining productions are derived from the rules R as follows. Rules of the form v → u with u ≠ ϵ are replaced by productions \overline{u → v}, where anchored rules are replaced by correspondingly anchored productions.

For a non-anchored rule v → ϵ, we introduce non-anchored productions \overline{x → xv} and \overline{x → vx} for all x ∈ 𝔸, together with the productions \overline{σ → v}. For a left-anchored rule v → ϵ, we introduce left-anchored productions \overline{x → vx} for all x ∈ 𝔸 together with the productions \overline{σ → v}. Right-anchored rules of this form are handled similarly. Finally, for a left and right anchored rule v → ϵ, we introduce the productions \overline{σ → v}.

By choosing the correct version of these rules at each step (i.e., including the correct set of X̃ letters), each reduction to ϵ using R can be turned into a derivation using P. Similarly, each derivation using P determines a corresponding reduction using R. Thus the language of this grammar is equal to L and, by Proposition 4, we may replace it by a standard GCSG with language L. □

We saw earlier that the property of a group G having growing context word problem is independent of the chosen semigroup generating set of G, and is closed under passing to finitely generated subgroups. It is proved in [6, Theorems 2.11,2.13] that the property of G having a deterministic Cannon’s Algorithm is preserved under taking free products and under passing to overgroups of finite index. These proofs work equally well for non-deterministic Cannon’s algorithms, and so having growing context sensitive word problem is also closed under these operations. But we shall see in the next section that F_{2} × F_{2} does not have growing context sensitive word problem. Hence we see that the class of groups with growing context sensitive word problem is not closed under direct products.

3 Groups without non-deterministic Cannon’s algorithm

This section is devoted to the proofs of Theorems 1 and 2, which extend Theorems 7.1 and 7.2 of [6].

Our proofs of Theorems 1 and 2 are modifications of the original proofs in [6]. We assume the reader is familiar with that work and has it available for reference. We will show how to modify those arguments so that they can be extended to the non-deterministic case.

The argument of [6] starts by examining the reduction of a word w_{0} to w_{n} by repeated applications of the length-reducing rules, which are referred to as the history to time n of w_{0}. These words are then displayed laid out in successive rows in a rectangle. The place in each row where a rule is to be applied is marked with a substitution line. The letters resulting from the substitution occupy the space on the next row below this line and are each given equal width. The authors introduce the notion of a splitting path which is a decomposition of such a rectangle into a right and left piece, together with combinatorial information on that decomposition. Two splitting paths are defined to be equivalent if they are labelled with the same combinatorial information. Given two histories, v_{0}, …, v_{r} and w_{0}, …, w_{s}, if these have equivalent splitting paths, then the left half of the first rectangle can be spliced together with the right half of the second rectangle in a way which produces the history of the reduction starting with v_{0}^{−}w_{0}^{+} and ending with v_{r}^{−}w_{s}^{+}. (The super-scripts denote the left and right halves of these words.) The combinatorics of splitting paths are such that in certain key situations, exponentially many cases are forced to share only polynomially many equivalence classes of splitting paths. The hypotheses of Theorems 7.1 and 7.2 of [6] assure a supply of exponentially many commutators, each of which must reduce to the empty word. One shows that two of these can be spliced together to produce a word which does not represent the identity, but which also reduces to the empty word. This is a contradiction.

Essentially we are able to work with the same definitions of histories, splitting paths and their details, and equivalence of splitting paths as [6], but need to introduce a definition of equivalence of histories, and re-word and re-prove some of the technical results involving these concepts. With those revisions, we shall see that minor variations of the original proofs verify the non-deterministic versions of the theorem.

We now describe how to modify the proofs of Theorems 7.1 and 7.2 of [6] to prove Theorems 1 and 2.

Given a non-deterministic Cannon’s algorithm and a word w_{0}, there is no longer a unique history to time n of w_{0}. We can call any sequence of words w_{0}, w_{1}, … w_{n} produced as the algorithm makes n substitutions on w_{0} a history, although it is no longer valid to call it the history.

The definitions of a “diagram”, a “substitution line”, and the “width” of a letter need no modification, nor do Lemmas 6.1 and 6.2 of [6] which relate the width of a letter to its generation.

The definition of a “splitting path” needs no modification. Lemma 6.4 of [6] states that a letter of generation g has a splitting path ending next to it of length at most 2g + 2. This remains true if we choose the history appropriately. We now show that we can do this.

Observe that in the non-deterministic case if a word w contains as disjoint substrings two left-hand sides, say u and u′ of the rules u → v and u′ → v′, then these two substitutions can be carried out in either order, i.e., either as

xuyu′z → xvyu′z → xvyv′z

or as

xuyu′z → xuyv′z → xvyv′z.

Now consider two histories,

h_{1} = w_{0}, …, xuyu′z, xvyu′z, xvyv′z, …, w_{n}

and

h_{2} = w_{0}, …, xuyu′z, xuyv′z, xvyv′z, …, w_{n}.

(Corresponding ellipses stand for identical sequences.) We will say that these are equivalent reductions^{1} and this generates an equivalence relation on reductions starting with w_{0} and ending with w_{n}. We can then speak of corresponding substitutions in equivalent reductions. Notice that corresponding substitution lines in equivalent reductions have the same width, occur at the same position horizontally, consume the same letters with the same widths and generations and produce the same letters with the same width and generation.

1The notion of equivalent reductions is not to be confused with the notion of equivalent histories defined below. Accordingly, we will briefly refer to histories as reductions to distinguish these equivalence relations.

Given a history w_{0}, …, w_{n}, there is a partial ordering of its substitutions which is generated by the relation s_{1} ≺ s_{2} if s_{2} consumes a letter produced by s_{1}. The relationship ≺ is visible in the diagram of the history in that s_{1} ≺ s_{2} if and only if there is a sequence of substitution lines with horizontally overlapping segents starting at s_{1} and ending at s_{2}. In particular, ≺- incomparable substitution lines do not overlap in horizontal position, except possibly at their endpoints. (We will omit further mention of this possible exception.) Because of this, given two ≺-incomparable substitutions s_{1} and s_{2} we either have s_{1} lying to the left of s_{2} or vice versa. Notice that if s_{1} lies to the left of s_{2}, then this is so for the corresponding substitutions in any equivalent reduction.

Lemma 5 Suppose that h_{1} = w_{0}, …, w_{n} is a reduction containing the substitutions s_{1} and s_{2} in which s_{1} takes place before s_{2} and s_{1} and s_{2} are ≺-incomparable. Then there is an equivalent reduction h_{2} in which the substitution corresponding to s_{1} takes place after that corresponding to s_{2}.

Proof: Note that s_{1} and s_{2} do not overlap horizontally. Thus, if these two substitutions take place at successive words of h_{1}, we are done.

Suppose now that no ≺-ancestor of s_{2} takes place later than s_{1}. In that case, s_{1} can be interchanged with the immediately preceding substitution, thus reducing by 1 the number of substitutions occurring between s_{1} and s_{2}. Continuing this in this way produces the previous case.

Finally, suppose there is s_{3} ≺ s_{2} with s_{3} occurring later than s_{1}. Let us suppose that s_{3} is the earliest such. Then s_{1} and s_{3} are ≺-incomparable, for otherwise we would have s_{1} ≺ s_{2}. Applying the previous case allows us to move s_{3} prior to s_{1}, thus reducing by 1 the number of ≺-ancestors of s_{2} lying between s_{1} and s_{2}. Continuing in this way produces the previous case. □

Corollary 6 Suppose that h_{1} = w_{0}, …, w_{n} is a reduction and that Σ_{1} and Σ_{2} are disjoint sets of substitutions in h_{1} with the property that no substitution of Σ_{1} is ≺-comparable with any substitution of Σ_{2}. Then there is an equivalent reduction h_{2} in which every substitution of Σ_{1} takes place before every substitution of Σ_{2}. □

In view of this, by passing to an equivalent reduction, we may assume that if s_{1} and s_{2} are ≺-incomparable and s_{1} takes place to the left of s_{2}, then s_{1} takes place prior to s_{2}.

Using this assumption on our choice of history justifies the statement in the proof of Lemma 6.4 that, “When this happens it can only be with substitutions to the left in the upper half and to the right in the lower.” The proof now goes through as before.

The definitions of “details” and equivalence of splitting paths need no modification. Remark 6.5 of [6] gives a bound on the number of equivalence classes of length n. This remains valid. (However, we could simplify the details by ceasing to record the W − 1 letters to the left/right in a right/left segment as part of the details. These are only needed to ensure that substitutions take place in the intended order in the deterministic case in Lemma 6.6.)

Lemma 6.6 of [6] states that if two histories, v_{0}, …, v_{r} and w_{0}, …, w_{s} have equivalent splitting paths then these can be spliced to form the history starting with v_{0}^{−}w_{0}^{+} and ending with v_{r}^{−}w_{s}^{+}. In our case, we need to modify the statement of Lemma 6.6 of [6] to say “Then a history of v_{0}^{−}w_{0}^{+} up to a suitable time ...” rather then “the history”, because this history may not be unique. With that change, Lemma 6.6 remains true.

The paragraph after the proof of Lemma 6.6 no longer applies at all; that is, v_{r} is not necessarily determined even in a weak sense by v_{0}.

Section 6.1 adapts these methods to respect subword boundaries. Given a reduction of v_{0} to v_{t}, and a subword w_{0} of v_{0}, this gives us a diagram for the reduction of w_{0} to the subword w_{t} of v_{t}. This subdiagram lies within the diagram for the reduction of v_{0} to v_{t} and shows w_{t} on the side opposite w_{0}. Lemma 6.7 of [6] says that if w_{0} is a subword of v_{0} of length N and w_{t} has length at least 2W − 1, then the reduction of w_{0} to w_{t} (and hence the reduction of v_{0} to v_{t}) has a splitting path in one of at most C_{1}N^{C_{2}} classes. The results of this section up to and including this Lemma remain valid.

Lemma 6.8 of [6] discusses the way that the choice of u_{0} affects the subword reduction of v_{0} in the word u_{0}v_{0}. This does not make sense as stated for a non-deterministic algorithm, because reduction of u_{0}v_{0} to u_{t}v_{t} no longer gives the word v_{t} as a function of u_{0}.

In order to state an analogous result, we need an appropriate notion of equivalence of histories. For fixed v_{0} and variable u_{0}, we define two histories u_{0}v_{0} → u_{t}v_{t} and u′_{0}v_{0} → u′_{t}v′_{t} to be equivalent if either:

(i) l(v_{t}) < W and v_{t} = v′_{t}; or (ii) l(v_{t}), l(v′_{t}) ≥ W, the first W −1 letters of v_{t} and v′_{t} are the same, and the two histories have equivalent splitting paths that begin at the same place in v_{0} and end immediately after the first W − 1 letters of v_{t} and v′_{t}.

Then it follows from Lemma 6.6 of [6] that, if u_{0}v_{0} → u_{t}v_{t} and u′_{0}v_{0} → u′_{t}v′_{t} are equivalent histories, then there is also a history u′_{0}v_{0} → u′_{t}v_{t}, to which both are equivalent. (Note: this notation may seem to imply that all of these histories have the same length t, but of course they need not. All three lengths might be different!)

Then the proof of Lemma 6.8 of [6] shows that, for fixed v_{0} of length N, there are at most C_{0}N^{C} equivalence classes of histories u_{0}v_{0} → u_{t}v_{t} for variable u_{0}.

We turn now to the proof of our Theorem 1. As we have already seen, the equivalent properties of having growing context sensitive word problem and having non-deterministic Cannon’s algorithms hold independently of the finite semigroup generating set G, so we only need to prove the nonexistence of the Cannon’s algorithm over G. We can further assume that 1 ∈ G so that any element which is represented by a word of length less than or equal to n is also represented by a word of length n. (It is also easily seen directly that the hypotheses of Theorems 1 and 2 do not depend on the choice of generators.) Assume for a contradiction that the hypotheses of that theorem hold and that there exists a non-deterministic Cannon’s algorithm over a working alphabet 𝔸 that contains G.

First we choose a specific value of n > 3W that is large enough for this stronger version of condition (2) of Theorems 1 and 2 to apply, |S_{i}(n)| ≥ α_{0}α_{1}^{n}, and also such that n is big enough so that that this exponential function is larger than a particular polynomial function that comes out of some of our technical lemmas. More precisely, we require

\frac{1}{2}α_{0}α_{1}^{n} > C_{1}n^{C_{2}+2}|𝔸|^{6W} C_{0}n^{C},

where C, C_{0}, C_{1} and C_{2} are the constants defined in Lemmas 6.7 and 6.8.

For i = 1, 2, let T_{i} be a set of words of length at least 3W and at most n representing the elements of S_{i}(n). Since each element of S_{1}(n) commutes with each element of S_{2}(n), we have u_{0}v_{0}u_{0}^{−1}v_{0}^{−1} =_{G} 1 for all u_{0} ∈ T_{1} and v_{0} ∈ T_{2}, and hence this word can be reduced, not necessarily uniquely, to the empty word by means of the Cannon’s algorithm. For ease of notation we write x_{0} for u_{0}^{−1} and y_{0} for v_{0}^{−1}. For each such u_{0} and v_{0}, we choose some sequence of substitutions that reduces u_{0}v_{0}x_{0}y_{0} to the empty word and let u_{t}v_{t}x_{t}y_{t} be the word that we get after applying t substitutions in this sequence.

For such a commutator, we run the algorithm to the point where for the first time v_{t} and x_{t} both have length less than 3W. At that time the longer one has length in the range [2W, 3W −1]. Note that t depends on u_{0} and v_{0}, and where it is used below it should seen that way, and not as a constant.

First we assume that for at least half of the pairs (u_{0}, v_{0}) ∈ T_{1} × T_{2}, we have l(v_{t}) ≥ l(x_{t}). We shall deal with the opposite case later.

Step 1. Now we fix a v_{0} ∈ T_{2}, chosen such that l(v_{t}) ≥ l(x_{t}) for at least half of the words u_{0} ∈ T_{1}, and we let U be the set of all words u_{0} with this property. Then |U| ≥ \frac{1}{2}α_{0}α_{1}^{n}.

Step 2. Since we have l(v_{t}) ≥ 2W, we can apply Lemma 6.7, which says that we can choose a splitting path for the subword history v_{0}, v_{1}, … v_{t} in one of polynomially many equivalence classes (C_{1}n^{C_{2}}, to be precise). That is to say there are polynomially many sets of details that can describe such a splitting path. This remains true (with the number increased to C_{1}n^{C_{2}+2}) if we add to the detail the information that tells us where within v_{0} the splitting path begins and where within v_{t} the splitting path ends. We call that the extended detail.

Step 3. Now since v_{0} is fixed we have a well defined map u_{0} ↦ v_{t}x_{t}y_{t}. (Recall that, although there may be many possible reduction sequences for u_{0}v_{0}x_{0}y_{0}, we arbitrarily chose some fixed sequence for each u_{0}.) Now we apply our amended version of Lemma 6.8 with u_{0}v_{0}x_{0} in place of u_{0} and y_{0} in place of v_{0}. This tells us there are at most polynomially (C_{0}n^{C} in fact) many equivalence classes of histories u_{0}v_{0}x_{0}y_{0} → u_{t}v_{t}x_{t}y_{t}. But u_{0} comes from a set of exponential size (at least \frac{1}{2}α_{0}α_{1}^{n}), which we have chosen to be bigger than the appropriate polynomial, through our choice of n. So we have a large set (of size more than C_{1}n^{C_{2}+2}) of u_{0} ∈ U that give rise to the same words v_{t} and x_{t}, and with the property that the histories u_{0}v_{0}x_{0}y_{0} → u_{t}(u_{0})v_{t}x_{t}y_{t}(u_{0}) (where v_{t} and x_{t} are fixed, but u_{t} and y_{t} depend on u_{0}) are all equivalent, in the sense defined above in our comments about the amended Lemma 6.8.

But, as we also noted above, Lemma 6.6 implies that these histories are also all equivalent to histories u_{0}v_{0}x_{0}y_{0} → u_{t}(u_{0})v_{t}x_{t}y_{t} for the same fixed y_{t}. Note that in these two equivalent histories u_{0}v_{0}x_{0}y_{0} → u_{t}(u_{0})v_{t}x_{t}y_{t}(u_{0}) and u_{0}v_{0}x_{0}y_{0} → u_{t}(u_{0})v_{t}x_{t}y_{t}, the parts of the two histories to the left of the splitting line are the same except for the number of steps in which the words remain constant. So we can use essentially the same splitting paths as we chose in Step 2 for the second history.

Step 4. Since the number of u_{0} giving rise to equivalent histories in Step 3 is greater than the number of equivalence classes of positioned splitting paths for v_{t} in Step 2, we can choose u_{0}, u′_{0} ∈ U such that u_{0}v_{0}x_{0}y_{0} → u_{t}v_{t}x_{t}y_{t} and u′_{0}v_{0}x_{0}y_{0} → u′_{t}v′_{t}x′_{t}y′_{t} are equivalent histories with v′_{t} = v_{t} and x′_{t} = x_{t}, and such that the subhistories v_{0} → v_{t} and v_{0} → v′_{t} in the two histories contain equivalent splitting paths, which start at the same position in v_{0} and end in the same position in v_{t} = v′_{t}.

By the remark above, the second of these histories (and hence also the first!) is equivalent to a history u′_{0}v_{0}x_{0}y_{0} → u′_{t}v′_{t}x′_{t}y_{t}, which still contains an equivalent splitting path through v_{0} → v′_{t}. Now we can do our splicing, and apply Lemma 6.6 of [6] to produce a history u_{0}v_{0}^{−}v_{0}^{′+}x′_{0}y′_{0} → u_{t}v_{t}^{−}v_{t}^{′+}x′_{t}y_{t} = u_{t}v_{t}x_{t}y_{t}.

But u_{t}v_{t}x_{t}y_{t} is part of the originally chosen history that reduces the commutator u_{0}v_{0}x_{0}y_{0} to the empty word, so there exists a history that reduces u_{0}v_{0}^{−}v_{0}^{′+}x′_{0}y′_{0} to the empty word, a contradiction, because this is not the identity element of the group.

In the second case (not considered in detail in Section 7 of [6]) where l(x_{t}) ≥ l(v_{t}) for at least half the pairs (u_{0}, v_{0}) ∈ T_{1} × T_{2}, rather than fix v_{0} ∈ T_{2} we fix u_{0} ∈ T_{1} in a similar way, and let V be the possible v_{0} from which, together with the chosen u_{0}, we get l(x_{t}) ≥ l(v_{t}). Then we apply Lemma 6.7 to the subword histories x_{1}, … x_{t}. Now we look at the map v_{0} ↦ u_{t}v_{t}x_{t}. The analogue of Lemma 6.8 applied to u_{t}v_{t} tells us that u_{t} can take polynomially many values, and we see that we get a large set of possible v_{0} ∈ V corresponding to a single u_{t}v_{t}x_{t}. Hence we can choose v′_{0} mapping such that u_{t}v_{t}x_{t} = u′_{t}v′_{t}x′_{t} and such that the subword histories x_{1}, … x_{t} and x′_{1}, … x′_{t} have the same extended details, and we can splice. Hence we see that the algorithm should rewrite u_{0}v_{0}x_{0}^{−}x_{0}^{′+}y′_{0} to u_{t}v_{t}x_{t}^{−}x_{t}^{′+}y′_{t}. Since x_{0} = x′_{0}, the first of these two words is equal to u_{0}v_{0}x_{0}y′_{0}, equal in the group to v_{0}v_{0}^{′−1}, so non-trivial. But the second word is equal to u′_{t}v′_{t}x′_{t}y′_{t}, which rewrites to the trivial word. Hence again we get our contradiction.

Modifying the proof of Theorem 7.2 from [6] in the same way, we arrive at a proof of Theorem 2.

Basically we choose n_{1}, n_{2} with

\frac{1}{2}α_{0}α_{1}^{n_{1}} > C_{1}n_{2}^{C_{2}+2}|𝔸|^{6W} C_{0}n_{2}^{C}, \frac{1}{2}α_{2}n_{2} > C_{1}n_{1}^{C_{2}+2}|𝔸|^{6W} C_{0}n_{1}^{C}

which we can do, for example, by first setting n_{2} equal to some polynomial function in n_{1} so that (2) is satisfied for all n_{1}, and then choosing n_{1} big enough so that (1) holds. (But notice that we need Hypothesis (2) in the statement of the theorem to be satisfied for these particular values of n_{1} and n_{2}, which is why we have assumed this hypothesis for all integers n > 0 rather than for infinitely many such n, which was sufficient for Theorem 1.)

As in the proof of Theorem 1, for i = 1, 2, we choose T_{i} to be a set of words of length at least 3W and at most n that represent the elements of S_{i}. Those conditions will now ensure each \frac{1}{2}|T_{i}| (i = 1, 2) is bounded below by the appropriate polynomial function of n_{2}, n_{1} which allows us to find u_{0}, u′_{0}. So in the case where v_{t} is longer than u_{t} we can do just what we did in the first case of Theorem 1, since T_{1} is big enough we can find a big enough set of elements of U mapping to the same v_{t}x_{t}y_{t}.

And in the second case we have T_{2} big enough, and so we can follow the argument used in the second case of the proof of Theorem 1

References

[1] Gerhard Buntrock, Home Page Growing Context Sensitive Languages,

http://www.itheoi.mu-luebeck.de/pages/buntrock/research/gcsl.html.

[2] Gerhard Buntrock and Krzysztof Loryś, On Growing Context-Sensitive Languages, in Automata, Languages and Programming, 19th International Colloquium, Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings, ed. Werner Kuich, Lecture Notes in Computer Science, vol 623, Springer 1992, 77–88.

[3] Gerhard Buntrock and Krzysztof Loryś, The variable membership problem: succinctness versus complexity, in STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings, ed. Patrice Enjalbert, Ernst W. Mayr and Klaus W. Wagner, Lecture Notes in Computer Science, vol 775, Springer 1994, 595–606.

[4] Gerhard Buntrock and Friedrich Otto, Growing context-sensitive languages and Church-Rosser Languages, in STACS 95, 12th Annual Symposium on Theoretical Aspects of Computer Science, Munich, Germany, March 2-4, 1995. Proceedings, ed. Ernst W. Mayr and Claude Puech, Lecture Notes in Computer Science, vol 900, Springer 1995, 313–324.

[5] D.B.A. Epstien, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson, W.P. Thurston, Word Processing in Groups, Jones and Bartlett, 1992.

[6] O. Goodman and M. Shapiro, A generalisation of Dehn’s algorithm,

arXiv preprint, http://front.math.ucdavis.edu/0706.3024.

[7] M. Kambites and F. Otto, Church-Rosser groups and growing context-sensitive groups, preprint, available from

http://www.maths.manchester.ac.uk/~mkambites/.

[8] M. Shapiro, A note on context-sensitive languages and word problems, Internat. J. Algebra Comput. (4) 4 (1994) 493–497.