Solving the word problem in real time

Derek F.\ Holt and Sarah Rees\

Keywords

word problem, real-time, Dehn algorithm

Status

published in J London Mathematical Society 63 (2001) 623-639

Abstract

This paper is devoted to the study of groups whose word problem can be solved by a Turing machine which operates in real-time. A recent result of the first author for word hyperbolic groups is extended to prove that under certain conditions the generalised Dehn algorithms of Cannon, Goodman and Shapiro, which clearly run in linear time, can be programmed on real-time Turing machines. It follows that word-hyperbolic groups, finitely generated nilpotent groups and geometrically finite hyperbolic groups all have real-time word problems. \

The preprint is available as gzipped dvi (36 kB) and postscript (96 kB) files.

Alternatively, you can request a copy by e-mailing me.