Multiple Usage of Random Bits in Finite Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

Multiple Usage of Random Bits in Finite Automata

  • Conference paper
Theory and Applications of Models of Computation (TAMC 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7287))

Abstract

Finite automata with random bits written on a separate 2-way readable tape can recognize languages not recognizable by probabilistic finite automata. This shows that repeated reading of random bits by finite automata can have big advantages over one-time reading of random bits.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences 36(2), 254–276 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barzdin, J.M.: On a Class of Turing Machines (Minsky Machines). Algebra i Logika 3(1) (1963) (Russian); Review in the Journal of Symbolic Logic 32(4), 523–524 (1967)

    Google Scholar 

  3. Calude, C.S., Staiger, L.: Generalisations of disjunctive sequences. Mathematical Logic Quarterly 51(2), 120–128 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dwork, C., Stockmeyer, L.: Finite state verifiers I: the power of interaction. Journal of the Association for Computing Machinery 39(4), 800–828 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  5. Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) SIAM-AMS Proceedings of the Complexity of Computation, vol. 7, pp. 27–41 (1974)

    Google Scholar 

  6. Freivalds, R.: Probabilistic machines can use less running time. In: Gilchrist, B. (ed.) Information Processing 1977, Proceedings of IFIP Congress 1977, pp. 839–842. North-Holland, Amsterdam (1977)

    Google Scholar 

  7. Freivalds, R.: Probabilistic Two-way Machines. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol. 118, pp. 33–45. Springer, Heidelberg (1981)

    Chapter  Google Scholar 

  8. Freivalds, R.: Complexity of Probabilistic Versus Deterministic Automata. In: Barzdins, J., Bjorner, D. (eds.) Baltic Computer Science. LNCS, vol. 502, pp. 565–613. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  9. Freivalds, R.: Non-constructive methods for finite probabilistic automata. International Journal of Foundations of Computer Science 19(3), 565–580 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Freivalds, R.: Amount of nonconstructivity in finite automata. Theoretical Computer Science 411(38-39), 3436–3443 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge complexity of interactive proof-systems. In: Proceedings of ACM STOC 1985, pp. 291–304 (1985)

    Google Scholar 

  12. Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of ACM STOC 1986, pp. 58–68 (1986)

    Google Scholar 

  13. Immerman, N.: Descriptive Complexity, pp. 113–119. Springer, New York (1999)

    MATH  Google Scholar 

  14. Jürgensen, H., Thierrin, G.: On ω-Languages whose syntactic monoid is trivial. International Journal of Parallel Programming 12(5), 359–365 (1983)

    MATH  Google Scholar 

  15. Karp, R.M., Lipton, R.: Turing machines that take advice. L’ Enseignement Mathematique 28, 191–209 (1982)

    MathSciNet  MATH  Google Scholar 

  16. Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems in Information Transmission 1, 1–7 (1965)

    MathSciNet  Google Scholar 

  17. Levin, L.A.: On the notion of a random sequence. Soviet Mathematics Doklady 14, 1413–1416 (1973)

    MATH  Google Scholar 

  18. Martin-Löf, P.: The definition of random sequences. Information and Control 9(6), 602–619 (1966)

    Article  MathSciNet  Google Scholar 

  19. Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer (1997)

    Google Scholar 

  20. Newman, I.: Private vs. common random bits in communication complexity. Information Processing Letters 39, 67–71 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  21. Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Information Processing Letters 90(4), 195–204 (2004)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  23. Schnorr, C.-P.: A unified approach to the definition of random sequences. Mathematical Systems Theory 5(3), 246–258 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  24. Schnorr, C.-P.: Process complexity and effective random tests. Journal of Computer and System Sciences 7(4), 376–388 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  25. Shannon, C.: Communication theory of secrecy systems. Bell System Technical Journal 28(4), 656–715 (1949)

    MathSciNet  MATH  Google Scholar 

  26. Tadaki, K., Yamakami, T., Lin, J.C.H.: Theory of one-tape linear-time Turing machines. Theoretical Computer Science 411(1), 22–43 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  27. Yamakami, T.: The Roles of Advice to One-Tape Linear-time Turing machines and finite automata. International Journal of Foundations of Computer Science 21(6), 941–962 (2010)

    Article  MathSciNet  MATH  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

    Rūsiņš Freivalds

Authors
  1. Rūsiņš Freivalds
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, Resource Planning and Generation, Indian Institute of Technology Kanpur, 208016, Kanpur, India

    Manindra Agrawal

  2. Department of Pure Mathematics, Leeds, University of Leeds, LS2 9JT, UK

    S. Barry Cooper

  3. Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, 100190, Beijing, P.R. China

    Angsheng Li

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Freivalds, R. (2012). Multiple Usage of Random Bits in Finite Automata. In: Agrawal, M., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2012. Lecture Notes in Computer Science, vol 7287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29952-0_50

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-29952-0_50

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-29951-3

  • Online ISBN: 978-3-642-29952-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation