On real-time word problems

Article English OPEN
Holt, Derek F. ; Röver, Claas E. (2003)

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.
  • References (12)
    12 references, page 1 of 2

    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.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Warwick Research Archives Portal Repository - IRUS-UK 0 21
Share - Bookmark