Computation with Absolutely No Space Overhead

  • Lane A. Hemaspaandra
  • Proshanto Mukherji
  • Till Tantau
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits’ own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that subclasses of the context-free languages can even be accepted in polynomial time with absolutely no space overhead.


space overhead space reuse overhead-free computation context-sensitive languages context-free languages linear space deterministic linear languages metalinear languages 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    A. Amir, G. Landau, and D. Sokol. Inplace run-length 2D compressed search. Theoretical Computer Science, 290(3):1361–1383, 2003.zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    N. Chomsky and M. Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, pages 118–161. North Holland, Amsterdam, 1963.Google Scholar
  3. 3.
    E. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223–233, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    E. Dijkstra and A. van Gastern. An introduction to three algorithms for sorting in situ. Information Processing Letters, 15(3):129–134, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    E. Feldman and J. Owings, Jr. A class of universal linear bounded automata. Information Sciences, 6:187–190, 1973.CrossRefMathSciNetGoogle Scholar
  6. 6.
    K. Fishkin. Performing in-place affine transformations in constant space. In Proceedings of Graphics Interface’ 92, pages 106–114, 1992.Google Scholar
  7. 7.
    V. Geffert, J. Katajainen, and T. Pasanen. Asymptotically efficient in-place merging. Theoretical Computer Science, 237(1–2):159–181, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    J. Geske. Nondeterminism, bi-immunity and almost-everywhere complexity. IEICE Trans. on Communications, Electronics, Information, and Systems, E76, 1993.Google Scholar
  9. 9.
    J. Hartmanis. On non-determinancy in simple computing devices. Acta Informatica, 1:336–344, 1972.zbMATHCrossRefMathSciNetGoogle Scholar
  10. 10.
    L. Hemaspaandra, P. Mukherji, and T. Tantau. Computation with absolutely no space overhead. Technical Report TR-779, Department of Computer Science, University of Rochester, Rochester, NY, May 2002.Google Scholar
  11. 11.
    M. Holzer and K. Lange. On the complexities of linear LL(1) and LR(1) grammars. In Proc. of the 9th Conference on Fundamentals of Computation Theory, volume 710 of Lecture Notes in Computer Science, pages 299–308. Springer-Verlag, 2003.Google Scholar
  12. 12.
    J. Hopcroft and J. Ullman. Formal Languages and their Relation to Automata. Addison-Wesley, 1969.Google Scholar
  13. 13.
    J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.Google Scholar
  14. 14.
    O. Ibarra, T. Jiang, and B. Ravikumar. Some subclasses of context-free languages in NC1. Information Processing Letters, 29(3):111–117, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5):935–938, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    T. Kasami. An efficient recognition and syntax algorithm for context-free languages. Scientific Report AFCRL-65-758, Air Force Cambridge Research Lab., Bedford, Mass., 1965.Google Scholar
  17. 17.
    J. Katajainen and T. Pasanen. In-place sorting with fewer moves. Information Processing Letters, 70:31–37, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    M. Nasu and N. Honda. Mappings induced by PGSM-mappings and some recursively unsolvable problems of finite probabilistic automata. Information and Control, 15(3):250–273, 1969.zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    A. Paz. Introduction to Probabilistic Automata. Academic Press, New York, 1971.zbMATHGoogle Scholar
  20. 20.
    A. Salomaa. Formal Languages. Academic Press, 1973.Google Scholar
  21. 21.
    J. Seiferas. Relating refined space complexity classes. Journal of Computer and System Sciences, 14:100–129, 1977.zbMATHCrossRefMathSciNetGoogle Scholar
  22. 22.
    R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26(3):279–284, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  23. 23.
    D. Younger. Recognition and parsing of context-free languages in time n 3. Information and Control, 10(2):189–208, 1967.zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Lane A. Hemaspaandra
    • 1
  • Proshanto Mukherji
    • 1
  • Till Tantau
    • 2
  1. 1.Department of Computer ScienceUniversity of RochesterRochesterUSA
  2. 2.Fakultät IV — Elektrotechnik und InformatikTechnische Universität BerlinBerlinGermany

Personalised recommendations