Skip to main content
SpringerLink
Log in

Minimal nontrivial space complexity of probabilistic one- way turing machines

  • Communications
  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 1990 (MFCS 1990)

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

Abstract

Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].

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.

References

  1. R.G. Bukharaev. Fundamentals of the Theory of Probabilistic Automata. Nauka, Moscow, 1985 (Russian).

    Google Scholar 

  2. R. Freivalds. Probabilistic two-way machines. Lecture Notes in Computer Science, Springer, 118: 33–45, 1981.

    Google Scholar 

  3. R. Freivalds. Capabilities of various models of one-way probabilistic automata. Izvestiya VUZ, 5: 26–34, 1981 (Russian).

    Google Scholar 

  4. R. Freivalds. Space and reversal complexity of probabilistic one-way Turing machines. Annals of Discrete Mathematics, 24: 39–50, 1985.

    Google Scholar 

  5. J.T.Gill. Computational complexity of probabilistic Turing machines. In Proc. 6th ACM Symposium on Theory of Computation, 91–96, 1974.

    Google Scholar 

  6. V.B. Kudrjavcev,S.V. Aleshin,A.S. Podkolzin. Introduction into Theory of Automata. Nauka, Moscow, 1985 (Russian).

    Google Scholar 

  7. M.O. Rabin. Probabilistic automata. Information and Control 6(3): 230–245, 1963.

    Google Scholar 

  8. R.E.Stearns,J.Hartmanis and P.M.Lewis II. Hierarchies of Memory Limited Computation. In Proc. IEEE Symposium on Switching Circuit Theory and Logical Design, 179–190, 1965.

    Google Scholar 

  9. B.A.Trakhtenbrot and J.M.Barzdin. Finite Automata (Behavior and Synthesis). North-Holland, 1972.

    Google Scholar 

  10. B.A. Trakhtenbrot. Notes on computational complexity by probabilistic machines. In Theory of Algorithms and Mathematical Logics, VC AN SSSR, Moscow, 159–176, 1974 (Russian).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics and Computer Science, University of Latvia, Raiņa bulvāris 29, Rīga, Latvia

    Jānis Kaņeps & Rūsiņš Freivalds

Authors
  1. Jānis Kaņeps
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rūsiņš Freivalds
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Branislav Rovan

Rights and permissions

Reprints and permissions

Copyright information

© 1990 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kaņeps, J., Freivalds, R. (1990). Minimal nontrivial space complexity of probabilistic one- way turing machines. In: Rovan, B. (eds) Mathematical Foundations of Computer Science 1990. MFCS 1990. Lecture Notes in Computer Science, vol 452. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029629

Download citation

  • DOI: https://doi.org/10.1007/BFb0029629

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-52953-8

  • Online ISBN: 978-3-540-47185-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation