Dense quantum coding and quantum finite automata, Journal of the ACM, vol.49, issue.4, pp.496-511, 2002. ,
DOI : 10.1145/581771.581773
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.7649
Two-way finite automata with quantum and classical states, Theoretical Computer Science, vol.287, issue.1, pp.299-311, 2002. ,
DOI : 10.1016/S0304-3975(02)00138-X
Regular Languages Accepted by Quantum Automata, Information and Computation, vol.165, issue.2, pp.174-182, 2001. ,
DOI : 10.1006/inco.2000.2911
A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata, SIAM Journal on Computing, vol.19, issue.6, pp.1011-1123, 1990. ,
DOI : 10.1137/0219069
Finite state verifiers I: the power of interaction, Journal of the ACM, vol.39, issue.4, pp.800-828, 1992. ,
DOI : 10.1145/146585.146599
Lower space bounds for randomized computation, ICALP'94: Proceedings of the 21st International Colloquium on Automata, Languages and Programming, pp.580-592, 1994. ,
DOI : 10.1007/3-540-58201-0_100
Improved constructions of mixed state quantum automata [Fre81] R¯ usin¸?usin¸usin¸? s Freivalds. Probabilistic two-way machines, Proceedings of the International Symposium on Mathematical Foundations of Computer ScienceFYS10] R¯ usin¸?usin¸usin¸? s Freivalds, Abuzer Yakary?lmaz, and A. C. Cem Say. A new family of nonstochastic languages. Information Processing Letters, pp.4101923-1931, 1981. ,
A lower bound for probabilistic algorithms for finite state machines, Journal of Computer and System Sciences, vol.33, issue.1, pp.88-105, 1986. ,
Various Aspects of Finite Quantum Automata, DLT'08: Proceedings of the 12th international conference on Developments in Language TheoryKan¸91Kan¸91] J¯ anis Kan¸epsKan¸eps. Stochasticity of the languages acceptable by two-way finite probabilistic automata. Discrete Mathematics and Applications, pp.21-33405, 1991. ,
DOI : 10.1007/978-3-540-85780-8_2
Minimal nontrivial space complexity of probabilistic one- way turing machines, In Proceedings on Mathematical Foundations of Computer Science Lecture Notes in Computer Science, vol.452, pp.355-361, 1990. ,
DOI : 10.1007/BFb0029629
On the power of quantum finite state automata, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.66-75, 1997. ,
DOI : 10.1109/SFCS.1997.646094
Oksana Scegulnaja-Dubrovska, and R¯ usin¸?usin¸usin¸? s Freivalds. Languages recognizable by quantum finite automata with cut-point 0, SOFSEM'09: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science, pp.35-46, 2009. ,
Closure properties of stochastic languages, 1993. ,
Quantum finite automata using ancilla qubits, 2000. ,
Introduction to Probabilistic Automata, 1971. ,
Introduction to the Theory of Computation, ACM SIGACT News, vol.27, issue.1, 2006. ,
DOI : 10.1145/230514.571645
On languages representable in rational probabilistic automata, Annales Academiae Scientiarum Fennicae Series A I Mathematica, vol.1969, issue.439, pp.4-10, 1969. ,
DOI : 10.5186/aasfm.1969.439
On the power of 2-way quantum finite state automata, 1997. ,
Space-bounded quantum computation, 1998. ,
DOI : 10.1006/jcss.1999.1655
URL : http://doi.org/10.1006/jcss.1999.1655
Languages recognized by nondeterministic quantum finite automata. Quantum Information and Computation. (To Appear) (Also available at arXiv:0902, 2081. ,
Efficient probability amplification in two-way quantum finite automata, Theoretical Computer Science, vol.410, issue.20, pp.1932-1941, 2009. ,
DOI : 10.1016/j.tcs.2009.01.029
Languages Recognized with Unbounded Error by Quantum Finite Automata, CSR'09: Proceedings of the Fourth International Computer Science Symposium in Russia, pp.356-367, 2009. ,
DOI : 10.1006/jcss.1999.1655
Unbounded-error quantum computation with small space bounds. in preparation, 2010. ,