This version of the contribution has been accepted for publication, after peer review but is not the
Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version ofRecord is available at: http://dx.doi.org/10.1007/978-3-031-33264-7_20. Use of this Accepted Version
is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/
open-research/policies/accepted-manuscript-terms.

Groups whose word problems are accepted byabelian G-automata
Takao Yuyama
Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japanyuyama@kurims.kyoto-u.ac.jp

Abstract. Elder, Kambites, and Ostheimer showed that if a finitely
generated group H has word problem accepted by a G-automaton for
an abelian group G, then H has an abelian subgroup of finite index.
Their proof is, however, non-constructive in the sense that it is by contradiction: they proved that H must have a finite index abelian subgroup
without constructing any finite index abelian subgroup of H. In addition,a part of their proof is in terms of geometric group theory, which makes
it hard to read without knowledge of the field.
We give a new, elementary, and in some sense more constructive proofof the theorem, in which we construct, from the abelian G-automaton
accepting the word problem of H, a group homomorphism from a subgroup of G onto a finite index subgroup of H. Our method is purely
combinatorial and contains no geometric arguments.
Keywords: word problem · G-automaton · abelian group.

1

Introduction

For a group G, a G-automaton is a variant of usual finite state automata, which
is augmented with a memory register that stores an element of G. During thecomputation of a G-automaton, the content of the register may be updated
by multiplying on the right by an element of G, but cannot be seen. Such an
automaton first initializes the register with the identity element 1G of G, andthe automaton accepts an input word if, by reading this word, it can reach aterminal state, in which the register content is 1G . (For the precise definition,see Section 2.4.) For a positive integer n, Zn -automata are the same as blind ncounter automata, which were defined and studied by Greibach [14,15]. Note thatthe notion of G-automata is discovered repeatedly by several different authors.
The name “G-automaton” is due to Kambites [22]. (In fact, they introduced thenotion of M -automata for any monoid M .) Render–Kambites [31] uses G-valence
automata and Dassow–Mitrana [8] and Mitrana–Stiebe [26] use extended finite
automata (EFA) over G instead of G-automata.

2

T. Yuyama

For a finitely generated group H, the word problem of H, with respect to a
fixed finite generating set of H, is the set of words over the generating set representing the identity element of H (see Section 2.2 for the precise definitions).
For several language classes, the class of finitely generated groups whose word
problem is in the class has been determined [1,27,2,17,10,19,28], and many attempts are made for other language classes [3,4,20,12,24,21,25,13,30]. One of themost remarkable theorems about word problems is the well-known result due to
Muller and Schupp [27], which states that, with the theorem by Dunwoody [9],a group has a context-free word problem if and only if it is virtually free, i.e.,
has a free subgroup of finite index. These theorems suggest deep connections
between group theory and formal language theory.
Involving both G-automata and word problems, the following broad question was posed implicitly by Elston and Ostheimer [11] and explicitly by Kambites [22].
Question 1. For a given group G, is there any connection between the structuralproperty of G and of the collection of groups whose word problems are acceptedby non-deterministic G-automata?
Note that by G-automata, we always mean non-deterministic G-automata inthis paper. As for deterministic G-automata, the following theorem is known.
Theorem 1 (Kambites [22, Theorem 1], 2006). Let G and H be groups
with H finitely generated. Then the word problem of H is accepted by a deterministic G-automaton if and only if H has a finite index subgroup which embeds
in G.
For non-deterministic G-automata, several results are known for specific types ofgroups. For a free group F of rank ≥ 2, it is known that a language is accepted by
an F -automaton if and only if it is context-free (essentially by [5, Proposition2], see also [7, Corollary 4.5] and [23, Theorem 7]). Combining with the Muller–
Schupp theorem, the class of groups whose word problems are accepted by F automata is the class of virtually free groups. The class of groups whose word
problems are accepted by (F × F )-automata is exactly the class of recursively
presentable groups [7, Corollary 3.5][23, Theorem 8][26, Theorem 10].
For the case where G is (virtually) abelian, the following result was shown
by Elder, Kambites, and Ostheimer. Recall that a group G is called virtuallyabelian if it has an abelian subgroup of finite index.
Theorem 2 (Elder, Kambites, and Ostheimer [10], 2008).
(1) Let H be a finitely generated group and n be a positive integer. Then the word
problem of H is accepted by a Zn -automaton if and only if H is virtually freeabelian of rank at most n [10, Theorem 1].
(2) Let G be a virtually abelian group and H be a finitely generated group. Thenthe word problem of H is accepted by a G-automaton if and only if H has afinite index subgroup which embeds in G [10, Theorem 4].

