# On groups whose word problem is solved by a nested stack automaton

## 1. Introduction.

During the past several years combinatorial group theory has received an infusion of ideas both from topology and from the theory of formal languages. The resulting interplay between groups, the geometry of their Cayley diagrams, and associated formal languages has led to several developments including the introduction of automatic groups , hyperbolic groups , and geometric and language–theoretic characterizations of virtually free groups .

We will restrict our attention to finitely generated groups. For any such group the language of all words which define the identity is called the word problem of the group. By words we mean words over the generators. Of course the word problem depends on the choice of generators. In  virtually free groups are shown to be exactly those groups whose word problem with respect to any set of generators is a context–free language. We are interested in investigating groups whose word problems lie in other language classes.

Formal languages are often defined in terms of the type of machine which can tell whether or not a given word is in the language. Such a machine is said to accept the language. Context–free languages are accepted by pushdown automata, and those context–free languages which are word problems are accepted by the subclass of deterministic limited erasing pushdown automata \[17, Lemma 3\]. In this paper we show that the more powerful class of deterministic limited erasing nested stack automata accept exactly the same word problems.

###### Theorem 1.1.

Suppose $`G`$ is an accessible group whose word problem is recognized by a deterministic nested stack automaton with limited erasing which accepts by final state and empty stack; then $`G`$ is virtually free.

The question of whether or not every group whose word problem is accepted by a nested stack automaton is virtually free has been open for some time. Some possible counterexamples are proposed in . Notice our assumption that $`G`$ is accessible. While it is not difficult to show that a group with context–free word problem is finitely presented (and therefore accessible), deciding the same question for groups whose word problem is accepted by a nested stack automaton seems much harder.

In  and  virtually free groups are characterized by geometric conditions on their Cayley diagrams as well as by language–theoretic conditions on their word problems. In the course of proving Theorem 1.1 we are led to another such geometric condition. To express this condition we recall that a choice of generators determines a word metric on a group. The distance between two group elements $`g`$ and $`h`$ is the length of the shortest word representing $`g^1h`$. This metric is just the restriction to vertices of the path metric in the corresponding Cayley diagram. Different word metrics for the same group are quasi–isometric. (See Definition 2.1.) We will assume that every group is equipped with a word metric.

###### Definition 1.2.

A group is narrow if there exists an integer $`i`$ such that for any ball $`B`$ and all but finitely many other balls $`B^{}`$ of the same radius, $`B`$ is separated from $`B^{}`$ by a set of size at most $`i`$. A group which is not narrow is wide.

Two subsets are separated by a set $`S`$ if every path between them intersects $`S`$. By path we mean a finite sequence of points each a distance one from its successor. In other words a path is just the sequence of vertices occurring in a path in the Cayley diagram.

Whether or not a group is narrow seems to depend on its word metric, but in fact it does not.

###### Theorem 1.3.

Narrowness is a quasi–isometry invariant of groups.

In adition narrowness characterizes those accessible groups which are virtually free.

###### Theorem 1.4.

If the group $`G`$ is finitely generated and accessible, then the following conditions are equivalent.

1. $`G`$ is wide;
2. $`G`$ is not virtually free;
3. $`G`$ contains a one–ended subgroup.

If $`G`$ is wide, then a one–ended subgroup can be found by splitting $`G`$ over finite subgroups.

Narrowness is related to two geometric conditions shown in  to characterize virtually free groups. By \[18, Theorem 2.9\] any finitely generated group $`G`$ (accessible or not) is virtually free if and only if the components of the complements of all balls fall into finitely many isomorphism classes of labeled graphs. In fact by a remark in the proof of that theorem, $`G`$ is virtually free if and only if the frontiers of the components have uniformly bounded size. Clearly this condition implies that $`G`$ is narrow, as any ball $`B`$ is separated from all but finitely many balls of the same radius by the frontiers of the components of the complement of $`B`$. Conversely if $`G`$ is narrow and accessible, then by  and Theorem 1.4, $`G`$ satisfies the other two geometric conditions. We do not know if there are narrow groups which are not virtually free.

We are indebted to Swarup Gadde, Chuck Miller, Walter Neumann, Christophe Pittet, and Nick Wormald for helpful conversations and in particular to Pittet for an argument which appeared in earlier versions of this paper. The second author wishes to extend special thanks to Rostislav Grigorchuk for his hospitality, and for first introducing him to this problem.

The reader is referred to Aho’s original paper  on nested stack automata, and for background on language theory to Hopcroft and Ullman’s book  on automata theory. The books by Cohen  and Lyndon and Schupp  are references for combinatorial group theory.

## 2. Preliminaries.

###### Definition 2.1.

A map $`\phi :XX^{}`$ between metric spaces $`(X,d)`$ and $`(X^{},d^{})`$ is a quasi–isometry if there exists a positive constant $`k`$ such that

1. $`(1/k)d(x,y)kd(\phi (x),\phi (y))kd(x,y)+k`$;
2. $`X^{}=_{xX}B_k(\phi (x))`$

For example inclusion of a group with the word metric corresponding to a choice of generators into the Cayley determined by the same generators is a quasi–isometry.

Quasi–isometry of metric spaces is an equivalence relation. As different choices of finite generating set for a group yield quasi–isometric metrics, it follows that all Cayley diagrams for a finitely generated group are quasi–isometric. In fact Cayley diagrams for commensurable groups are quasi–isometric \[9, Prop. 11, page 8\].

