publication . Preprint . Part of book or chapter of book . 2002

Probabilistic Reversible Automata and Quantum Automata

Marats Golovkins; Maksim Kravtsev;
Open Access English
  • Published: 16 Sep 2002
Abstract
Comment: COCOON 2002, extended version of the paper, 22 pages
Subjects
arXiv: Computer Science::Formal Languages and Automata TheoryNonlinear Sciences::Cellular Automata and Lattice Gases
free text keywords: Computer Science - Computational Complexity, Computer Science - Formal Languages and Automata Theory, Quantum Physics, F.1.1, F.4.3, Nested word, Quantum finite automata, Nondeterministic finite automaton, Combinatorics, Quantum cellular automaton, Computer science, Mobile automaton, Discrete mathematics, Continuous spatial automaton, ω-automaton, Automata theory
Related Organizations
Download fromView all 2 versions
http://arxiv.org/pdf/cs/020901...
Part of book or chapter of book
Provider: UnpayWall
http://link.springer.com/conte...
Part of book or chapter of book
Provider: Crossref

AF 98. A. Ambainis, R. Freivalds. 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. Proc. 39th FOCS, 1998, pp. 332-341. http://arxiv.org/abs/quant-ph/9802062 [OpenAIRE]

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. http://arxiv.org/abs/quant-ph/0009004

BP 99. A. Brodsky, N. Pippenger. Characterizations of 1-Way Quantum Finite Automata. http://arxiv.org/abs/quant-ph/9903014

GS 97. C. M. Grinstead, J. L. Snell. Introduction to Probability. American Mathematical Society, 1997. http://www.dartmouth.edu/~chance/teaching 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. [OpenAIRE]

MC 97. C. Moore, J. P. Crutchfield. Quantum Automata and Quantum Grammars. Theoretical Computer Science, 2000, Vol. 237(1-2), pp. 275-306. http://arxiv.org/abs/quant-ph/9707031

N 99. A. Nayak. Optimal Lower Bounds for Quantum Automata and Random Access Codes. Proc. 40th FOCS, 1999, pp. 369-377. http://arxiv.org/abs/quant-ph/9904093

R 63. M. O. Rabin. Probabilistic Automata. Information and Control, 1963, Vol. 6(3), pp. 230-245.

T 68. G. Thierrin. Permutation Automata. Mathematical Systems Theory, 1968, Vol. 2(1), pp. 83-90. 1 n−1 1

n2η02 Xi=0 pi,ω(1 − pi,ω) ≤ 4nη02

≥ 1 − 4n1η02 . So, taking into

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Part of book or chapter of book . 2002

Probabilistic Reversible Automata and Quantum Automata

Marats Golovkins; Maksim Kravtsev;