Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-27T09:39:50.980Z Has data issue: false hasContentIssue false
  • English
  • Français

SOLVING THE WORD PROBLEM IN REAL TIME

Published online by Cambridge University Press:  05 July 2001

DEREK F. HOLT  and
SARAH REES
DEREK F. HOLT
Affiliation:
Mathematics Institute, University of Warwick, Coventry CV4 7AL; [email protected]
SARAH REES
Affiliation:
Department of Mathematics, University of Newcastle, Newcastle NE1 7RU; [email protected]
Get access

Abstract

The 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.

Type
Research Article
Information
Journal of the London Mathematical Society , Volume 63 , Issue 3 , June 2001 , pp. 623 - 639
Copyright
The London Mathematical Society 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)