Recall that all groups are assumed to be finitely generated. A virtually free group is one with a free subgroup of finite index; virtually cyclic groups are defined likewise. All finite groups are virtually cyclic.

A group $`G`$ is one–ended if for all $`r`$ the complement in its Cayley diagram of the ball of radius $`r`$ around the identity has exactly one infinite component. It is not hard to show that the validity of this condition is independent of the generating set of the group. A famous theorem of Stallings  says that a group which is not one–ended is either virtually cyclic, or splits as a free product of two factors with a finite subgroup amalgamated, or is an HNN extension with one stable letter and finite associated subgroups.

In the latter two cases we have $`G=H_1_{K_0}H_2`$ or $`G=H_0,tt^1K_1t=K_2`$ respectively for subgroups $`H_i`$ of $`G`$. We call $`H_i`$ a factor and $`K_i`$ an associated subgroup. In either case we say that $`G`$ splits over a finite subgroup.

When a group $`G`$ splits over a finite subgroup, it may be possible that a factor splits over a finite subgroup, and one of the factors of that splitting splits again etc. $`G`$ is accessible if there is an upper bound on the length of any such chain of splittings. The least upper bound is the accessibility length of $`G`$. It is a result of Dunwoody  that a finitely presented group is accessible.

###### Lemma 2.2.

An accessible group is either virtually free or contains a one–ended subgroup.

###### Proof.

If $`G`$ does not split over a finite subgroup, then it is virtually cyclic or one–ended. If it does split, use induction on accessibility length together with results of Gregorac  and Karrass, Pietrowski and Solitar  which say that a group which splits over a finite subgroup is virtually free if each factor is. ∎

## 3. Machines.

We begin with an informal account based on the original definition of nested stack automata as a certain kind of computer . However this definition is unwieldy, so our subsequent formal definition is in terms of labeled graphs. This approach to automata theory is well established. See for example Brainerd and Landweber \[2, Chapter 4\], Eilenberg \[5, Volume A, Chapter X\], Floyd and Biegel , Gilman , Goldstine , and Salomaa, Wood and Yu .

Figure 1 shows a nested stack automaton $`A`$ consisting of a finite one–way input tape holding a word form an input alphabet $`\mathrm{\Sigma }`$, a finite set of internal states $`\{q_i\}`$, and a memory which at each instant contains a finite directed tree with edge labels from a memory alphabet $`\mathrm{\Xi }`$. At each instant $`A`$ is in a particular internal state, $`q_i`$, and is either scanning a cell on the input tape or has moved off the tape to the right. Also $`A`$ is pointing at a vertex of its memory tree. The label of the inedge to this vertex is called the current memory symbol. If $`A`$ is pointing to the root, the current memory symbol is the empty word $`ϵ`$.

$`A`$ begins a computation in a designated initial state $`q_0`$ and scanning the leftmost cell on its input tape (or off the tape if the input is $`ϵ`$). Initially the memory is empty; that is, the memory tree consists of just a single vertex. Each computation consists of a number of moves, and $`A`$ is completely specified by a list of moves to be made for various combinations of internal state, input letter, and current memory symbol. The input letter is either the content of the current cell on the input tape or $`ϵ`$. In the former case $`A`$ moves right on the input tape as the last part of the move; in the latter case it does not. If $`A`$ has moved off the input tape, only $`ϵ`$–moves are possible. For any particular combination of internal state, input letter, and memory symbol there may be one, many or no moves specified.

If there is a sequence of moves in which $`A`$ moves off the input tape and reaches a configuration with empty memory and one of a designated set of final states, then $`A`$ accepts the word on the input tape. The set of all accepted words is the language accepted by $`A`$. If $`A`$ reaches a situation in which no move is possible, it halts. If the conditions just mentioned obtain, then the input is accepted, otherwise not. $`A`$ need not halt after accepting an input, but its susequent behavior has no effect on the language accepted.

In addition to updating the pointer to the input tape, the other parts of a move are the choice of a new internal state and a memory operation. There are four memory operations in addition to the trivial operation $`1`$ in which the memory tree $`T`$ is left unchanged. To define these operations we observe that during a computation vertices are added to and deleted from $`T`$. Thus at any given time the vertices are ordered according to when they were added to $`T`$. The root is the earliest vertex and is never deleted. The four memory operations are moving the pointer down to the the parent of the current vertex if that vertex is not the root, moving the pointer up to the latest child of a vertex if a child exists, deleting the current vertex if it is a leaf but not the root, and adding a new edge whose source is the current vertex and whose target is a new leaf. After deleting a leaf the current vertex is set to the source of the edge to that leaf, and after adding a new edge the current vertex is set to the new leaf.

It follows from the definitions above that the the vertex pointed to by $`A`$ is always on the path from the root to the latest vertex, which is a leaf. In particular only the latest vertex can be deleted. Our description is not quite the same as the original in . There the memory tree of Figure 1 would be replaced by a memory tape containing three nested stacks $`\$x_1x_2\$y_1\$z|c\widehat{y_2}|cx_3\mathrm{\#}`$. In addition we allow NSA’s to operate on empty stack. We leave it to the reader to check that the two kinds of machine are equivalent in the sense that each can simulate the other.

