@inproceedings{94e4dc193e3046aa8e05665ab8f4cfb4,
title = "Languages recognized with unbounded error by quantum finite automata",
abstract = "We prove the following facts about the language recognition power of Kondacs-Watrous quantum finite automata in the unbounded error setting: One-way automata of this kind recognize all and only the stochastic languages. When the tape head is allowed two-way (or even {"}1.5-way{"}) movement, more languages become recognizable. This leads to the conclusion that quantum Turing machines are more powerful than probabilistic Turing machines when restricted to constant space bounds.",
author = "Abuzer Yakaryilmaz and Say, \{A. C.Cem\}",
year = "2009",
doi = "10.1007/978-3-642-03351-3\_33",
language = "English",
isbn = "3642033504",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "356--367",
booktitle = "Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings",
note = "4th International Computer Science Symposium in Russia, CSR 2009 ; Conference date: 18-08-2009 Through 23-08-2009",
}