SOME DECISION PROBLEMS IN GROUP THEORY
by
Justin A. James
A DISSERTATION
Presented to the Faculty of
The Graduate College at the University of Nebraska
In Partial Fulfillment of Requirements
For the Degree of Doctor of Philosophy
Major: Mathematics
Under the Supervision of Professors Susan M. Hermiller and John C. Meakin
Lincoln, Nebraska
May, 2006
UMI Number: 3208081
3208081
2006
UMI Microform
Copyright
All rights reserved. This microform edition is protected against
unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company
300 North Zeeb Road
P.O. Box 1346
Ann Arbor, MI 48106-1346
by ProQuest Information and Learning Company.
SOME DECISION PROBLEMS IN GROUP THEORY
Justin A. James, Ph.D.
University of Nebraska, 2006
Advisors: Susan M. Hermiller and John C. Meakin
We give an algorithm deciding the generalized power problem for word hyperbolic
groups. Alonso, Brady, Cooper, Ferlini, Lustig, Mihalik, Shapiro, and Short showed
that elements of infinite order in word hyperbolic groups induce quasigeodesic rays in

the Cayley graph. We show that a pair of quasigeodesic rays induced by two elements
of infinite order either never meet at a vertex or intersect infinitely many times, and we
give an algorithm detecting which option occurs for a given pair of quasigeodesic rays.
Since solutions to the generalized power problem correspond to points of intersection
along these rays, this decides instances of the generalized power problem involving
elements of infinite order. For finite order instances, we use the algorithm deciding the
word problem in word hyperbolic groups finitely many times. We extend this result to
obtain an algorithm deciding membership in the product of two cyclic submonoids of
a word hyperbolic group. We also give an algorithm deciding membership in finitely
generated submonoids of the free product of two finitely presented groups, provided
there is an algorithm to decide membership in the rational subsets of each factor.
This extends a result of K. A. Mihailova, who proved that the uniform generalized
word problem is decidable in the free product of two groups if it is decidable in each
factor. Since rational membership is known to be decidable for free groups, free
abelian groups, virtually free groups, and virtually free abelian groups, our algorithm
can be used to decide membership in finitely generated submonoids of a free product
of groups with factors drawn from these classes of groups.
ACKNOWLEDGEMENTS
I would like to express my gratitude to my advisors, Dr. Susan Hermiller and Dr.
John Meakin, for the countless hours you spent in our weekly research meetings and
for the many ways you have helped me both personally and professionally during
my time at UNL. I especially want to thank Dr. Hermiller for the effort she put into
reading the drafts leading up to this final document. I would also like to thank the
other members of my supervisory committee: Dr. Mark Brittenham, Dr. Allan
Donsig, and Dr. David Swanson. I would particularly like to thank Dr. Brittenham
for his suggestions which improved the clarity of my proofs. I would also like to
thank Dr. Brittenham and Dr. Donsig for reading the penultimate draft and
providing many helpful comments. I am especially grateful for the camaraderie
among the graduate students at UNL. I would like to thank Josh Brown-Kramer,
Dr. Charles Cusack, Dr. Benton Duncan, Pari Ford, Mike Gunderson, Ned

Hummel, Eddie Loeb, Albert Luckas, Dr. Matt Koetz, and Jacob Weiss for their
friendship. You have enriched my life in innumerable ways. I would be remiss if I
failed to thank my friends in the UNL Navigators and at Oak Lake Evangelical Free
Church. Without your prayers and support, I would never have made it to this
point. You truly embody Romans 12:3-13. I would also like to thank my family:
Mom, Ron, Heather, Eddie, Lisa, Amity, and Eric. Your love and support mean
more to me than words are able to express. Lastly, I dedicate this dissertation to
the memory of my father, Tam T. James, and to my God and Savior, Jesus Christ.
“Blessed be the name of God forever and ever, to whom belong wisdom and might.
He changes times and seasons; he removes kings and sets up kings; he gives wisdom
to the wise and knowledge to those who have understanding; he reveals deep and
hidden things; he knows what is in the darkness, and the light dwells with him.”
Daniel 2:20b-22 (ESV)
Contents
1 Introduction 1
2 Preliminaries 7
2.1 Conventions and Notation . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Monoids and Groups . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Dehn’s Problems . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.3 Generalizations of the Word Problem . . . . . . . . . . . . . . 10
2.1.4 Cayley Graphs and Metric Spaces . . . . . . . . . . . . . . . . 13
2.1.5 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Languages and Automata . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Rational Subsets of Monoids . . . . . . . . . . . . . . . . . . . 17
2.2.2 Rational Problems . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.3 Algorithms in Free and Free Abelian Groups . . . . . . . . . . 20
2.2.4 Finite State Automata . . . . . . . . . . . . . . . . . . . . . . 21
3 Word Hyperbolic Groups 24
3.1 δ-hyperbolic Spaces and δ-hyperbolic Groups . . . . . . . . . . . . . . 25
3.2 Algorithms for δ-hyperbolic Groups . . . . . . . . . . . . . . . . . . . 29

3.2.1 The Word Problem . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.2 The Order Problem . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 The Power Problem and the Generalized
Power Problem in Word Hyperbolic Groups . . . . . . . . . . . . . . 32
3.3.1 Quasigeodesics and Quasiconvexity . . . . . . . . . . . . . . . 33
3.3.2 Arzel`a − Ascoli . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 Properties of Geodesic and Quasigeodesic Rays . . . . . . . . 40
3.3.4 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.5 Extending the Algorithm to decide {u}
∗
· {v}
∗
. . . . . . . . . . 59
4 Algorithms in Free Products of Groups 65
4.1 Free Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.1.1 Definition and the Word Problem . . . . . . . . . . . . . . . . 67
4.1.2 Cancellation Diagrams . . . . . . . . . . . . . . . . . . . . . . 71
4.2 The Uniform Submonoid Membership Problem . . . . . . . . . . . . . 76
4.2.1 The Automaton Construction . . . . . . . . . . . . . . . . . . 76
4.2.2 An Algorithm to Recognize Short Elements . . . . . . . . . . 81
4.2.3 Generating Set Completion . . . . . . . . . . . . . . . . . . . 93
Bibliography 104
List of Figures
2.1 A directed edge in a Cayley graph. . . . . . . . . . . . . . . . . . . . 14
2.2 The Cayley graph of the free group of rank two. . . . . . . . . . . . . 14
2.3 The Cayley graph of the free abelian group of rank two. . . . . . . . . 15
2.4 A - a non-deterministic finite state automaton with ǫ-transitions. . . 23
3.1 A δ-slim triangle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 A δ-thin triangle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Geodesics and quasigeodesics are Hausdorff close . . . . . . . . . . . . 35

3.4 A geodesic ray associated with a quasigeodesic ray . . . . . . . . . . . 41
3.5 Quasigeodesic and geodesic rays are Hausdorff close . . . . . . . . . . 42
3.6 A point on a geodesic segment close to a given point p on a quasigeo-
desic ray. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.7 A point on the geodesic ray close to a given point p on a quasigeodesic
ray. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8 A geodesic connecting two p oints an equal distance along a pair of
geodesic rays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.9 The case where p = x
0
. . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.10 The case where p ∈ (x
0
, o
2
] . . . . . . . . . . . . . . . . . . . . . . . . 46
3.11 The case where p ∈ (o
2
, y
2
) . . . . . . . . . . . . . . . . . . . . . . . . 46
3.12 The case where p ∈ [y
2
, ∞) . . . . . . . . . . . . . . . . . . . . . . . . 47
3.13 An upper bound on the distance between a pair of non-divergent qua-
sigeodesic rays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.14 A lower bound on the distance between points on a pair of divergent
quasigeodesic rays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.15 A lower bound on the distance b etween a point on a quasigeodesic ray
and another quasigeodesic ray when the two rays are divergent. . . . 50

3.16 The triangle inequality applied to points on a pair of divergent quasi-
geodesic rays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.17 A pair of points along associated geodesic rays that are more than 3δ
apart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.18 Finding an upper bound for t
2
. . . . . . . . . . . . . . . . . . . . . . . 54
3.19 A pair of vertices on non-divergent quasigeodesic rays at a distance of
< K from one another. . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.20 A second pair of vertices on non-divergent quasigeodesic rays at a dis-
tance of < K from one another. . . . . . . . . . . . . . . . . . . . . . 56
3.21 A sequence of pairs of vertices, each at a distance of < K from one
another. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.22 A path from v
l
to u
−k
labeled by w
−1
. . . . . . . . . . . . . . . . . . . 60
3.23 Deciding membership in the product of two cyclic submonoids in the
divergent case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.24 The quasigeodesic rays induced by u
−1
and v in the non-divergent case. 62
3.25 A word of length less than |w| labeling a path between non-divergent
quasigeodesic rays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.26 A translate of a path of length less than |w| between non-divergent
quasigeodesic rays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.27 A word of length less than |w| labeling a path from the second ray to

the first ray in a non-divergent quasigeodesic pair. . . . . . . . . . . . 63
4.1 A product in M equivalent to π(P)π
k
(w)π(S). . . . . . . . . . . . . . . 79
4.2 The transition diagram for A
(V,ǫ,C
2
,1)
. . . . . . . . . . . . . . . . . . . 79
4.3 The transition diagram for A
(V,Ab,ABC,2)
. . . . . . . . . . . . . . . . . . 80
4.4 The transition diagram for A
(V,ǫ,ǫ,1)
. . . . . . . . . . . . . . . . . . . . 81
4.5 The tree of computations carried out by Algorithm S. . . . . . . . . . 84
4.6 The prefix of the product containing v
1
. . . . . . . . . . . . . . . . . . 86
4.7 The case where x
1
is a syllable of

u
1
. . . . . . . . . . . . . . . . . . . 87
4.8 The case where x
1
is a syllable of


u
2
. . . . . . . . . . . . . . . . . . . 87
4.9 The case where x
1
is a syllable of

u
3
. . . . . . . . . . . . . . . . . . . 88
4.10 The case where no segments lie between x
l
and x
l+1
. . . . . . . . . . . 88
4.11 The case x
l
and x
l+1
are in consecutive

u
i
s and there is a cancellation
between them. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.12 The case where x
l+1
is in

u

t+2
. . . . . . . . . . . . . . . . . . . . . . . 89
4.13 The path in the automaton from ǫ to the final state S
1
, labeled by v
1
. 90
4.14 The cancellations forming v
2
when y
1
is a segment of

u
m
1
, and v
2
=
G
y
1
. 91
4.15 The cancellations forming v
2
when y
1
is a segment of

u

m
1
and v
2

G
y
1
. 91
4.16 The cancellations forming v
2
when y
1
is not a segment of

u
m
1
and v
2

G
y
1
. 91
4.17 The case where the last surviving segment is in

u
N
. . . . . . . . . . . 93

4.18 The case where the last surviving segment is in

u
m
r
for m
r
< N. . . . . 93
4.19 A long cancellation in a product of generators from U. . . . . . . . . 95
4.20 Replacing the long cancellation C
i
with a short cancellation C
′
i
by
adding a new generator. . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.21 A long cancellation in a product of generators from U. . . . . . . . . 97
4.22 A long cancellation in the subproduct

u
j+1


u
j+k
1
−1
=
G
T

−1
1
R
−1
k
1
. . . . . . 98
1
Chapter 1
Introduction
In 1911, Dehn formulated three fundamental decision problems for groups: the word
problem, the conjugacy problem, and t he isomorphism problem [Deh]. Dehn proved
that there are algorithms to decide each of these problems when G is the fundamental
group of a closed 2-manifold. However, these problems are undecidable for finitely
generated groups in general. The word problem for a group G with finite generating
set A asks whether or not there is an algorithm that, given input a word w ∈ (A∪A
−1
)
∗
,
determines in a finite number of steps whether or not w represents the trivial element
in the group. In 1955, Novikov [Nov] and Boone [Boo] independently proved that
there is a finitely generated group with undecidable word problem. Since then, there
has been much progress toward the goal of determining which classes of groups have
decidable word problem and which have undecidable word problem, but many open
questions remain.
If we restrict our attention to finitely generated groups with decidable word prob-
lem, there are several generalizations of the word problem that can be considered.
These include: deciding membership in finitely generated subgroups (the uniform
generalized word problem), deciding membership in finitely generated submonoids

2
(the uniform submonoid membership problem), determining the order of an element
of the group (the order problem), deciding whether or not one element of the group
is a non-negative power of another element (th e power problem), deciding, given two
elements of the group via two words u and v, whether or not there are nonzero integer
exponents k and l such that u
k
=
G
v
l
(the generalized power problem), and decid-
ing membership in rational subsets of the group (the rational membership problem).
Each of these problems is known to be strictly harder than the word problem. That
is, an algorithm deciding any of these problems for a finitely generated group G im-
plies that there is also an algorithm to decide the word problem, and for each of these
decision problems, there is an example of a finitely generated group for which the
word problem is decidable, but the given problem is undecidable (references for these
examples will be given in Chapter 2). Consequently, each of these problems is unde-
cidable in general. However, there are examples of classes of groups for which these
problems are decidable. For example, each of these problems is decidable for both fi-
nitely generated free groups and finitely generated free abelian groups. In 1999, Zeph
Grunschlag [Gru] showed that the word problem, uniform generalized word problem,
and rational membership problem are all preserved when passing to finite index sub-
groups and to finite index extensions. Therefore, each of these membership problems
is decidable for virtually finitely generated free groups and virtually finitely gener-
ated free abelian groups as well. This dissertation explores the decidability of the
aforementioned generalizations of the word problem. The main results are as follows:
Corollary 3.3.28 Let G = A | R be a finitely generated δ-hyperbolic group with
A closed under inversion. Let u, v ∈ A

∗
be words representing elements of infinite
order in G. Let β
u
and β
v
be the quasigeodesic rays based at 1 induced by u and v
respectively. Then there is an algorithm that decides whether the pair of rays β
u
and
β
v
are divergent or non-divergent.
3
Theorem 3.0.13 Let G = A be a finitely generated δ-hyperbolic group with A
closed under inversion. Then there is an algorithm deciding the generalized power
problem for G.
Theorem 3.0.14 Let G = A be a finitely generated δ-hyperbolic group with A
closed under inversion. Let u, v ∈ A
∗
. Then there is an algorithm deciding member-
ship in the rational subset {u}
∗
· {v}
∗
.
Theorem 4.2.9 Let G = G
1
∗ G
2

where G
1
and G
2
are finitely presented groups with
generating sets A and B respectively, both closed under inversion. If G
1
and G
2
have
decidable rational membership problem, then the uniform submonoid membership
problem for G is decidable.
Here is an outline of the material in this dissertation:
Chapter 2 introduces the notation and background concepts necessary for the al-
gorithms developed in the remainder of the dissertation. It outlines the historical
development of the word problem and its generalizations, and discusses examples of
finitely generated groups for which these decision problems are decidable and others
for which they are undecidable. Some tools of particular importance that are de-
veloped in this chapter are Cayley graphs, rational subsets, normal forms and finite
state automata.
In Chapter 3, we turn our attention to algorithms in word hyperbolic groups.
Word hyperbolic groups were introduced by Gromov in 1987 [Gro]. It is known that
the word problem [A+], the order problem ([Lys], [Bra]), and the power problem
[Lys] are decidable for word hyperbolic groups. However, E. Rips [Rip] showed that
the uniform generalized word problem is undecidable in general for word hyperbolic
groups. Therefore, membership in finitely generated submonoids and in rational sub-
sets are also undecidable. We prove that the generalized power problem is decidable
for word hyperbolic groups. To do so, we prove some geometric and algorithmic prop-
4
erties of the quasigeodesic rays induced by elements of infinite order in the Cayley

graph of a word hyperbolic group. Our main result is that pairs of quasigeodesic rays
in the Cayley graph of a word hyperbolic group induced by elements of infinite order
either never meet at a vertex, or they intersect at a vertex infinitely many times, and
we can detect which of the two happens for a given pair of quasigeodesic rays. Since
solutions to the generalized power problem for pairs of words representing elements of
infinite order correspond to points of intersection on their induced quasigeodesic rays,
this result leads to an algorithm to decide the generalized power problem in instances
where both words represent elements of infinite order. The case where the given
words represent elements of finite order can be decided using the algorithm deciding
the word problem for word hyperbolic groups finitely many times. The algorithm
deciding the order problem for word hyperbolic groups can be used to determine
whether we should use the infinite order algorithm or the finite order algorithm for a
given pair of test words. Together, these give an algorithm deciding the generalized
power problem for word hyperbolic groups. We use similar techniques to extend this
to an algorithm deciding membersh ip in the product of two cyclic submonoids of a
word hyperbolic group.
In Chapter 4, we shift our focus to another perspective on decision problems in
groups. Rather than considering a class of groups, we consider the effect of classical
group theoretic constructions on decision algorithms. The most common construc-
tions for building new groups from old are: subgroups, quotients, direct products,
free products, free products with amalgamation, and HNN extensions. It is natural
to ask what effect these constructions have on the decidability of the word problem
and its generalizations. A theorem of Grunschlag [Gru] shows that the word prob-
lem, uniform generalized word problem, and rational membership problem are all
preserved when passing to finite index subgroups and finite index extensions. K. A.
5
Mihailova has shown that the uniform generalized word problem is not preserved by
direct products [Mih1], but that it is preserved by free products [Mih3].
Most of chapter 4 is devoted to extending Mihailova’s result on the uniform gen-
eralized word problem for free products to obtain a similar result for the uniform

submonoid membership problem. Using the normal form theorem for free products,
we define the cancellation diagram of a product of generators in a finitely generated
submonoid of a free product of two groups with decidable word problem (these are
similar to the cancellation d iagrams introduced by Patrick Bahls [Bah]). These di-
agrams allow us to keep track of exactly how cancellation occurs when putting a
product of generators in a finitely generated submonoid of the free product of two
groups into reduced alternating form. The cancellation diagram for a product in the
submonoid generators is short if each of its maximal cancellations is short, that is, if
each maximal cancellation involves at most three consecutive submonoid generators
in the product (see Definition 4.1.12). We give an automaton construction that forms
the foundation of an algorithm that recognizes the elements of a finitely generated
submonoid that can be written as short products. We then give a procedure that,
given a finite generating set U for a submonoid M of a free product G = G
1
∗ G
2
,
forms a finite generating set
U with the property that every element of the monoid
can be written as a short product with respect to
U. The completion procedure is
conceptually similar to the procedure for forming a Nielsen closed generating set for
a submonoid of a free group. Once we have the generating set
U, the algorithm that
recognizes elements of the monoid that can be written as a short product with respect
to a given finite generating set can be used to decide membership in the submonoid,
since every word that represents an element in the monoid can be written as a short
product in U. The idea of deciding membership by first finding an algorithm that
recognizes short elements and then finding a generating for which every element is
6

short is due to Mihailova [Mih4]. However, since we are deciding membership in sub-
monoids rather than subgroups, our algorithm recognizing short elements requires
different techniques than those employed by Mihailova.
Notice that Mihailova’s result for the uniform generalized word problem in a free
product only requires an algorithm to decide the uniform generalized word problem
in each factor, while our algorithm deciding uniform submonoid memb ership in a
free product requires an algorithm to decide membership in rational subsets in each
factor, which is a stronger hypothesis than just requiring an algorithm to decide
uniform submonoid membership in each factor.
7
Chapter 2
Preliminaries
The purpose of this chapter is to introduce some stand ard notation that will be
used throughout this dissertation and the background material necessary to make the
results in the chapters that follow accessible.
2.1 Conventions and Notation
2.1.1 Monoids and Groups
Let A be a set. The free monoid on A, denoted by A
∗
, is the set of all finite length
strings (or words) over A with concatenation as its product and the empty string
ǫ as its unit. A language L is any subset of A
∗
. Given a word w = a
1
a
2
a
n
with

a
i
∈ A for all i, the length of w, denoted by |w|, is n, the number of letters in w. By
convention, l(ǫ) = 0.
A set A is a generating set for a monoid M if there is a surjective homomorphism
π : A
∗
→ M. Similarly, A is a generating set for a group G if there is a surjective
homomorphism π : (A ∪ A
−1
)
∗
→ G, where A
−1
:= {a
−1
| a ∈ A} is a set of formal
inverses corresponding to A and π(a
−1
) = π(a)
−1
for every a ∈ A. A generating set A
8
is closed under inversion if A = B ∪ B
−1
where B is a generating set for G, and
B
−1
= {b
−1

| b ∈ B} satisfies π(b
−1
) = π(b)
−1
for every b ∈ B.
If two words u, v ∈ A
∗
satisfy π(u) = π(v), then we write u =
G
v. If the words
are equal as strings (that is, as elements of A
∗
), then we write u ≡
A
∗
v. When the
underlying alphabet of the words u and v is clear from context, we abbreviate this
as u ≡ v. Given U ⊆ A
∗
, U denotes the subgroup of G generated by U (formally
speaking, we mean the subgroup of G generated by π(U)). Similarly, U
N
denotes
the normal subgroup of G generated by U, and MonU denotes the submonoid of G
generated by U
Given any non-empty set X, we can construct F(X), the free group on the set X.
Let X
−1
:= {x
−1

| x ∈ X}. We define an equivalence relation on (X ∪ X
−1
)
∗
by taking
two words w and v to be equivalent, written w ∼ v, if it is possible to pass from one
word to the other by inserting and deleting subwords of the form xx
−1
or x
−1
x for
x ∈ X. A word w ∈ (X ∪ X
−1
)
∗
is reduced if it contains no subwords of the form xx
−1
or x
−1
x. Every equivalence class [w] contains exactly one reduced word (see [Rob] p.
46). Then F(X) := {[w] | w ∈ (X ∪ X
−1
)
∗
}, is a group with operation [w][v] := [wv] (the
equivalence class of the word formed by concatenating w and v), identity element [ǫ]
(the equivalence class if the empty word), and inverses [w]
−1
= [w
−1

], where, given
w ≡ x
ǫ
1
1
x
ǫ
2
2
x
ǫ
r
r
with x
i
∈ X and ǫ
i
∈ {−1, +1}, w
−1
≡ x
−ǫ
1
1
x
−ǫ
2
2
x
−ǫ
r

r
.
Definition 2.1.1 A set R ⊆ A
∗
is called a set of relators if r =
G
1 for every r ∈ R.
P = A | R is called a presentation for a group G if A is a generating set for G,
and the natural homomorphism ϕ : F(A)/R
N
→ G is an isomorphism.
A group G is finitely presented if there is a presentation P = A | R with
|A| < ∞, |R| < ∞, and G  F(A)/R
N
.
Example: The free abelian group of rank n is the group with presentation Z
n
:=
a
1
, a
2
, , a
n
| a
i
a
j
a
−1

i
a
−1
j
= 1 for 1 ≤ i < j ≤ n.
9
2.1.2 Dehn’s Problems
In 1911 Dehn formulated three decision problems for groups: the word problem, the
conjugacy problem, and the isomorphism problem (see [Deh], [Mil], or [LS]).
(1) Given a group G with generating set A, the word problem asks if there is an
algorithm that decides, given two words w
1
, w
2
∈ (A∪ A
−1
)
∗
, whether or not w
1
=
G
w
2
.
Since w
1
=
G
w

2
if and only if w
1
w
−1
2
=
G
1, this is equivalent to deciding for a given
word w ∈ (A ∪ A
−1
)
∗
, whether or not w =
G
1. If such an algorithm exists, then we say
the group G with generating set A has decidable word problem. Otherwise, we
say (G, A) has undecidable word problem.
(2) Given a group G with generating set A, the conjugacy problem asks if there
is an algorithm that decides, given two words w
1
, w
2
∈ (A ∪ A
−1
)
∗
, whether or not w
1
and w

2
represent conjugate elements in G; that is, whether or not there is some g ∈ G
such that g
−1
π(w
1
)g = π(w
2
). If such an algorithm exists, then we say the pair (G, A)
has decidable conjugacy problem. Otherwise, we say (G, A) has undecidable
conjugacy problem.
(3) Given a group G with presentation G = A | R and a group G
′
with presen-
tation G
′
= B | S, the isomorphism problem asks if there is an algorithm that
decides whether or not G and G
′
are isomorphic. If such an algorithm exists for
any class of groups, then we say this class of groups has decidable isomorphism
problem. Otherwise, we say the class of groups has undecidable isomorphism
problem.
Proposition 2.1.2 ([LS] Proposition 2.2 p. 90) If G = A | R is a presentation
with finite generating set for which the word problem or the conjugacy problem is
decidable, then the word problem (or the conjugacy problem) is decidable for any
finitely generated presentation of the group.
10
Notes:
(1) In light of the previous proposition, it makes sense to say that a group G

has decidable word problem (or conjugacy problem) without reference to a specific
generating set, with the understanding that this means that the word (or conjugacy)
problem is decidable for any finite generating set for the group.
(2) Dehn showed that all three of his decision problems are decidable when G is the
fundamental group of a closed 2-manifold ([Deh]). However, the word problem turns
out to be undecidable in general. That is, there are examples of finitely generated
groups with undecidable word problem (see [Nov], [Boo], and [Hig]).
(3) If G has decidable conjugacy problem, it also has decidable word problem. To
see this, let G be a group with finite generating set A, with A closed under inversion.
Let w ∈ A
∗
. Notice that w =
G
1 if and only if g
−1
π(w)g =
G
1 for some g ∈ G. Then we
can use the algorithm deciding the conjugacy problem for this presentation in order
to check to see if w and 1 are conjugate in G, hence we can decide the word problem
for G.
(4) There is a finitely generated group G with decidable word problem and unde-
cidable conjugacy problem. ([Fri], [Col])
(5) The isomorphism problem is undecidable. In fact, there is no algorithm that,
given a finite presentation, decides whether or not the group given by this presentation
is the trivial group. ([Adi1], [Adi2], [Rab]).
2.1.3 Generalizations of the Word Problem
In this section, we consider several generalizations of the word problem. Each problem
is known to be a strictly harder problem than the word problem for the class of finitely
generated groups.

11
Definition 2.1.3 Let G = A be a finitely generated group, with A closed under
inversion. The uniform generalized word problem asks if there is an algorithm
that decides, given a finite collection of words u
1
, u
2
, , u
k
∈ A
∗
and a test word w ∈ A
∗
,
whether or not π(w) ∈ H := π(u
1
), π(u
2
), , π(u
k
). If such an algorithm exists, we say
G has decidable uniform generalized word problem. Otherwise, we say G has
undecidable uniform generalized word problem.
Definition 2.1.4 Let G = A be a finitely generated group, with A closed under
inversion. The uniform submonoid membership problem asks if there is an
algorithm that decides, given a finite collection of words u
1
, u
2
, , u

k
∈ (A ∪ A
−1
)
∗
and
a test word w ∈ (A ∪ A
−1
)
∗
, whether or not π(w) ∈ M := Monπ(u
1
), π(u
2
), , π(u
k
).
If such an algorithm exi sts, we say G has decidable uniform submonoid mem-
bership problem. Otherwise, we say G has undecidable uniform submonoid
membership problem.
Definition 2.1.5 Let G = A be a finitely generated group, with A closed under
inversion. The order problem asks if there is an algorithm that, given a word
w ∈ A
∗
, determines whether or not π(w) has finite order in G. If π(w) has finite order,
the algorithm outputs t he order of π(w) (that is, the least n ∈ N
+
such that w
n
=

G
1).
On the other hand, if π(w) has infinite order, the algorithm stops after a finite number
of steps and outputs ∞. If such an algorithm exists, we say G has decidable order
problem. Otherwise, we say G has undecidable order problem.
Definition 2.1.6 Let G = A be a finitely generated group, with A closed under
inversion. The power problem asks if there is an algorithm that, given two words
u, v ∈ A
∗
, determines whether or not there is an integer k ∈ N such that u =
G
v
k
. If
such an algorithm exists, we say G has decidable power problem. Otherwise, we
say G has undecidable power problem.
12
Definition 2.1.7 Let G = A be a finitely generated group, with A closed under
inversion. The root problem asks if there is an algorithm that, given any word
w ∈ A
∗
and any integer k, determines whether or not w has a kth root. That is, whether
or not there is an element g ∈ G such that π(w) =
G
g
k
. If such an algorithm exists, we
say G has decidable root problem. Otherwise, we say G has undecidable root
problem.
Definition 2.1.8 Let G = A be a finitely generated group, with A closed under

inversion. The generalized power problem asks if there is an algorithm that,
given two words u, v ∈ A
∗
, determines whether or not there are nonzero integers
k, l ∈ Z such that u
k
=
G
v
l
. If such an algorithm exists, we say G has decidable
generalized power problem. Otherwise, we say G has undecidable generalized
power problem.
Proposition 2.1.9 ([LM] Theorem 1 p. 8): If the uniform generalized word problem,
the uniform submonoid membership problem, the order problem, the root problem, the
power problem, or the generalized power problem are decidable for a finitely generated
group G, then the word problem for G is also decidable.
Notes:
(1) There is a finitely generated group for which the word problem is decidable,
and the uniform generalized word problem is undecidable. In fact, we can take G to
be F × F where F is a free group of rank at least 2. ([Mih1])
(2) Since every finitely generated subgroup of a group G is also a finitely generated
submonoid, any algorithm deciding th e uniform submonoid membership problem for
G can also be used to decide the uniform generalized word problem for G. Hence the
uniform submonoid membership problem is at least as hard as the uniform generalized
word problem.
13
(3) The ord er and power problems were introduced by J. McCool ([Mc1]). McCo ol
gives an example of a finitely generated group G with decidable word problem and
undecidable order and power problems (Theorem 2 in [Mc2] p. 837).

(4) The root problem and the generalized power problem were introduced by S.
Lipschutz and C. F. Miller ([LM]). Their paper gives many examples that demon-
strate the relationships between generalizations of the word problem including: an
example of a finitely generated group with decidable generalized power problem and
undecidable order, power, and root problems, and an example of a finitely generated
group with decidable order problem and undecidable power, root, and generalized
power problems (see [LM] pp. 8-9).
(5) If the uniform submonoid membership problem is decidable for a finitely gen-
erated group G, then the power problem is also decidable for G, since the power
problem is equivalent to deciding membership in a cyclic submonoid.
Question 2.1.10 Is there a finitely generated group G with decidable uniform gen-
eralized word problem and undecidable uniform submonoid membership problem?
2.1.4 Cayley Graphs and Metric Spaces
Definition 2.1.11 Let G be a group and A a generating set for G that is closed under
inversion. The Cayley graph of G with respect to A, denoted by Γ
(G,A)
, is the directed
labeled graph defined as follows:
(1) V(Γ
(G,A)
) = G. That is, there is a vertex for each element of G.
(2) For every vertex g and every a ∈ A, there is a directed edge (g, ga) from g to
ga labeled by a (see Figure 2.1).
Note: Since A is closed under inversion, we can write A = B ∪ B
−1
. For each directed
edge (g, gb) labeled by b ∈ B, there is an inverse edge (gb, g) labeled by b
−1
∈ B
−1

.
14
a
g
ga
Figure 2.1: A directed edge in a Cayley graph.
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . . . .
. . .
. . .
. . .
. . .
. . .
. . .
aa
b
b
a
b
b
a
b
aa

a
a
b
b
b
1
Figure 2.2: The Cayley graph of the free group of rank two.
Therefore, we can omit the inverse edges labeled over B
−1
, yielding a directed graph
labeled by B, with the understanding that the B labeled edge is rep resented by moving
along the directed edge, and the B
−1
labeled inverse edge is represented by moving
opposite the arrow along the directed edge.
Examples:
(1) G = F
2
= a, b, A, B | aA = Aa = bB = Bb = 1 (see Figure 2.2).
(2) G = Z
2
= a, b, A, B | abAB = 1, aA = Aa = bB = Bb = 1 (see Figure 2.3).
Notes:
(1) The Cayley graph of a group Γ
(G,A)
with finite generating set A, A closed under
inversion, can be made into a metric space as follows: each edge (g, gb) labeled by
b ∈ B along with its “inverse edge” (gb, g) labeled by b
−1
∈ B

−1
are identified to form a
15
1
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
a
a
b
b
a
a
a
a
b
b
b
b
a
a
b
b
Figure 2.3: The Cayley graph of the free abelian group of rank two.
single undirected edge. Each of these undirected edges is taken to be isometric to the

unit interval [0, 1] in R. The distance between arbitrary points in the graph (including
points in the interior of edges) is defined to be the length of the shortest path in the
graph connecting them. Since there is a one to one correspondence between elements
of the group and vertices in the Cayley graph, the metric on the Cayley graph induces
a metric on the group G. For any pair of elements g, h ∈ G, d(g, h) is the distance
between the vertices in Γ
(G,A)
corresponding to the elements g and h.
(2) Since Γ
(G,A)
is a labeled graph, when viewed as a directed graph, each path of
minimal length between two vertices g and h is labeled by a word in A
∗
. Any word in
A
∗
that is the label of a minimal length path is called a geodesic word. For a fixed
element g ∈ G, the collection of all words labeling minimal length paths from vertex
1 to vertex g is the set of geodesic representatives of g with respect to the generating
set A.
16
2.1.5 Normal Forms
Definition 2.1.12 Let G be a group with finite generating set A, and suppose A is
closed under inversion. Let π : A
∗
→ G be the canonical surjective homomorphism. A
normal form for G is a subset L ⊆ A
∗
such that π
|

L
: L → G is a bijection.
Note: We will usually restrict our attention to the case where, given a word w ∈ A
∗
there is an algorithm to find the n ormal form representing the corresponding group
element. That is, given w, one can find

w ∈ L such that π(w) = π(

w).
Suppose A = {a
1
, a
2
, , a
n
}, and let w ∈ A
∗
. Let w ≡ s
1
s
2
s
m
with each s
i
∈ A.
Recall that the length w, written |w| := m, is the number of letters in w. Any fixed
ordering on A induces a shortlex ordering on A
∗

as follows: given u, v ∈ A
∗
, suppose
that u ≡ x
1
x
2
x
m
and v ≡ y
1
y
2
y
n
. We say u is shortlex less than v (written u <
sl
v)
if: (1) m < n or (2) m = n, x
i
= y
i
for i < k, and x
k
< y
k
in the order on A.
Since we will never use two different orderings of A at the same time, we can omit
reference to the ordering on A in our notation <
sl

without fear of ambiguity.
Definition 2.1.13 A shortlex normal form for G is a normal form L for which
there is an order on A such that for any w ∈ L and v ∈ A
∗
, if w =
G
v then w ≤
sl
v in the
related shortlex ordering on A
∗
. For any v ∈ A
∗
,

v denotes the shortlex representative
of the word v.
Note: Let G be a group with generating set A, with A closed under inversion. If
there is an algorithm that, when given as input a word w ∈ A
∗
, outputs the shortlex
representative of w with respect to a fixed ordering on A, then the word problem for
G is decidable. To see this, notice that w =
G
1 if and only if

w = ǫ. The following
proposition shows that the converse to this statement is also true:
Proposition 2.1.14 Let G = A | R be a fin itely generated group with A closed under
inversion. If the word problem for G with respect to this generati ng set is decidable,

17
then there is an algorithm that, given a word w ∈ A
∗
, outputs

w, the shortlex normal
form for w with respect to a fi xed ordering on the generating set A.
Proof: Given w ≡ x
1
x
2
x
m
and some fixed ordering on A, let S := {v ∈ A
∗
| v <
sl
w},
the set of words shorter than w in the related shortlex ordering. Notice that S is a
finite subset of A
∗
, hence S is recursive. We can effectively put S in decreasing order
with respect to <
sl
. For each v ∈ S, apply the algorithm deciding the word problem
to test to see if wv
−1
=
G
1. If the answer is NO for every v ∈ S, then w is in shortlex

normal form. Otherwise, let v
N
be the least element of S such that the word problem
algorithm returns YES. Then v
N
is the shortlex normal form for w. 
2.2 Languages and Automata
2.2.1 Rational Subsets of Monoids
Let M be a monoid. Then Rat(M), the rational subsets of a monoid M, is the
smallest family of subsets of M containing the empty set and every singleton set, and
closed under the operations: finite union, finite product, and submonoid closure.
A convenient way to represent rational subsets is by means of regular expres-
sions. Regular expressions are recursively defined as follows:
(i) ∅ is a regular expression and denotes the empty set.
(ii) for each m ∈ M, m is a regular expression and denotes the set {m}.
(iii) If r and s are regular expressions denoting rational sub sets R and S respec-
tively, then (r ∪ s), (rs), and (r
∗
) are regular expressions that denote R ∪ S , RS, and
R
∗
respectively.
Given a regular expression r, R(r) denotes the rational subset of M associated with r.
Note: Distinct regular expressions are sometimes associated with the same rational
subset of M.