Now we will give a more precise definition of nested stack automaton. We fix once and for all an infinite countable memory alphabet $`\mathrm{\Xi }`$. Each NSA will use only finitely many letters from $`\mathrm{\Xi }`$, so this convention does no harm. We order the vertices of a finite tree by depth first search. That is, the root is earliest followed by all the vertices in order along a path to a leaf. Then we back up to the first vertex with an outedge which has not been traversed and continue along that edge to another leaf, etc. Edges are ordered according to their target vertices. If the tree in Figure 1 is ordered this way by taking the leftmost possible outedge at each opportunity, the corresponding ordering of edge labels would be $`x_3,x_2,x_1,y_2,y_1,z`$.

It is clear that for any tree ordered by depth–first seach the latest vertex is a leaf and deleting it gives a tree ordered in the same way. Likewise adding a new edge with source anywhere along the path from the root to the latest vertex and making the new leaf later than all the other vertices in the tree yields a tree ordered in the right way.

###### Definition 3.1.

The set $`𝔗`$ of memory trees consists of all finite trees $`T`$ ordered by depth–first search with

1. Root vertex $`v_0`$;
2. Edges labeled by letters from $`\mathrm{\Xi }`$;
3. All edges directed away from the root;
4. One distinguished vertex on the path from $`v_0`$ to the latest vertex of $`T`$.

$`T_0`$ is the tree consisting of just $`v_0`$.

Next we define a monoid of operators on memory trees.

###### Definition 3.2.

$`M_{\text{nsa}}`$ is the monoid generated under composition by certain partial maps from $`𝔗`$ to itself. Pick $`T𝔗`$ with distinguished vertex $`v`$, and let $`y`$ be the label of the inedge to $`v`$. If $`v=v_0`$, then $`y=ϵ`$. We describe the effect of the partial maps on $`T`$. In each case if $`T`$ does not satisfy the conditions given, then the map is not defined at $`T`$.

If $`x=y`$ and $`vv_0`$, then $`D_x(T)`$ is obtained by changing the distinguished vertex of $`T`$ to the parent of $`v`$.

If $`x=y`$ and $`v`$ is not a leaf, make the latest child of $`v`$ the new distinguished vertex.

Add to $`T`$ a new edge with source $`v`$, label $`x`$, and target a new vertex $`v_1`$. Make $`v_1`$ the latest vertex of $`T`$ and the new current vertex.

If $`x=y`$ and $`v`$ is a leaf with parent $`v_1`$, delete $`v`$ and its inedge. Make $`v_1`$ the distinguished vertex.

Clearly $`M_{\text{nsa}}`$ acts by partial injective maps whence it is a submonoid of the symmetric inverse semigroup on $`𝔗`$. $`M_{\text{nsa}}`$ has both an identity and a zero element, which we denote by $`1`$ and $`0`$ respectively.

###### Definition 3.3.

Let $`\mathrm{\Sigma }`$ be a finite alphabet. A nested stack automaton $`A`$ over $`\mathrm{\Sigma }`$ is a finite directed graph with a designated initial vertex, designated final vertices, and with edges labeled by pairs $`(m,a)`$ where $`a\mathrm{\Sigma }\{ϵ\}`$, and either $`m=1`$ or $`m`$ is one of the generators defined in Definition 3.2.

Every (directed) path in $`A`$ has a label $`(m,w)`$ formed by multiplying the components of the edge labels in order. A path of length zero has label $`(1,ϵ)`$.

###### Definition 3.4.

A computation of a nested stack automaton $`A`$ is a path $`\gamma `$ which starts at the initial vertex of $`A`$ and has label $`(m,w)`$ for some $`m`$ with $`T=m(T_0)`$ defined. $`T`$ is called the outcome of $`\gamma `$. The word $`w`$ is accepted by $`A`$ if there is a computation with label $`(w,m)`$ and outcome $`T=T_0`$ ending at a final state. These computations are called successful. The set of all accepted words is the language accepted by $`A`$.

In other words $`A`$ accepts $`w`$ if it can read all of $`w`$, empty its memory, and stop at a final state. One can also consider NSA’s which accept just by final state or empty memory, but we do not do so here.

Figure 2 shows an NSA $`A`$ which accepts $`\{a^nb^nc^nd^n\}^{}=\{(a^nb^nc^nd^n)^kn0,k0\}`$. Vertex 1 is both the start vertex and the single final vertex. To see that $`A`$ accepts the language claimed, first observe that domain of $`U_x`$ is disjoint from the range of $`Q_x`$. Thus a computation in the sense of Definition 3.4 cannot have an edge with label $`(Q_x,d)`$ followed by one with label $`(U_x,c)`$. Consequently the label of any successful computation by $`A`$ is a product of terms of the form $`(P_yP_x^iD_x^jU_yU_x^kQ_x^lQ_y,a^ib^jc^kd^l)`$. In particular there is a successful computation whose label is the empty product, $`(1,ϵ)`$, so $`A`$ accepts $`ϵ`$.

To show that the language accepted by $`A`$ is as claimed, it suffices to show that the exponents $`i,j,k,l`$ in any term above are equal and that all cases in which the exponents are equal and greater than $`0`$ can occur. Suppose $`(P_yP_x^iD_x^jU_yU_x^kQ_x^lQ_y,a^ib^jc^kd^l)`$ is the first term. $`A`$ begins by constructing a memory tree $`T`$ with a single branch labeled $`yx^i`$. If $`i<j`$, then $`A`$ tries unsuccessfully to move down to the root of $`T`$ by executing $`D_x`$ while pointing at the vertex of $`T`$ with inedge labeled $`y`$. If $`i>j`$, then $`A`$ tries to move up past the leaf of $`T`$. Conseqently $`A`$ reaches vertex $`4`$ if and only if $`i=j>0`$ and $`k>0`$. Additional arguments of a similar nature demonstrate that $`A`$ returns to vertex $`1`$ if and only if $`i=j=k=l>1`$ and that upon its return $`T=T_0`$. But $`T=T_0`$ imples that our analysis applies to each term in succession.

It follows easily from the preceding paragraph that at any point in a computation the memory tree $`T`$ has only a single branch. In other words $`A`$ is a stack automaton; operations $`P_x`$ are executed only when the distinguished vertex is a leaf. In addition it is clear from Figure 2 that $`A`$ has at most one move for each combination of state and input symbol. Such automata are called deterministic.

###### Definition 3.5.

An NSA $`A`$ over $`\mathrm{\Sigma }`$ is deterministic if each combination of vertex $`v`$, memory $`T`$, and letter $`a\mathrm{\Sigma }`$ admits at most one outedge with label $`(m,a)`$ or $`(m,ϵ)`$ such that $`m(T)`$ is defined. In other words the $`m`$’s which occur in labels of these outedges have pairwise disjoint domains in $`𝔗`$.

Any computation of length $`n`$ by a deterministic NSA can be continued in at most one way to a computation of length $`n+1`$.

###### Definition 3.6.

An NSA $`A`$ has limited erasing if there is a constant $`k`$ such that every path in $`A`$ with label $`(m,ϵ)`$ has at most $`k`$ edges with labels involving $`Q`$. In other words the $`A`$ makes at most $`k`$ erasures from its memory without consuming input.

The NSA in Figure 2 is deterministic and has limited erasing with $`k=1`$.

###### Lemma 3.7.

Suppose $`L\mathrm{\Sigma }^{}`$ is the language of all words accepted by the deterministic NSA with limited erasing $`A`$ over $`\mathrm{\Sigma }`$. If $`\mathrm{\Delta }`$ is a finite alphabet and $`f:\mathrm{\Delta }^{}\mathrm{\Sigma }^{}`$ is a homomorphism which does not map any generator to the empy word, then $`f^1(L)`$ is also accepted by a deterministic NSA with limited erasing.

###### Proof.

Suppose first that $`f`$ maps generators to generators. In this case we can construct the required NSA $`A^{}`$ directly from $`A`$. Replace each edge with label $`(m,a)`$, $`a\mathrm{\Sigma }`$, by a set of edges with labels $`(m,p)`$ for all $`pf^1(a)`$. The new edges have the same source and target as the edge they replace. If $`f^1(a)`$ is empty, the original ledge is simply deleted. It is clear from the construction that $`A^{}`$ is deterministic with limited erasing. Further for any path in $`A`$ from vertex $`v_1`$ to $`v_2`$ with label $`(m,w)`$ there is for each $`w^{}f^1(w)`$ a path in $`A^{}`$ from $`v_1`$ to $`v_2`$ label $`(m,p)`$. Conversely every path in $`A^{}`$ with label $`(m,w^{})`$ projects to a path in $`A`$ with label $`(m,f(w^{}))`$. It follows that $`A^{}`$ accepts $`f^1(L)`$.

In general $`f`$ factors as a product of homomorphisms of the type just considered and homomorphisms which map one generator into a word of length two and all other generators into themselves. Thus it suffices to prove $`f^1(L)`$ is an NSA language in this second case. More precisely we may assume that $`\mathrm{\Delta }`$ and $`\mathrm{\Sigma }`$ are the same except that one generator $`a\mathrm{\Delta }`$ is replaced by $`a_1`$ and $`a_2`$ in $`\mathrm{\Sigma }`$. Further $`f(a)=a_1a_2`$ and $`f`$ maps all other elements of $`\mathrm{\Delta }`$ to themselves.

Construct an NSA $`A^{}`$ from the union of two disjoint copies of $`A`$, say $`A_1`$ and $`A_2`$. The idea here is to modify $`A_1A_2`$ so that paths in $`A`$ correspond to paths in $`A_1`$ except that subpaths with label sequences

$$(m_1,a_1),(m_2,ϵ),\mathrm{},(m_{k1},ϵ),(m_k,a_2)$$

move over to $`A_2`$ at the first edge and return to $`A_1`$ at the last edge. Further the first label of such a subpath is changed to $`(m_1,a)`$ and the last to $`(m_k,ϵ)`$. It is also necessary to prevent $`A^{}`$ from emptying its memory at any vertex in $`A_2`$. For this purpose we add a new memory symbol $`z`$ which is pushed on to the memory at the beginning of each computation and which can only be removed at final vertices in $`A_1`$.

More precisely $`A^{}`$ is formed from the disjoint union $`A_1A_2\{v_0,v_1\}`$ in the following way.

1. The start vertex of $`A^{}`$ is $`v_0`$, and there is an edge from $`v_0`$ to the start vertex of $`A_1`$ with label $`(P_z,ϵ)`$;
2. Every final vertex of $`A_1`$ has an outedge to $`v_1`$ with label $`(Q_z,ϵ)`$;
3. The single final vertex is $`v_1`$.
4. Each edge in $`A_1`$ with $`a_1`$ in its label has $`a_1`$ changed to $`a`$ and its terminal vertex changed to the corresponding vertex in $`N_2`$;
5. All edges from $`A_2`$ except those with an $`ϵ`$ or $`a_2`$ in their label are removed;
6. Each edge in $`A_2`$ whose label involves $`a_2`$ has $`a_2`$ changed to $`ϵ`$ and its terminal vertex changed to the corresponding vertex of $`N_1`$.

It is straightforward to check that $`A^{}`$ is deterministic with limited erasing, and accepts $`f^1(L)`$. ∎

## 4. Group languages.

In this section we develop the first properties of groups whose word problems are solvable by deterministic nested stack automata with limited erasing. From now on NSA will refer to an anutomaton of this type which accepts by final state and empty stack, and NSA language will mean a language accepted by an NSA.

We fix some notation. A choice of generators for a group $`G`$ is a surjective monoid homomorphism $`\sigma :\mathrm{\Sigma }^{}G`$ from a finitely generated free monoid. We will write $`\overline{w}`$ for $`\sigma (w)`$ and assume that a choice of generators $`\sigma :\mathrm{\Sigma }^{}G`$ always has formal inverses. That is, $`\mathrm{\Sigma }`$ is a union of pairs $`\{a,a^1\}`$ and $`\sigma (a^1)=(\sigma (a))^1`$. We emphasize that $`\mathrm{\Sigma }`$ still generates $`\mathrm{\Sigma }^{}`$ freely as a monoid; there is no cancellation in $`\mathrm{\Sigma }^{}`$. Recall that $`ϵ`$ denotes the empty word and $`\overline{ϵ}=1`$. The word problem of $`G`$ corresponding to a certain choice of generators is $`\{w\mathrm{\Sigma }^{}\overline{w}=1\}`$.

###### Lemma 4.1.

If the word problem of a group $`G`$ with respect to one choice of generators is an NSA language, then so are the word problem with respect to any choice of generators and the word problem for every finitely generated subgroup of $`G`$.

###### Proof.

Let $`\sigma :\mathrm{\Sigma }^{}G`$ be a generating set for $`G`$ such that an NSA solves the word problem for $`G`$ with respect to $`\mathrm{\Sigma }^{}`$, and $`\delta :\mathrm{\Delta }^{}HG`$ be a generating set for $`H`$. Choose a homomorphism $`f:\mathrm{\Sigma }^{}\mathrm{\Delta }^{}`$ such that $`\delta f=\sigma `$ and $`f`$ does not map any generator to the identity. Apply Lemma 3.7. ∎

Now let $`A`$ be an NSA over $`\mathrm{\Sigma }`$ accepting the word problem of $`G`$ with respect to a choice of generators $`\mathrm{\Sigma }^{}G`$. We use $`A`$ to construct a graph $`𝒜`$ which covers both $`A`$ and $`𝒢`$, the Cayley diagram of $`G`$. We augment $`𝒢`$ by adding an edge with label $`ϵ`$ from every vertex to itself.

###### Definition 4.2.

A configuration of an NSA $`A`$ is a pair $`(q,T)`$ where $`q`$ is a state of $`A`$ and $`T`$ is a memory tree. A configuration is accessible if $`T`$ is the outcome of a valid computation $`\gamma `$ ending at $`q`$ and if there is a continuation $`\gamma ^{}`$ such that $`\gamma \gamma ^{}`$ is successful.

Accessible configurations might more properly be called accessible and co–accessible.

###### Definition 4.3.

The configuration graph $`𝒜`$ of $`A`$ has as vertices all accessible configurations. There is an edge from $`(q,T)`$ to $`(q^{},T^{})`$ with label $`a\mathrm{\Sigma }\{ϵ\}`$ if and only if there is an edge with label $`(m,a)`$ from $`q`$ to $`q^{}`$ in $`A`$ such that $`m(T)=T^{}`$. The initial vertex of $`𝒜`$ is $`(q_0,T_0)`$ where $`q_0`$ is the initial vertex of $`A`$.

In Figure 3 a vertex with label $`yx3x`$, say, stands for the configuration $`(3,T)`$ in which $`T`$ consists of one branch of length three with label $`yxx`$ and distinguished vertex a distance two from the root.

The the first half of the next lemma is clear from Definition 3.3 and Definition 3.4; the second half follows from Definitions 3.5 and 3.6.

###### Lemma 4.4.

The following conditions hold.

1. Every computation $`\gamma `$ of $`A`$ which can be continued to a successful computation lifts uniquely to a path in $`𝒜`$ which starts at $`(q_0,T_0)`$ and has label equal to the first component of the label of $`\gamma `$.
2. If a computation which ends at $`q`$ with outcome $`T`$ lifts to a path starting at $`(q_0,T_0)`$, then the lift ends at $`(q,T)`$. Conversely any path in $`A`$ from $`(q_0,T_0)`$ to a vertex $`(q,T)`$ is the lift of a computation with outcome $`T`$.
3. Each vertex of $`𝒜`$ either has a single outedge with label $`ϵ`$ and no other outedges, or it has no outedges with label $`ϵ`$ and at most one outedge with label $`a`$ for each $`a\mathrm{\Sigma }`$.
4. For some constant $`K`$ any path in $`𝒜`$ has at most $`K`$ successive edges labeled $`ϵ`$.

###### Lemma 4.5.

There is a homomorphism of labeled graphs $`\phi :𝒜𝒢`$, where $`𝒢`$ is Cayley diagram of $`G`$ augmented by the addition of a loop with label $`ϵ`$ at every vertex. The image of a vertex in $`𝒜`$ is the group element represented by the label of any path from $`(q_0,T_0)`$ to that vertex. In particular the initial vertex of $`𝒜`$ maps to $`1`$. Every path $`𝒢`$ starting at $`1`$ lifts to a path in $`𝒜`$ which starts at $`(q_0,T_0)`$ and projects to a path differing from the original only by addition or deletion of edges with label $`ϵ`$. The lift is unique up to a terminal segment with label $`ϵ`$.

###### Proof.

By definition of $`𝒜`$ each vertex $`(q,T)`$ is reached by a path from $`(q_0,T_0)`$. Suppose there are two such paths with labels $`w`$ and $`w^{}`$. By the definition of $`𝒜`$ again there is a path from $`(q,T)`$ to some vertex $`(q^{},T_0)`$. Let $`u`$ be the label of this path. Then $`A`$ accepts $`wu`$ and $`w^{}u`$ whence both denote the identity in $`G`$. It follows that $`w`$ and $`w^{}`$ represent the same element of $`G`$.

Define $`\phi `$ by mapping each vertex of $`𝒜`$ to the group element represented by the label of any path from $`(q_0,T_0)`$ to that vertex. In particular $`\phi ((q_0,T_0))=1`$. Suppose there is an edge from $`(q,T)`$ to $`(q^{},T^{})`$ with label $`a\mathrm{\Sigma }\{ϵ\}`$. Pick a path from $`(q_0,T_0)`$ to $`(q,T)`$, and let its label be $`w`$. As $`wa`$ is the label of a path to $`(q^{},T^{})`$, it follows that if $`\phi ((q,T))=g`$, then $`\phi ((q^{},T^{}))=g\overline{a}`$. Thus $`\phi `$ is a graph homomorphism.

Since $`\phi `$ is a homomorphism, the penultmate assertion amounts to showing that for every $`w\mathrm{\Sigma }^{}`$ there is a path in $`𝒜`$ starting at $`(q_0,T_0)`$ and with label $`w`$. But for some $`v\mathrm{\Sigma }^{}`$, $`wv`$ represents the identity in $`G`$ and hence there is a successful computation in $`A`$ with label $`(m,w)`$. The last assertion follows from the third part of Lemma 4.4. ∎

We pause to remark on a difference in configuration graphs of NSA’s and pushdown automata which illustrates the different power of the two types of automaton. A pushdown automaton is a nested stack automaton, not necessarily quasi-realtime or deterministic, which has no labels involving $`D_x`$ or $`U_x`$. In other words its memory trees all have just one branch and the distinguished vertex is always the leaf. We metrize graphs in the usual way by disregarding orientation and taking edges to be isometric to the unit interval.

###### Theorem 4.6.

The configuration graph of a pushdown automaton is quasi-isometric to a tree. This quasi-isometry is given by a quotient map. In contrast to this, the configuration graph of a stack automaton (and hence an NSA) may have arbitrarily large isometrically embedded loops.

###### Proof.

The second claim is clear from Figure 3. It remains to prove that the configuration graph of a pushdown automaton is quasi–isometric to a tree. Let $`𝒜`$ be the configuration graph of a pushdown automaton $`A`$. We will write $`(p,T)(q,T)`$ if there is an undirected path in $`𝒜`$ between $`(p,T)`$ and $`(q,T)`$ with the property that $`T`$ is an initial segment of the memory tree of every intermediate vertex. That is to say, $`(p,T)(q,T)`$ if we can get from $`(p,T)`$ to $`(q,T)`$ by a sequence of forward and backwards moves without ever erasing any portion of $`T`$.

Since $`𝒜`$ has no labels involving $`D_x`$, the existence of such a path depends only on $`p`$, $`q`$, and the label of the inedge to the leaf of $`T`$. It follows that there is a universal bound on the undirected distance between $`(p,T)`$ to $`(q,T)`$ whenever $`(p,T)(q,T)`$. We denote the equivalence class of $`(p,T)`$ by $`([p],T)`$ since $`T`$ is constant throughout the class. This is an abuse of notation, since $`[p]`$ depends on $`T`$. We console ourselves with the hope that $`T`$ will be clear from context.

Project $`𝒜`$ to the graph $`\overline{𝒜}`$ whose vertices are equivalence classes of $``$ with distinct classes joined by an unoriented edge if there is an edge between any two vertices in the preimages of the classes. In the case where an edge of $`𝒜`$ connects a vertex to itself, we project that edge of $`𝒜`$ to the image of its endpoints in $`\overline{𝒜}`$. We have seen that there is a universal bound on the size of $`([p],T)`$. It follows that the quotient map is a quasi–isometry. We will show that $`\overline{𝒜}`$ has no simple cycles and is therefore a tree.

Suppose to the contrary that there is a simple cycle in $`\overline{𝒜}`$. Since $`\overline{𝒜}`$ has no loops and at most one edge between any two vertices, this cycle must have length at least three. We examine the cycle at a place where $`T`$ has maximal size. Either there is a single edge between distinct vertices $`([p],T)`$ and $`([q],T)`$, or there are two edges connecting distinct vertices $`([p],T^{})`$, $`([q],T^{})`$ with $`T^{}`$ a proper prefix of $`T`$ to a vertex $`([r],T^{})`$. The vertices $`([p],T^{})`$ and $`([q],T^{})`$ have the same memory tree because their memory trees are shorter than $`T`$ but derived from $`T`$ by popping a single element.

In the first case, there is an edge in $`𝒜`$ between $`(p^{},T)`$ and $`(q^{},T)`$ for some $`p^{}[p]`$ and $`q^{}[q]`$. Consequently $`([p],T)=([q],T)`$, and we have a contradiction. In the second case there is an undirected path from $`(p^{},T^{})`$ to $`(q^{},T^{})`$ along which each memory tree is an initial segment of $`T`$. Hence $`([p],T^{})=([q],T^{})`$, and our cycle is not simple. It follows that $`\overline{𝒜}`$ is a tree. ∎

Notice that the proof above does not work for the usual kind of pushdown automata which allowed to push a string of letters onto the stack on one move. Our pushdown automata are restricted to pushing one symbol at a time. However is easy to simulate a more general automaton by adding internal states to obtain one of ours, and it is straightforward to show that the configuration graphs of the two machines are quasi–isometric. Thus the result above holds for standard pushdown automata.

Theorem 4.6 provides another way of proving the result of Muller and Schupp. For we now have the configuration graph $`𝒜`$ mapping to the Cayley graph $`𝒢`$ and quasi–isometrically to a tree $`T`$. The lifting properties quickly show that $`𝒢`$ is not one–ended and one proceeds as before. This points up a difference between our result and that of Muller and Schupp. In the case of pushdown automata, the treeness — and therefore, the freeness — are already implicit in the class of machines. In the case of nested stack automata, the freeness is a result of the class of automata together with the fact that they are being used to solve the word problem.

## 5. Proof of Theorem 1.3

Suppose that $`\phi :GG^{}`$ is a quasi–isometry of groups and that $`G^{}`$ is narrow. It suffices to show that $`G`$ is narrow too. Pick a ball $`BG`$ of radius $`r`$ and let $`\overline{B}`$ be its image in $`G^{}`$. By Definition 2.1 $`\overline{B}`$ lies in a ball $`C`$ of radius $`k(r+1)`$. Since $`G^{}`$ is narrow, there is an integer $`i`$ such that all but finitely many balls $`C_j^{}G^{}`$ of radius $`k(r+1)`$ are separated from $`C`$ by $`i`$ points.

It follows from Definition 2.1 that $`\phi `$ is uniformly finite to one. Consequently the preimage in $`G`$ of the union of the balls $`C_j^{}`$ not satisfying the separation condition is finite. Thus with a finite number of exceptions every ball $`B^{}G`$ of radius $`r`$ has an image which lies in a ball $`C^{}`$ separated from $`C`$ by a set $`S`$ of size $`i`$.

The image under $`\phi `$ of any path from $`B`$ to $`B^{}`$ is a sequence of points from $`C`$ to $`C`$ with each point a distance at most $`2k`$ from its successor. Add points to obtain a path from $`C`$ to $`C^{}`$ and observe that this path must intersect $`S`$. It follows that at least one of the original image points is a distance at most $`k`$ from $`S`$. In other words the preimage in $`G`$ of all points within $`k`$ of $`S`$ disconnects $`B`$ and $`B^{}`$. Since $`\phi `$ is uniformly finite to one, we are done.

## 6. Proof of Theorem 1.4

We must prove the following three implications:

1. A group which is wide is not virtually free.
2. A group which is not virtually free has a one–ended subgroup.
3. A group with a one–ended subgroup is wide.

The first of these follows from the discussion immediately following the statement of the Theorem, and the second is a consequence of Lemma 2.2. Thus it remains only to prove that if $`G`$ contains a one–ended subgroup, then it is wide. Choose generators for $`G`$ which contain generators of the subgroup; then it follows immediately from Definition 1.2 that if $`G`$ is narrow, so is the subgroup. Conversely if the subgroup is wide, so is $`G`$. Thus it suffices to prove that a one–ended group is wide.

Suppose to the contrary that $`G`$ is one–ended and narrow. Assume we can choose the sets $`S`$ in Definition 1.2 so that the distance between any two points in $`S`$ is uniformly bounded. It follows from the fact that $`G`$ acts transitively and isometrically on itself by left translation that up to the action of $`G`$ there are only finitely many different $`S`$’s. Thus at least one $`S`$ separates pairs of balls of arbitrarily large radius whence $`GS`$ has at least two infinite connected components contrary to the hypothesis that $`G`$ is one–ended.

We complete the proof by showing that we can choose the sets $`S`$ as required. Observe that since $`G`$ is one–ended and of bounded valence, $`G\{1\}`$ has one infinite component and finitely many finite ones. Some ball $`C`$ of radius at least 1 around $`1`$ contains all the finite components, and any two vertices on the boundary of $`C`$ are joined by a path lying entirely in the infinite component. Pick one such path for each pair of vertices on the boundary of $`C`$, and pick a ball $`D`$ around $`1`$ containing $`C`$ and all these paths. Let $`D`$ have radius $`d`$. It is clear from Definition 1.2 that we may assume the balls to be separated are of radius greater than $`d`$.

It does no harm to restrict attention to sets $`S`$ which are minimal with respect to inclusion, and we do so. Pick balls $`B`$ and $`B^{}`$ of radius greater than $`d`$ and separated by a set $`S`$. Suppose $`S`$ contains a point $`v`$ at a distance greater than $`d`$ from all other points of $`S`$. Without loss of generality we assume this vertex is $`1`$ whence $`DS=\{1\}`$.

By minimality of $`S`$ there is a path $`\gamma `$ from from $`B`$ to $`B^{}`$ with $`\gamma S=\{1\}`$. If $`\gamma `$ starts outside $`C`$, define $`\gamma _1`$ to be the initial segment of $`\gamma `$ from $`B`$ to a point $`x`$ on the boundary of $`C`$. Otherwise $`BC`$ is not empty; and because $`B`$ is connected and larger than $`C`$, there is a point $`x`$ in $`B`$ and on the boundary of $`C`$. In this case define $`\gamma _1`$ to be the path of length zero from $`x`$ to itself. In both cases $`\gamma _1`$ goes from $`B`$ to a point $`x`$ on the boundary of $`C`$ and intersects $`S`$ trivially. Define $`\gamma _3`$ similarly from a point $`y`$ on the boundary of $`C`$ to $`B^{}`$, and let $`\gamma _2`$ be a path from $`x`$ to $`y`$ lying in $`D\{1\}`$. Clearly $`\gamma _1\gamma _2\gamma _3`$ is a path from $`B`$ to $`B^{}`$ intersecting $`S`$ trivially. Hence $`S`$ cannot have a point $`v`$ a distance greater than $`d`$ from all other points of $`S`$. Since the sets $`S`$ have uniformly bounded size, we are done.

## 7. Proof of Theorem 1.1

Suppose that the word problem of $`G`$ is accepted by a deterministic nested stack automaton with limited erasing $`A`$ with $`q`$ states and limited erasing constant $`K`$. To prove Theorem 1.1 it is enough to show that $`G`$ is narrow. Recall that the configuration graph $`𝒜`$ of $`A`$ projects onto the Cayley diagram $`𝒢`$ of $`G`$ where $`𝒢`$ is augmented by the addition of edge with label $`ϵ`$ from every vertex to itself. For any constant $`C`$ there are only finitely many vertices in $`𝒜`$ with memory tree of at most $`C`$ edges. Thus for any element $`gG`$ far enough away from $`1`$ every vertex $`𝒜`$ projecting to $`g`$ has memory tree with at least $`C`$ edges.

By the action of $`G`$ we may take $`B`$ to be a ball around $`1`$; and by discarding only finitely many possiblities for $`B^{}`$ we may assume that the center of $`B^{}`$ is an element $`g`$ far enough away from $`1`$ so that every vertex in the preimage in $`A`$ of $`g`$ has a memory tree with at least $`2Kr+1`$ edges. If necessary move $`g`$ farther away so that $`B`$ and $`B^{}`$ are a distance at least 2 from each other.

Fix a path $`\gamma `$ from $`1`$ to $`g`$ in $`𝒢`$. By Lemma 4.5 there is a unique shortest path $`\widehat{\gamma }`$ beginning at the initial vertex $`(q_0,T_0)`$ of $`A`$ and projecting to $`\gamma `$. By choice of $`g`$, $`\widehat{\gamma }`$ ends at $`(q,T)`$ for some memory tree with at least $`2Kr+3`$ edges. Recall that the edges of $`T`$ are ordered, and let $`T^{}`$ be the tree obtained by removing the $`Kr+1`$ latest edges and taking the latest remaining vertex as distinguished. We claim that the images in $`G`$ of all vertices of the form $`(q^{},T^{})`$ separate $`B`$ and $`B^{}`$.

It suffices to show that any path beginning at the boundary of $`B^{}`$ and ending at the boundary of $`B`$ contains one of the desired vertices. Extend such a path by geodesics of length $`r`$ to a path $`\gamma _1`$ from $`g`$ to $`1`$ in $`G`$, and consider the cycle $`\gamma \gamma _1`$. As the label $`w`$ of this cycle represents the identity in $`G`$, there must be a path in $`𝒜`$ from $`(q_0,T_0)`$ to a vertex $`(q_1,T_0)`$ with label $`w`$ and $`q_1`$ a final state. Our choice of $`\widehat{\gamma }`$ insures that $`\widehat{\gamma }`$ is a prefix of this path. Consequently there is a path $`\widehat{\gamma _1}`$ from $`(q,T)`$ to $`(q_1,T_0)`$ projecting to $`\gamma _1`$.

Since $`A`$ is limited erasing, the initial and terminal segments of $`\widehat{\gamma _1}`$ projecting to the geodesic segments at the ends of $`\gamma `$ have length at most $`Kr`$. It follows at most $`Kr+1`$ edges of $`T`$ can be deleted along each of these initial and terminal segments. Since edges must be deleted in order, it follows that there is an edge not in these segments with label $`(q^{},T^{})`$.