Strong optimal lower bounds for Turing machines that accept nonregular languages | SpringerLink
Skip to main content
Springer Nature Link
Log in

Strong optimal lower bounds for Turing machines that accept nonregular languages

  • Contributed Papers
  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 1995 (MFCS 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 969))

Abstract

In this paper, simultaneous lower bounds on space and input head reversals for deterministic, nondeterministic and alternating Turing machines accepting nonregular languages are studied.

Three notions of space complexity, namely strong, middle, and weak, are considered; moreover, another notion called accept, is introduced. For all cases we obtain tight lower bounds. In particular, we prove that while in the deterministic and nondeterministic case these bounds are “strongly” optimal—in the sense that we exhibit a nonregular language over a unary alphabet exactly fitting them—in the alternating case optimal lower bounds for tally languages turn out to be higher than those for arbitrary languages.

This work was supported in part by the ESPRIT Basic Research Action No. 6317: “Algebraic and Syntactic Methods in Computer Science (ASMICS 2)” and by the Ministero dell'Università e della Ricerca Scientifica e Tecnologica (MURST).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. M. Alberts. Space complexity of alternating Turing machines. In Fundamentals of Computation Theory, Proceedings, Lecture Notes in Computer Science 199, pages 1–7. Springer Verlag, 1985.

    Google Scholar 

  2. H. Alt and K. Mehlhorn. A language over a one symbol alphabet requiring only O(log log n) space. SIGAGT news, 7:31–33, 1975.

    Google Scholar 

  3. J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I. EATCS Monographs on Theoretical Computer Science 11. Springer Verlag, 1987.

    Google Scholar 

  4. A. Bertoni, C. Mereghetti, and G. Pighizzini. On languages accepted with simultaneous complexity bounds and their ranking problem. In Mathematical Foundations of Computer Science 1994, Proceedings, Lecture Notes in Computer Science 841, pages 245–255. Springer Verlag, 1994.

    Google Scholar 

  5. A. Bertoni, C. Mereghetti, and G. Pighizzini. An optimal lower bound for nonregular languages. Information Processing Letters, 50:289–292, 1994. Corrigendum. ibid., 52:339, 1994.

    Google Scholar 

  6. A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28:114–133, 1981.

    Article  Google Scholar 

  7. C. Damm and M. Holzer. Inductive counting below LOGSPACE. In Mathematical Foundations of Computer Science 1994, Proceedings, Lecture Notes in Computer Science 841, pages 276–285. Springer Verlag, 1994.

    Google Scholar 

  8. R. Freivalds. On time complexity of deterministic and nondeterministic Turing machines. Latvijskij Matematiceskij Eshegodnik, 23:158–165, 1979. (In Russian).

    Google Scholar 

  9. V. Geffert. Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Computing, 20:484–498, 1991.

    Google Scholar 

  10. V. Geffert. Tally version of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space. SIAM J. Computing, 22:102–113, 1993.

    Google Scholar 

  11. F. Hennie. One-tape, off-line Turing machine computations. Information and Control, 8:553–578, 1965.

    Article  Google Scholar 

  12. J. Hopcroft and J. Ullman. Some results on tape-bounded Turing machines. Journal of the ACM, 16:168–177, 1969.

    Google Scholar 

  13. J. Hopcroft and J. Ullman. Introduction to automata theory, languages, and computations. Addison-Wesley, Reading, MA, 1979.

    Google Scholar 

  14. K. Iwama. ASPACE(o(log log n)) is regular. SIAM J. Computing, 22:136–146, 1993.

    Google Scholar 

  15. M. LiŚekiewicz and R. Reischuk. The complexity world below logarithmic space. In Structure in Complexity Theory, Proceedings, pages 64–78, 1994.

    Google Scholar 

  16. R. Stearns, J. Hartmanis, and P. Lewis. Hierarchies of memory limited computations. In IEEE Conf. Record on Switching Circuit Theory and Logical Design, pages 179–190, 1965.

    Google Scholar 

  17. M. Sipser. Halting space-bounded computations. Theoretical Computer Science, 10:335–338, 1980.

    Google Scholar 

  18. I. Sudborough. Efficient algorithms for path system problems and applications to alternating and time-space complexity classes. In Proc. 21st IEEE Symposium on Foundations of Computer Science, pages 62–73, 1980.

    Google Scholar 

  19. A. Szepietowski. Remarks on languages acceptable in log log n space. Information Processing Letters, 27:201–203, 1988.

    Google Scholar 

  20. A. Szepietowski. Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science 843. Springer Verlag, 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Scienze dell'Informazione, Universitá degli Studi di Milano, via Comelico, 39, 20135, Milano, Italy

    Alberto Bertoni, Carlo Mereghetti & Giovanni Pighizzini

Authors
  1. Alberto Bertoni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlo Mereghetti
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giovanni Pighizzini
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jiří Wiedermann Petr Hájek

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bertoni, A., Mereghetti, C., Pighizzini, G. (1995). Strong optimal lower bounds for Turing machines that accept nonregular languages. In: Wiedermann, J., Hájek, P. (eds) Mathematical Foundations of Computer Science 1995. MFCS 1995. Lecture Notes in Computer Science, vol 969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60246-1_137

Download citation

  • DOI: https://doi.org/10.1007/3-540-60246-1_137

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60246-0

  • Online ISBN: 978-3-540-44768-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation