Holt, Derek F. and Röver, Claas E.. (2003) On real-time word problems. Journal of the London Mathematical Society, Vol.67 (No.2). pp. 289-301. ISSN 0024-6107

Preview

PDF WRAP_Holt_Real-time_word.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (250Kb)

Abstract

It is proved that the word problem of the direct product of two free groups of rank 2 can be recognised by a 2-tape real-time but not by a 1-tape real-time Turing machine. It is also proved that the Baumslag–Solitar groups B(1,r) have the 5-tape real-time word problem for all r != 0.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Word problems (Mathematics), Turing machines, Combinatorial group theory, Geometric group theory
Journal or Publication Title:	Journal of the London Mathematical Society
Publisher:	Cambridge University Press
ISSN:	0024-6107
Date:	April 2003
Volume:	Vol.67
Number:	No.2
Page Range:	pp. 289-301
Identification Number:	10.1112/S0024610702003770
Status:	Peer Reviewed
Access rights to Published version:	Open Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
References:	1. S. O. Aanderaa, `On k-tape versus (k − 1)-tape real time computation', Complexity of computation, SIAM-AMS Proceedings VII (American Mathematical Society, Providence, RI, 1974). 2. J. Cannon, O. Goodman and M. Shapiro, `Dehn's algorithm for non-hyperbolic groups', preprint, University of Melbourne. 3. M. J. Dunwoody, `The accessibility of nitely presented groups', Invent. Math. 81 (1985) 449{457. 4. M. J. Fischer and A. L. Rosenberg, `Real-time solutions of the origin-crossing problem', Math. Systems Theory 2 (1968) 257{263. 5. E. Ghys and P. de la Harpe, Sur les groupes hyperboliques d'apres Mikhael Gromov (Birkh¨auser, Boston, 1990). 6. J. Hartmanis and R. E. Stearns, `On the computational complexity of algorithms', Trans. Amer. Math. Soc. 117 (1965) 285{306. 7. D. F. Holt and S. Rees, `Solving the word problem in real time', J. London Math. Soc. 63 (2001) 623{639. 8. R. C. Lyndon and P. E. Shupp, Combinatorial group theory (Springer, Berlin, 1977). 9. D. E. Muller and P. E. Schupp, `Groups, the theory of ends, and context-free languages', J. Comput. System Sci. 26 (1983) 295{310. 10. D. E. Muller and P. E. Schupp, `The theory of ends, pushdown automata, and second-order logic', Theoret. Comput. Sci. 37 (1985) 51{75. 11. M. O. Rabin, `Real time computation', Israel J. Math 1 (1963) 203{211. 12. A. L. Rosenberg, `Real time denable languages', J. Assoc. Comput. Mach. 14 (1967) 645{662.
URI:	http://wrap.warwick.ac.uk/id/eprint/767

Request changes to a record

Actions (login required)

View Item