[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Multihead two-way probabilistic finite automata

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies.

We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Borodin, A., Cook, S., and Pippenger, N. Parallel computation for well-endowed rings and space-bounded probabilistic machines.Information and Control, 48, 1983, pp. 113–136.

    Article  MathSciNet  Google Scholar 

  2. Dijkstra, E. W. Making a fair roulette from a possibly biased coin.Information Processing Letters, 36, 1990, pp. 193–193.

    Article  MATH  Google Scholar 

  3. Dwork, C., and Stockmeyer, L. Finite state verifiers I: The power of interaction.Journal of the Association for Computing Machinery, 39, 1992, pp. 800–828.

    Article  MathSciNet  Google Scholar 

  4. Freivalds, R. Probabilistic two-way machines.Proceedings of the International Symposium on the Mathematical Foundations of Computer Science, 1981. Lecture Notes in Computer Science, 118, 1981, pp. 33–45.

  5. Freivalds, R. Complexity of probabilistic versus deterministic automata.Baltic Computer Science, Selected Papers. Lecture Notes in Computer Science, 502, 1991, pp. 565–613.

  6. Freivalds, R., and Karpinski, M. Lower space bounds for randomized computation.Proceedings of the 21st International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, 820, 1994, pp. 580–592.

  7. Galil, Z. Two-way deterministic pushdown automata and some open problems in the theory of computation.Proceedings of the 15th Annual IEEE Symposium on Switching and Automata Theory, 1974, pp. 170–177.

  8. Gill, J. Computational complexity of probabilistic Turing machines.SIAM Journal on Computing, 6, 1977, pp. 675–695.

    Article  MathSciNet  MATH  Google Scholar 

  9. Hartmanis, J. On non-determinancy in simple computing devices.Acta Informatica, 1, 1972, pp. 336–344.

    Article  MathSciNet  MATH  Google Scholar 

  10. Hartmanis, J., and Stearns, R. E. On the computational complexity of algorithms.Transactions of the American Mathematical Society, 117, 1965, pp. 285–306.

    Article  MathSciNet  MATH  Google Scholar 

  11. Hopcroft, J. E., and Ullman, J. D.Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979.

    MATH  Google Scholar 

  12. Ibarra, O. H. One two-way multihead automata.Journal of Computer and System Sciences, 7, 1973, pp. 28–36.

    Article  MathSciNet  MATH  Google Scholar 

  13. Immerman, N. Nondeterministic space is closed under complementation.SIAM Journal on Computing, 17, 1988, pp. 935–938.

    Article  MathSciNet  MATH  Google Scholar 

  14. Jones, N. D. Space-bounded reducibility among combinatorial problems.Journal of Computer and System Sciences, 11, 1975, pp. 68–75.

    Article  MathSciNet  MATH  Google Scholar 

  15. Jones, N. D., and Lien, Y. E. New problems complete for nondeterministic log space.Mathematical Systems Theory, 10, 1976, pp. 1–17.

    Article  MathSciNet  MATH  Google Scholar 

  16. Jung, H. Relationships between probabilistic and deterministic tape complexity.Proceedings of the International Symposium on the Mathematical Foundations of Computer Science, 1981. Lecture Notes in Computer Science, 118, 1981, pp. 339–346.

  17. Jung, H. On probabilistic tape complexity and fast circuits for matrix inversion problems.Proceedings of the 11th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, 172, 1984, pp. 281–291.

  18. Jung, H. On probabilistic time and space.Proceedings of the 12th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, 194, 1985, pp. 310–317.

  19. Kaneps, J. Stochasticity of the languages recognizable by 2-way finite probabilistic automata.Diskretnaya Matematika, 1, no 4, 1989, pp. 63–77 (Russian).

    MathSciNet  Google Scholar 

  20. Kaneps, J. Regularity of one-letter languages acceptable by 2-way finite probabilistic automata.Proceedings of the Fundamentals of Computation Theory, 1991. Lecture Notes in Computer Science, 529, 1991, pp. 287–296.

  21. King, K. N. Alternating multihead finite automata.Theoretical Computer Science, 61, 1988, pp. 149–174.

    Article  MathSciNet  MATH  Google Scholar 

  22. Kuklin, Yu. I. Two-way probabilistic automata.Avtomatika i vycislitelnaja tekhnika, No. 5, 1973, pp. 35–36 (Russian).

  23. Lewis II, P. M., Stearn, R., and Hartmanis, J. Memory bounds for recognition of context-free and context-sensitive languages.IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 191–202.

  24. Macarie, I. I. Space-efficient deterministic simulations of probabilistic automata.Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, 775, 1994, pp. 109–122.

  25. Macarie, I. I. Decreasing the bandwidth of a configuration matrix.Information Processing Letters, 53, no. 6, pp. 315–320.

  26. Monien, B. Transformational methods and their application to complexity problems.Acta Informatica, 6, 1976, pp. 95–108.

    Article  MathSciNet  MATH  Google Scholar 

  27. Monien, B. Two-way multihead automata over a one-letter alphabet.R.A.I.R.O. Informatique Theoretique/Theoretical Informatics, 14, no. 1, 1980, pp. 67–82.

    MathSciNet  MATH  Google Scholar 

  28. von Neumann, J. Various techniques used in connection with random digits.John von Neumann, Collected Works, Vol. V. Pergamon, Oxford, 1963, pp. 768–770.

    Google Scholar 

  29. Paz, A.Introduction to Probabilistic Automata. Academic Press, New York, 1971.

    MATH  Google Scholar 

  30. Ravikumar, B. Some observations on 2-way probabilistic finite automata. TR92-208, May 1992. Department of Computer Science and Statistics, University of Rhode Island.

  31. Ruby, S. S., and Fischer, P. C. Translational methods and computational complexity.IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 173–178.

  32. Ruzzo, W., Simon, J., and Tompa, M. Space-bounded hierarchies and probabilistic computation.Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 215–223.

  33. Santos, E. S. Probabilistic Turing machines and computability.Proceedings of the American Mathematical Society, 22, 1969, pp. 704–710.

    Article  MathSciNet  MATH  Google Scholar 

  34. Santos, E. S. Computability by probabilistic Turing machines.Transactions of the American Mathematical Society, 159, 1971, pp. 165–184.

    Article  MathSciNet  MATH  Google Scholar 

  35. Savitch, W. J. Relationships between nondeterministic and deterministic tape complexity.Journal of Computer and System Sciences, 4, 1970, pp. 177–192.

    Article  MathSciNet  MATH  Google Scholar 

  36. Seiferas, J. I. Relating refined space complexity classes.Journal of Computer and System Sciences, 14, 1977, pp. 100–129.

    Article  MathSciNet  MATH  Google Scholar 

  37. Seiferas, J. I. Techniques for separating space complexity classes.Journal of Computer and System Sciences, 14, 1977, pp. 73–99.

    Article  MathSciNet  MATH  Google Scholar 

  38. Simon, J. On the difference between one and many.Proceedings of the 4th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, 52, 1977, pp. 480–491.

  39. Simon, J. Space-bounded probabilistic Turing machine complexity classes are closed under complement.Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981, pp. 158–167.

  40. Sudborough, I. H. On tape-bounded complexity classes and multihead finite automata.Journal of Computer and System Sciences, 10, 1975, pp. 62–76.

    Article  MathSciNet  MATH  Google Scholar 

  41. Sudborough, I. H. On the tape complexity of deterministic context-free languages.Journal of the Association for Computing Machinery, 25, 1978, pp. 405–414.

    Article  MathSciNet  MATH  Google Scholar 

  42. Szelepcsenyi, R. The method of forced enumeration for nondeterministic automata.Acta Informatica, 26, 1988, pp. 279–284.

    Article  MathSciNet  MATH  Google Scholar 

  43. Turakainen, P. On languages representable in rational probabilistic automata.Annales Academiae Scientiarum Fennicae, AI, 439.

  44. Yao, A. C., and Rivest, R. L.. K + 1 heads are better thanK.Journal of the Association for Computing Machinery, 25, 1978, pp. 337–340.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, SUNY Geneseo, 14454, Geneseo, NY, USA

    I. I. Macarie

  2. Millennium Computer Corporation, 14534, Pittsford, NY, USA

    I. I. Macarie

Authors
  1. I. I. Macarie
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported by the National Science Foundation under Grant No. CDA 8822724 while the author was at the University of Rochester. An extended abstract of this paper appeared in Proceedings, Second Latin American Symposium, LATIN ’95: Theoretical Informatics, Valparaiso, Chile, April 1995.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Macarie, I.I. Multihead two-way probabilistic finite automata. Theory of Computing Systems 30, 91–109 (1997). https://doi.org/10.1007/BF02679455

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation