How good is Dehn's algorithm?
Sarah Rees, University of Newcastle
Friday May 19, 12.15-1.00, Groups in Galway 2006
In 1912, Dehn posed the word problem, the
question of whether or not a given word in the generators of a
group described by a presentation represented the identity element,
and solved it for surface groups. In fact Dehn's algorithm
can be used to solve the word problem for a larger class of
groups, namely word hyperbolic groups. The algorithm applies
length reducing rules from a finite set; words which represent the
identity are reduced to the trivial word.
But what happens away from the identity?
Usually words are not reduced to geodesic representatives. We
can prove that if they are, then the solution of the word
problem can be programmed on a pushdown automaton,
and hence the group is virtually free. Indeed,
virtually free groups can be characterised by this
feature of their geodesics.
I shall examine Dehn's algorithm, explain this characterisation of
virtually free groups, and look more generally at the structure of
geodesics in groups and its connection to the word problem.
This work is joint work with Gilman, Hermiller and Holt.