The Library
Solving the word problem in real time
Tools
Tools
Tools
Holt, Derek F. and Rees, Sarah. (2001) Solving the word problem in real time. Journal of the London Mathematical Society, Vol.63 (No.3). pp. 623-639. ISSN 0024-6107
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png)
|
PDF
WRAP_Holt_Solving_word_problem.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (301Kb) |
Official URL: http://dx.doi.org/10.1017/S0024610701002083
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.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Mathematics |
| Library of Congress Subject Headings (LCSH): | Turing machines, Word problems (Mathematics), Group theory, Automorphisms |
| Journal or Publication Title: | Journal of the London Mathematical Society |
| Publisher: | Cambridge University Press |
| ISSN: | 0024-6107 |
| Date: | June 2001 |
| Volume: | Vol.63 |
| Number: | No.3 |
| Page Range: | pp. 623-639 |
| Identification Number: | 10.1017/S0024610701002083 |
| Status: | Peer Reviewed |
| Access rights to Published version: | Open Access |
| References: | 1. B. H. Bowditch, `Geometrical finiteness for hyperbolic groups', J. Funct. Anal. 113 (1993) 245±317. 2. Cannon, Goodman and Shapiro, `Dehn's algorithm for non-hyperbolic groups', preprint. 3. M. Dehn, `U $ ber die Topologie des dreidimensionalen Raumes', Math. Ann. 69 (1910) 137±168. 4. D. B. A. Epstein, J.W.Cannon, D.F.Holt, S.Levy, M. S.Paterson and W. Thurston, Word processing in groups (Jones and Bartlett, 1992). 5. T. Herbst and R. M. Thomas, `Group presentations, formal languages and characterizations of onecounter groups', Theoret. Comput. Sci. 112 (1993) 187±213. 6. D. F. Holt, `Word-hyperbolic groups have real-time word problem', Internat. J. Algebra Comput. 10 (2000) 221±227. 7. W. D. Neumann and M. Shapiro, `Automatic structures, rational growth and geometrically finite hyperbolic groups', Invent. Math. 120 (1995) 259±287. 8. A. L. Rosenberg, `Real-time definable languages', J. Assoc. Comput. Mach. 14 (1967) 645±662. |
| URI: | http://wrap.warwick.ac.uk/id/eprint/812 |
Actions (login required)
 |
View Item |
