Probabilistic Reversible Automata and Quantum Automata

Preprint English OPEN
Golovkins, Marats; Kravtsev, Maksim;
  • Subject: F.4.3 | Computer Science - Computational Complexity | Computer Science - Formal Languages and Automata Theory | Quantum Physics | F.1.1
    arxiv: Nonlinear Sciences::Cellular Automata and Lattice Gases | Computer Science::Formal Languages and Automata Theory

To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA... View more
  • References (14)
    14 references, page 1 of 2

    AF 98. A. Ambainis, R. Freivalds. 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. Proc. 39th FOCS, 1998, pp. 332-341.

    AKV 00. A. Ambainis, A. K¸ ikusts, M. Valdats. On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. STACS 2001, Lecture Notes in Computer Science, 2001, Vol. 2010, pp. 75-86.

    BP 99. A. Brodsky, N. Pippenger. Characterizations of 1-Way Quantum Finite Automata.

    GS 97. C. M. Grinstead, J. L. Snell. Introduction to Probability. American Mathematical Society, 1997. aids/articles.html

    HW 79. G. H. Hardy, E. M. Wright. An Introduction to the Theory of Numbers. Fifth Edition. Oxford University Press, 1979.

    HS 66. J. Hartmanis, R. E. Stearns. Algebraic Structure Theory of Sequential Machines. Prentice Hall, 1966.

    KS 76. J. G. Kemeny, J. L. Snell. Finite Markov Chains. Springer Verlag, 1976.

    KW 97. A. Kondacs, J. Watrous. On The Power of Quantum Finite State Automata. Proc. 38th FOCS, 1997, pp. 66-75.

    MC 97. C. Moore, J. P. Crutchfield. Quantum Automata and Quantum Grammars. Theoretical Computer Science, 2000, Vol. 237(1-2), pp. 275-306.

    N 99. A. Nayak. Optimal Lower Bounds for Quantum Automata and Random Access Codes. Proc. 40th FOCS, 1999, pp. 369-377.

  • Metrics
Share - Bookmark