Groups whose word problems are accepted by abelian G-automata

3

However, their proof is non-constructive in the sense that it is by contradiction:
they proved that H must have a finite index abelian subgroup without constructing any finite index abelian subgroup of H. In addition, their proof depends ona deep theorem in geometric group theory due to Gromov [16], which statesthat every finitely generated group with polynomial growth function is virtuallynilpotent.
The proof of Theorem 2 in [10] proceeds as follows. Let H be a finitely generated group whose word problem is accepted by a Zn -automaton. First, sometechniques to compute several bounds for linear maps and semilinear sets aredeveloped. Then a map from H to Zn with some geometric conditions is constructed to prove that H has polynomial growth function. By Gromov’s theorem,
H is virtually nilpotent. Finally, it is proved that H is virtually abelian, using
some theorems about nilpotent groups and semilinear sets. Theorem 2 (2) isdeducible from Theorem 2 (1). Because of the non-constructivity of the proof,
the embedding in Theorem 2 (2) is obtained only a posteriori and hence has
nothing to do with the G-automaton.
To our knowledge, there are almost no attempts so far to obtain explicit algebraic connections between G and H, where H is a finitely generated group withword problem accepted by a G-automaton. The only exception is the result due
to Holt, Owens, and Thomas [19, Theorem 4.2], where they gave a somewhat
combinatorial proof to a special case of Theorem 2 (1), for the case where n = 1.
(In fact, their theorem is slightly stronger than Theorem 2 (1) for n = 1 because
it is for non-blind one-counter automata. See also [10, Section 7].) However, their
proof also involves growth functions.
In this paper, we give an elementary, purely combinatorial proof of the following our main theorem, which is equivalent to Theorem 2 (see Section 3).
Theorem 3. Let G be an abelian group and H be a finitely generated group.
Suppose that the word problem of H is accepted by a G-automaton. Then there
exists a group homomorphism from a subgroup of G onto a finite index subgroupof H.
Our proof of Theorem 3 proceeds as follows. Suppose that the word problem
of a finitely generated group H is accepted by a G-automaton A, where G isan abelian group. First, we prove that there exist only finitely many minimal
accepting paths in A. Next, for each vertex p of A and each minimal accepting
path µ in A, we define a set M (µ, p) of closed paths that is pumpable in µand starts from p, and prove that each M (µ, p) forms a monoid with respect
to concatenation. Then, we show that each monoid M (µ, p) induces a grouphomomorphism fµ,p from a subgroup G(µ, p) of G onto a subgroup H(µ, p) of
H. Finally, we show that at least one of the H(µ, p)’s has finite index in H.
In addition to this introduction, this paper comprises four sections. Section 2
provides necessary preliminaries, notations, and conventions. In Section 3, wereduce Theorem 2 to Theorem 3 and vice versa. Section 4 is devoted to theproof of Theorem 3. Section 5 concludes the paper.

4

T. Yuyama

2

Preliminaries

2.1

Words, subwords, and scattered subwords

For a set Σ, we write Σ ∗ for the free monoid generated by Σ, i.e., the set ofwords over Σ. For a word u = a1 a2 · · · an ∈ Σ ∗ (n ≥ 0, ai ∈ Σ), the number n
is called the length of u, which is denoted by |u|. For two words u, v ∈ Σ ∗ , theconcatenation of u and v are denoted by u · v, or simply uv. The identity elementof Σ ∗ is the empty word, denoted by ε, which is the unique word of length zero.
For an integer n ≥ 0, the n-fold concatenation of a word u ∈ Σ ∗ is denoted by
un . For an integer n > 0, we write Σ <n for the set of words of length less thann.
A word u ∈ Σ ∗ is a subword of a word v ∈ Σ ∗ , denoted by u ⊑ v, if
there exist two words u1 , u2 ∈ Σ ∗ such that u1 uu2 = v. A word u ∈ Σ ∗ is ascattered subword of a word v ∈ Σ ∗ , denoted by u ⊑sc v, if there exist two finite
sequences of words u1 , u2 , . . . , un ∈ Σ ∗ (n ≥ 0) and v0 , v1 , . . . , vn ∈ Σ ∗ such thatu = u1 u2 · · · un and v = v0 u1 v1 u2 v2 · · · un vn . That is, v is obtained by insertingsome words in u. Note that the two binary relations ⊑ and ⊑sc are both partial
orderings on Σ ∗ .
2.2

Word problem for groups

Let H be a finitely generated group. A choice of generators for H is a surjective
monoid homomorphism ρ from the free monoid Σ ∗ , on a finite alphabet Σ,
onto H. The word problem of H with respect to ρ, denoted by WPρ (H), is
the set of words in Σ ∗ mapped to the identity element 1H of H via ρ, i.e.,
WPρ (H) = ρ−1 (1H ).
Although the word problem WPρ (H) depends on the choice of generators ρ,
this does not cause problems, at least for our purpose:
Proposition 1 (e.g., [20, Lemma 1]). Let C be a class of languages closed
under inverse homomorphisms and let H be a finitely generated group. Then
WPρ (H) ∈ C for some choice of generators ρ if and only if WPρ (H) ∈ C for
every choice of generators ρ.
⊔⊓
Therefore we usually say “the word problem of H” rather than “a word problemof H.”
2.3

Graphs and paths

A graph is a 4-tuple (V, E, s, t), where V is the set of vertices, E is the set of(directed) edges, s : E → V and t : E → V are functions assigning to every edgee ∈ E the source s(e) ∈ V and the target t(e) ∈ V , respectively. A graph is finite
if it has only finitely many vertices and edges.
A path (of length n) in a graph Γ = (V, E, s, t) is a word e1 e2 · · · en ∈ E ∗ (n ≥0) of edges ei ∈ E such that t(ei ) = s(ei+1 ) for i = 1, 2, . . . , n − 1. We usually use
Greek letters for paths in a graph. For a non-empty path ω = e1 e2 · · · en ∈ E ∗ ,Groups whose word problems are accepted by abelian G-automata

5the source and the target of ω are defined as s(ω) = s(e1 ) and t(ω) = t(en ),respectively. If ω = e1 e2 · · · en and ω ′ = e′1 e′2 · · · e′k are non-empty paths suchthat t(ω) = s(ω ′ ), or at least one of ω and ω ′ is empty, then the concatenationof ω and ω ′ , denoted by ω · ω ′ or ωω ′ , is the path e1 e2 · · · en e′1 e′2 · · · e′k of lengthn + k, i.e., the concatenation as words. A path ω in Γ is closed if s(ω) = t(ω),
or ω = ε. For a closed path σ and an integer n ≥ 0, we write σ n for the n-foldconcatenation of σ.
For a graph Γ = (V, E, s, t), an edge-labeling function is a function ℓ from E
to a set M . If M is a monoid and ω = e1 e2 · · · en ∈ E ∗ is a path in Γ , then thelabel of ω is defined as ℓ(ω) = ℓ(e1 )ℓ(e2 ) · · · ℓ(en ) via the multiplication of M .
2.4

G-automata

For a group G, a (non-deterministic) G-automaton over a finite alphabet Σ isdefined as a 5-tuple (Γ, ℓG , ℓΣ , pinit , pter ), where Γ = (V, E, s, t) is a finite graph,ℓG : E → G and ℓΣ : E → Σ ∗ are edge-labeling functions, pinit ∈ V is theinitial vertex, and pter ∈ V is the terminal vertex. For simplicity, we assume thatℓΣ (e) ∈ Σ ∪ {ε} for each e ∈ E. (Note that this assumption does not decrease
the accepting power of G-automata. Indeed, if necessary, one can subdivide anedge e with labels ℓΣ (e) = uv, ℓG (e) = g into two new edges e1 , e2 with labelsℓΣ (e1 ) = u, ℓG (e1 ) = g and ℓΣ (e2 ) = v, ℓG (e2 ) = 1G .) An accepting path in a
G-automaton A = (Γ, ℓG , ℓΣ , pinit , pter ) is a path α in Γ such that s(α) = pinit ,t(α) = pter , and ℓG (α) = 1G (we consider that the empty path ε ∈ E ∗ isaccepting if and only if pinit = pter ). We say that a path ω in Γ is promising if ω
is a subword of some accepting path in A, i.e., there exist two paths ω1 , ω2 ∈ E ∗such that the concatenation ω1 ωω2 ∈ E ∗ is an accepting path in A. The language
accepted by a G-automaton A, denoted by L(A), is the set of all words u ∈ Σ ∗such that u is the label of some accepting path in A, i.e.,
L(A) = { ℓΣ (α) ∈ Σ ∗ | α is an accepting path in A }.
We say that a G-automaton A is abelian if G is an abelian group.
The class of languages accepted by G-automata satisfies the assumption of
Proposition 1:
Proposition 2 (e.g., [23, Proposition 2]). For a group G, the class of languages accepted by G-automata is closed under inverse homomorphisms.
⊔⊓
Therefore one can speak of a group H whose word problem is accepted by a
G-automaton without any reference to generating set for H.

3

Equivalence of Theorem 3 and Theorem 2

Proposition 3. Theorem 3 implies Theorem 2.
Proof. Since Theorem 2 (2) is deducible from Theorem 2 (1) [10, Section 6], it
suffices to show Theorem 2 (1). If H is a finitely generated group and Zm is6

T. Yuyamaa finite index subgroup of H for some m ≤ n, then one can easily construct a
Zn -automaton that accepts the word problem of H (see e.g., [11, Theorem 7]).
Conversely, suppose that the word problem of H is accepted by a Zn -automaton.
By Theorem 3, there exists a group homomorphism f from a subgroup G0 of Zn
onto a finite index subgroup H0 of H. In general, a subgroup S of a free abeliangroup F is also free abelian, and the rank of S does not exceed that of F (seee.g., [32, 4.2.3]). Thus G0 ∼= Zm for some m ≤ n. Since H0 is a homomorphicmimage of Z , H0 is an abelian group generated by at most m elements. Hence,by the fundamental theorem of finitely generated abelian groups (see e.g., [32,4.2.10]), H0 has a finite index subgroup isomorphic to Zk for some k ≤ m. Thus
H has a finite index subgroup isomorphic to Zk .
⊔⊓Proposition 4. Theorem 2 implies Theorem 3.
Proof. Suppose that the word problem of a finitely generated group H is accepted by a G-automaton A, where G is an abelian group. By Theorem 2 (2),there exist a finite index subgroup H0 of H and an embedding f : H0 → G. Since
f is injective, the homomorphism f −1 : f (H0 ) → H0 is the desired one.

4

Proof of Theorem 3

Throughout this section, we fix an abelian group G, a finitely generated group
H, a choice of generators ρ : Σ ∗ → H, and an abelian G-automaton A = (Γ =(V, E, s, t), ℓG , ℓΣ , pinit , pter ) such that WPρ (H) = L(A). We write the group
operation of G additively and write 0G for the identity element of G.
4.1

Minimal accepting paths

The minimal accepting paths, defined below, play a central role in this paper.
Definition 1. An accepting path α in A is minimal if it is minimal with respect to the scattered subword relation ⊑sc on E ∗ among the accepting paths. An
accepting path α in A dominates a minimal accepting path µ in A if µ ⊑sc α.
A similar notion of minimal accepting paths can be found in [6, Section 4].
Proposition 5 (Higman’s lemma [18, Theorem 4.4]). For any finite
alphabet Σ, the scattered subword relation ⊑sc on Σ ∗ is a well-quasi-order, i.e.,
for any infinite sequence u1 , u2 , . . . ∈ Σ ∗ , there exist some i < j such thatui ⊑sc uj .
⊔⊓Corollary 1. There are only finitely many minimal accepting paths in A, andevery accepting path on A dominates some minimal accepting path in A.
Proof. Suppose the contrary that there are infinitely many distinct minimal
accepting paths µ1 , µ2 , . . . ∈ E ∗ . Then we have µi ̸⊑sc µj for any i < j becauseof the minimality of µj , a contradiction. The second half of the lemma is also
true since a well-quasi-ordered set admits no infinite descending sequence.
⊔⊓
Note that if pinit = pter then the only minimal accepting path is the empty pathε.

Groups whose word problems are accepted by abelian G-automata

4.2

7

Pumpable paths and the monoids M (µ, p)

Definition 2. Let µ = e1 e2 · · · en ∈ E ∗ (ei ∈ E) be a minimal accepting pathin A. A closed path σ ∈ E ∗ in Γ is pumpable in µ if there exists an accepting path α in A dominating µ such that α = α0 e1 α1 e2 · · · en αn for some paths
α0 , α1 , . . . , αn ∈ E ∗ in Γ and σ ⊑ αj for some j ∈ {0, 1, . . . , n}.
Remark 1.
(1) In Definition 2, each αi inserted to µ is a closed path in Γ . In addition,ℓG (α0 ) + ℓG (α1 ) + · · · + ℓG (αn ) = 0G since G is abelian and ℓG (α) = ℓG (µ) =0G .
(2) Every closed path σ pumpable in a minimal accepting path µ is promising since σ is a subword (not a scattered subword) of an accepting path α
dominating µ.
Definition 3. For a minimal accepting path µ in A and a vertex p ∈ V , define()∗ σ is a closed path in Γ pumpable in µ
M (µ, p) = σ ∈ E.
such that s(σ) = p, or σ = εNote that there are only finitely many M (µ, p)’s by Corollary 1.
Lemma 1. Each M (µ, p) is a monoid with respect to the concatenation operation, i.e., σ1 , σ2 ∈ M (µ, p) implies σ1 σ2 ∈ M (µ, p).
Proof. Since both σ1 and σ2 are pumpable in µ = e1 e2 · · · en ∈ E ∗ (ei ∈ E),
there exist two accepting paths α = α0 e1 α1 e2 · · · en αn (αi ∈ E ∗ ) and β =β0 e1 β1 e2 · · · en βn (βi ∈ E ∗ ) such that σ1 ⊑ αi and σ2 ⊑ βj for some i, j ∈{0, 1, . . . , n}. Then we have αi = αi′ σ1 αi′′ for some αi′ , αi′′ ∈ E ∗ and βj = βj′ σ2 βj′′
for some βj′ , βj′′ ∈ E ∗ . We may assume that i ≤ j. Since G is abelian, the merged
path γ = (α0 β0 )e1 (α1 β1 )e2 · · · en (αn βn ) and its permutation
γ ′ = (α0 β0 )e1 (α1 β1 )e2 · · · ei (αi′ σ1 σ2 αi′′ βi )ei+1 · · · ej (αj βj′ βj′′ )ej+1 · · · en (αn βn )(1)
are accepting paths in A by Remark 1 (1) (Figure 1).
⊔⊓
Lemma 2. Let σ and τ be closed paths in Γ such that s(τ ) = p (or τ = ε) andτ ⊑sc σ ∈ M (µ, p). Then τ ∈ M (µ, p).
Proof. Suppose that τ = e′1 e′2 · · · e′k (k ≥ 0, e′i ∈ E) and σ = σ0 e′1 σ1 e′2 · · · e′k σk(σi ∈ E ∗ ). Note that each σi is a closed path in Γ . Since, by Lemma 1, σ 2 ispumpable in µ = e1 e2 · · · en (n ≥ 0, ei ∈ E), there exists an accepting path α =α0 e1 α1 e2 · · · en αn dominating µ such that σ 2 ⊑sc αi for some i ∈ {0, 1, . . . , n}.
If αi = αi′ σ 2 αi′′ , then the path
α0 e1 α1 e2 · · · ei (αi′ · τ · (σ02 e′1 σ12 e′2 · · · e′k σk2 ) · αi′′ )ei+1 · · · en αnis an accepting path in A by Remark 1 (1) (Figure 2).

(2)
⊔
⊓

8

T. Yuyama






µ=





σ1





σ2







, α = 





αi′





, β = 





βj′′







αi′′







⇝ γ=



βj′









 ⇝ γ′ = 











Fig. 1. Construction of the accepting path γ ′ in (1)


σ=







2
⇝σ =











⇝ τ · (σ02 e′1 σ12 e′2 · · · e′k σk2 ) = 












, τ = Fig. 2. Construction of the path τ · (σ02 e′1 σ12 e′2 · · · e′k σk2 ) in (2)Lemma 3. Let σ ∈ M (µ, p) and ω ⊑ σ be a path. Then there exist two paths
ω1 , ω2 ∈ E <|V | such that ω1 ωω2 ∈ M (µ, p).
Proof. Let (ω1 , ω2 ) ∈ E ∗ × E ∗ be a pair of two paths such that ω1 ωω2 ∈ M (µ, p)
and max{|ω1 |, |ω2 |} is minimum. Such a pair exists since ω ⊑ σ ∈ M (µ, p). Suppose the contrary that max{|ω1 |, |ω2 |} ≥ |V |, say |ω1 | ≥ |V |. By the pigeonhole
principle, ω1 must visit some vertex p ∈ V at least twice. That is, there exist
three paths α, β, γ such that ω1 = αβγ and β is a non-empty closed path. Now
we have αγωω2 ⊑sc ω1 ωω2 ∈ M (µ, p), and Lemma 2 implies αγωω2 ∈ M (µ, p),which contradicts the minimality of (ω1 , ω2 ).
⊔⊓4.3

Group homomorphisms fµ,p from G(µ, p) onto H(µ, p)

For each M (µ, p), Lemma 1 allows us to define a surjective monoid homomorphism φµ,p : M (µ, p) → ρ(ℓΣ (M (µ, p))) as the composition function ρ ◦ℓΣ . Then each φµ,p induces a well-defined surjective monoid homomorphism
φ̄µ,p : ℓG (M (µ, p)) → ρ(ℓΣ (M (µ, p))) thanks to the following Lemma 4.
Lemma 4. Let ω and ω ′ be paths in Γ such that s(ω) = s(ω ′ ) and t(ω) = t(ω ′ ),and suppose that ω is promising. Then ℓG (ω) = ℓG (ω ′ ) implies ρ(ℓΣ (ω)) =ρ(ℓΣ (ω ′ )).

Groups whose word problems are accepted by abelian G-automata

9

Proof. Since ω is promising, there exist two paths ω1 , ω2 in Γ such that ω1 ωω2is an accepting path in A. From the assumption ℓG (ω) = ℓG (ω ′ ), we haveℓG (ω1 ω ′ ω2 ) = ℓG (ω1 ωω2 ) = 0G and hence ω1 ω ′ ω2 is also an accepting pathin A. That is, ℓΣ (ω1 ωω2 ), ℓΣ (ω1 ω ′ ω2 ) ∈ L(A) ⊆ WPρ (H) and henceρ(ℓΣ (ω1 ))ρ(ℓΣ (ω))ρ(ℓΣ (ω2 )) = 1H = ρ(ℓΣ (ω1 ))ρ(ℓΣ (ω ′ ))ρ(ℓΣ (ω2 )).
Since H is cancellative, we have ρ(ℓΣ (ω)) = ρ(ℓΣ (ω ′ )).

⊔⊓Let G(µ, p) (resp. H(µ, p)) denote the subgroup of G generated by ℓG (M (µ, p))(resp. the subgroup of H generated by ρ(ℓΣ (M (µ, p)))).
Lemma 5. One can extend φ̄µ,p : ℓG (M (µ, p)) → ρ(ℓΣ (M (µ, p))) to a uniquesurjective group homomorphism fµ,p : G(µ, p) → H(µ, p).
Proof. Since G is an abelian group, every element g ∈ G(µ, p) can be written as
g = ℓG (σ1 ) − ℓG (σ2 ) for some σ1 , σ2 ∈ M (µ, p). Defining fµ,p (g) = ρ(ℓΣ (σ1 )) −ρ(ℓΣ (σ2 )), one can easily check the well-definedness, the uniqueness, and thesurjectivity.
⊔⊓
4.4

One of the H(µ, p)’s has finite index in H

The remaining task is to prove that at least one of the H(µ, p)’s has finite index
in H. To do this, we use B. H. Neumann’s lemma in the following form.
Proposition 6 (B. H. Neumann’s lemma [29, (4.1) Lemma and (4.2)]).
Let H be a group, H1 , H2 , .S
. . , Hn be subgroups of H, and a1 , b1 , a2 , b2 , . . . , an , bnnbe elements of H. If H = i=1 ai Hi bi , then at least one of the Hi ’s is of index
at most n in H.
⊔⊓
Lemma 6. The following holds.
)([µ is a minimal accepting path in A,
−1
−1
.
H=
h1 H(µ, p)h2
p ∈ V , and h1 , h2 ∈ ρ(Σ <|V | )(3)

Proof. Let h ∈ H and fix a word v ∈ Σ ∗ such that ρ(v) = h. Since ρ is surjective,
there exists a word v̄ ∈ Σ ∗ such that ρ(v̄) = ρ(v)−1 . Define
N = 1 + max{ |µ| | µ ∈ E ∗ is a minimal accepting path in A },and we have N < ∞ by Corollary 1. Since (vv̄)N ∈ WPρ (H) ⊆ L(A), there
exists an accepting path
α = ω1 ω̄1 ω2 ω̄2 · · · ωN ω̄N(4)

in A such that ℓΣ (ωi ) = v and ℓΣ (ω̄i ) = v̄ for i = 1, 2, . . . , N . Let µ = e1 e2 · · · en(ei ∈ E) be a minimal accepting path such that α dominates µ. Then we haveanother decomposition
α = α0 e1 α1 e2 · · · en αn
(5)

10

T. Yuyama

for some closed paths α0 , α1 , . . . , αn ∈ E ∗ . Since N > |µ| = n and each ei in thedecomposition (5) is contained in at most one ωi in the decomposition (4), atleast one of the ωi ’s is “disjoint” from all ei ’s, i.e., there exist i ∈ {1, 2, . . . , N }and j ∈ {0, 1, . . . , n} such that ωi ⊑ αj . Since αj is a pumpable closed path inµ, we have αj ∈ M (µ, p), where p = s(αj ). By Lemma 3, there exist αj′ , αj′′ ∈E <|V | such that αj′ ωi αj′′ ∈ M (µ, p). Then we have |ℓΣ (αj′ )|, |ℓΣ (αj′′ )| < |V | andρ(ℓΣ (αj′ ))ρ(ℓΣ (ωi ))ρ(ℓΣ (αj′′ )) ∈ ρ(ℓΣ (M (µ, p))) ⊆ H(µ, p), henceh = ρ(v) = ρ(ℓΣ (ωi )) ∈ ρ(ℓΣ (αj′ ))−1 H(µ, p)ρ(ℓΣ (αj′′ ))−1 .
Thus (3) holds.

⊔⊓

Proof of Theorem 3. Since G is an abelian group and L(A) ⊆ WPρ (H), we havesurjective group homomorphisms fµ,p : G(µ, p) → H(µ, p) by Lemmata 4 and 5.
Since WPρ (H) ⊆ L(A), the equation (3) holds by Lemma 6, and the righthand side of (3) is a finite union of cosets of H by Corollary 1. Thus, by B. H.
Neumann’s lemma (Proposition 6), at least one of the H(µ, p)’s is of index at
most |{ µ | µ is a minimal accepting path in A }| × |V | × |Σ <|V | |2 in H.
⊔⊓

5

Conclusion

We gave a new, elementary, purely combinatorial proof of the theorem due to
Elder, Kambites, and Ostheimer, which states that if a finitely generated group
H has word problem accepted by an abelian G-automaton A, then H is virtuallyabelian. In contrast to their original geometric argument, we stuck to the combinatorial link—the abelian G-automaton A—between the two groups G and H,
and we obtained explicit algebraic connections between them as finitely manygroup homomorphisms fµ,p : G(µ, p) → H(µ, p).
We leave the following question as our future work.
Question 2. Let G and H be (not necessarily abelian) groups with H finitely
generated. Suppose that the word problem of H is accepted by a G-automaton.
Can one combinatorially obtain a group homomorphism from a subgroup of G
onto a finite index subgroup of H?
For example, how about the case where G is free or nilpotent? Our Theorem 3
is the very first step for approaching Question 2.
Acknowledgements The author would like to thank Ryoma Sin’ya (Akita University) for encouragement and helpful comments. They would also like to thankanonymous reviewers for many valuable comments. This work was supported by
JSPS KAKENHI Grant Numbers JP20J23039 and JP20H05961.

References
1. Anı̄sı̄mov, A.V.: Certain algorithmic questions for groups and context-free languages. Kibernetika (Kiev) (2), 4–11 (1972)

Groups whose word problems are accepted by abelian G-automata

11

2. Boone, W.W., Higman, G.: An algebraic characterization of groups with soluble
word problem. J. Austral. Math. Soc. 18, 41–53 (1974), collection of articles dedicated to the memory of Hanna Neumann, IX
3. Brough, T.: Groups with poly-context-free word problem. Groups Complex. Cryptol. 6(1), 9–29 (2014), https://doi.org/10.1515/gcc-2014-0002
4. Ceccherini-Silberstein, T., Coornaert, M., Fiorenzi, F., Schupp, P.E., Touikan,
N.W.M.: Multipass automata and group word problems. Theoret. Comput. Sci.
600, 19–33 (2015), https://doi.org/10.1016/j.tcs.2015.06.054
5. Chomsky, N., Schützenberger, M.P.: The algebraic theory of context-free languages.
In: Computer programming and formal systems, pp. 118–161. North-Holland, Amsterdam (1963)
6. Cleary, S., Elder, M., Ostheimer, G.: The word problem distinguishes counter languages (2006), https://arxiv.org/abs/math/0606415
7. Corson, J.M.: Extended finite automata and word problems. Internat. J. Algebra
Comput. 15(3), 455–466 (2005), https://doi.org/10.1142/S0218196705002360
8. Dassow, J., Mitrana, V.: Finite automata over free groups. Internat. J. Algebra
Comput. 10(6), 725–737 (2000), https://doi.org/10.1142/S0218196700000315
9. Dunwoody, M.J.: The accessibility of finitely presented groups. Invent. Math.
81(3), 449–457 (1985), https://doi.org/10.1007/BF01388581
10. Elder, M., Kambites, M., Ostheimer, G.: On groups and counter automata. Internat. J. Algebra Comput. 18(8), 1345–1364 (2008), https://doi.org/10.1142/
S0218196708004901
11. Elston, G.Z., Ostheimer, G.: On groups whose word problem is solved by a counter
automaton. Theoret. Comput. Sci. 320(2-3), 175–185 (2004), https://doi.org/10.
1016/j.tcs.2003.09.007
12. Gebhardt, K., Meunier, F., Salvati, S.: On is an n-MCFL. J. Comput. System Sci.
127, 41–52 (2022), https://doi.org/10.1016/j.jcss.2022.02.003
13. Gilman, R.H., Kropholler, R.P., Schleimer, S.: Groups whose word problems are
not semilinear. Groups Complex. Cryptol. 10(2), 53–62 (2018), https://doi.org/
10.1515/gcc-2018-0010
14. Greibach, S.A.: Remarks on the complexity of nondeterministic counter languages. Theoret. Comput. Sci. 1(4), 269–288 (1975/76), https://doi.org/10.1016/
0304-3975(76)90072-4
15. Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7(3), 311–324 (1978), https://doi.org/10.1016/
0304-3975(78)90020-8
16. Gromov, M.: Groups of polynomial growth and expanding maps. Inst. Hautes
Études Sci. Publ. Math. (53), 53–73 (1981), http://www.numdam.org/item?id=
PMIHES_1981__53__53_0
17. Higman, G.: Subgroups of finitely presented groups. Proc. Roy. Soc. London Ser.
A 262, 455–475 (1961), https://doi.org/10.1098/rspa.1961.0132
18. Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc.
(3) 2, 326–336 (1952), https://doi.org/10.1112/plms/s3-2.1.326
19. Holt, D.F., Owens, M.D., Thomas, R.M.: Groups and semigroups with a onecounter word problem. J. Aust. Math. Soc. 85(2), 197–209 (2008), https://doi.
org/10.1017/S1446788708000864
20. Holt, D.F., Rees, S., Röver, C.E., Thomas, R.M.: Groups with context-free coword problem. J. London Math. Soc. (2) 71(3), 643–657 (2005), https://doi.org/
10.1112/S002461070500654X
21. Holt, D.F., Röver, C.E.: Groups with indexed co-word problem. Internat. J. Algebra Comput. 16(5), 985–1014 (2006), https://doi.org/10.1142/S0218196706003359

12

T. Yuyama

22. Kambites, M.: Word problems recognisable by deterministic blind monoid automata. Theoret. Comput. Sci. 362(1-3), 232–237 (2006), https://doi.org/10.1016/
j.tcs.2006.06.026
23. Kambites, M.: Formal languages and groups as memory. Comm. Algebra 37(1),
193–208 (2009), https://doi.org/10.1080/00927870802243580
24. Kanazawa, M., Salvati, S.: MIX is not a tree-adjoining language. In: Proceedings of
the 50th Annual Meeting of the Association for Computational Linguistics (Volume
1: Long Papers). pp. 666–674. Association for Computational Linguistics, Jeju
Island, Korea (Jul 2012), https://aclanthology.org/P12-1070
25. Kropholler, R.P., Spriano, D.: Closure properties in the class of multiple contextfree groups. Groups Complex. Cryptol. 11(1), 1–15 (2019), https://doi.org/10.
1515/gcc-2019-2004
26. Mitrana, V., Stiebe, R.: Extended finite automata over groups. Discrete Appl.
Math. 108(3), 287–300 (2001), https://doi.org/10.1016/S0166-218X(00)00200-6
27. Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J. Comput. System Sci. 26(3), 295–310 (1983), https://doi.org/10.1016/
0022-0000(83)90003-X
28. Nesin, G.A.R., Thomas, R.M.: Groups whose word problem is a Petri net language. In: Descriptional complexity of formal systems, Lecture Notes in Comput. Sci., vol. 9118, pp. 243–255. Springer, Cham (2015), https://doi.org/10.1007/
978-3-319-19225-3_21
29. Neumann, B.H.: Groups covered by permutable subsets. J. London Math. Soc. 29,
236–248 (1954), https://doi.org/10.1112/jlms/s1-29.2.236
30. Nyberg-Brodda, C.F.: On the word problem for free products of semigroups andmonoids. J. Algebra 622, 721–741 (2023). https://doi.org/10.1016/j.jalgebra.2023.
02.007, https://doi.org/10.1016/j.jalgebra.2023.02.007
31. Render, E., Kambites, M.: Polycyclic and bicyclic valence automata. In: Language
and automata theory and applications, Lecture Notes in Comput. Sci., vol. 5196,
pp. 464–475. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-88282-4_
42, https://doi.org/10.1007/978-3-540-88282-4_42
32. Robinson, D.J.S.: A course in the theory of groups, Graduate Texts in Mathematics, vol. 80. Springer-Verlag, New York, second edn. (1996), https://doi.org/10.
1007/978-1-4419-8594-1