Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Holt, Derek F.; Röver, Claas E. (2003)
Publisher: Cambridge University Press
Languages: English
Types: Article
Subjects: QA
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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 (Birkha¨user, 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 de nable languages', J. Assoc. Comput. Mach. 14 (1967) 645{662.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article