Input-driven languages are recognized in log n space

1. B.v.Braunmühl, S.A. Cook, K. Mehlhorn, R. Verbeek: The recognition of deterministic CFLs in small time and space, submitted for publication.

   Google Scholar 

2. B.v. Braunmühl, R. Verbeek: A recognition algorithm for DCFLs optimal in time and space, Proc. 21th FOCS, pp. 411–420.

   Google Scholar 

3. S.A. Cook: Deterministic CFLs are accepted simultaneously in polynomial time and log squared tape, Proc. 11th ACM-STOC, pp. 338–345.

   Google Scholar 

4. S.A. Cook, R. Sethi: Storage requirements for deterministic polynomial time recognizable languages. JCSS 13, 25–37.

   Google Scholar 

5. Y. Igarashi: The tape complexity of some classes of Szilard languages, SIAM 3. Comp. 6, pp. 460–466.

   Google Scholar 

6. Y. Igarashi: Tape bounds for some subclasses of deterministic context-free languages, Inf. Contr. 37, 321–333.

   Google Scholar 

7. P.M. Lewis, R.E. Stearns, J. Hartmanis: Memory bounds for the recognition of context-free and context-sensitive languages, Proc. 6th IEEE-SWAT, pp. 191–212.

   Google Scholar 

8. R. Lipton, Y. Zalcstein: Word problem solvable in log-space, JACM 24, 522–526.

   Google Scholar 

9. K. Mehlhorn: Bracket languages are recognizable in logarithmic space, Technical report, FB 10. Universität Saarbrücken.

   Google Scholar 

10. K. Mehlhorn: Pebbling mountain ranges and its application to DCFL-recognition, Proc. 7th ICALP, pp. 422–432.

    Google Scholar 

11. M.S. Paterson, C.E. Hewitt: Comparative schematology, project MAC, Conf. on concurrent systems and parallel computation, pp. 109–127.

    Google Scholar 

12. R.W. Ritchie, F.N. Springsteel: Language recognition by marking automata, Inf. Contr. 20, 313–330.

    Google Scholar 

13. I.H. Sudborough: On tape bounded complexity classes and multi-head finite automata, JCSS 10, 177–192.

    Google Scholar 

14. R. Verbeek: Time-space tradeoffs for general recursion, 22nd IEEE-FOCS, pp. 228–234.

    Google Scholar 

15. R. Verbeek: Complexity of pushdown computations, Institut für Informatik der Universität Bonn.

    Google Scholar 

Download references