Institutional Repository
| State succinctness of two-way finite automata with quantum and classical states | |
| Zheng, Shenggen (1); Qiu, Daowen (1); Gruska, Jozef (3); Li, Lvzhou (1); Mateus, Paulo (2); Qiu, D.(issqdw@mail.sysu.edu.cn) | |
| 2013 | |
| Source | Theoretical Computer Science
 |
| ISSN | 3043975 |
| Volume | 499Pages:98-112 |
| English Abstract | Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any mΕZ+ and any ∈<1/2, we show that:there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error ∈ in a polynomial expected running time with a constant number (that depends neither on m nor on Ε) of quantum states and O(log1/∈) classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m+2, √logm, and √3(logm)/b, respectively;there exists a language Ltwin(m)={wcw|wΕ{ a,b}*,|w|=m} over the alphabet Σ={a,b,c} which can be recognized by a 2QCFA with one-sided error ∈ in an exponential expected running time with a constant number of quantum states and O(log1/∈) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m, √m, and √3m/b, respectively; where b is a constant. © 2013 Elsevier B.V.; Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any mΕZ+ and any ∈<1/2, we show that:there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error ∈ in a polynomial expected running time with a constant number (that depends neither on m nor on Ε) of quantum states and O(log1/∈) classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m+2, √logm, and √3(logm)/b, respectively;there exists a language Ltwin(m)={wcw|wΕ{ a,b}*,|w|=m} over the alphabet Σ={a,b,c} which can be recognized by a 2QCFA with one-sided error ∈ in an exponential expected running time with a constant number of quantum states and O(log1/∈) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m, √m, and √3m/b, respectively; where b is a constant. © 2013 Elsevier B.V. |
| Indexed Type | SCI ; EI |
| Keyword | Computing Models Quantum Finite Automata State Complexity Succinctness |
| Department | (1) Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China; (2) Departamento de Matemática, Instituto Superior Técnico, Technical University of Lisbon, Av. Rovisco Pais 1049-001, Lisbon, Portugal; (3) Faculty of Informatics, Masaryk University, Brno, Czech Republic; (4) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China |
| Language | 英语 |
| WOS ID | WOS:000323809200007 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16918 |
| Collection | 中国科学院软件研究所 |
| Corresponding Author | Qiu, D.(issqdw@mail.sysu.edu.cn) |
| Recommended Citation GB/T 7714 | Zheng, Shenggen ,Qiu, Daowen ,Gruska, Jozef ,et al. State succinctness of two-way finite automata with quantum and classical states[J]. Theoretical Computer Science,2013,499:98-112. |
| APA | Zheng, Shenggen ,Qiu, Daowen ,Gruska, Jozef ,Li, Lvzhou ,Mateus, Paulo ,&Qiu, D..(2013).State succinctness of two-way finite automata with quantum and classical states.Theoretical Computer Science,499,98-112. |
| MLA | Zheng, Shenggen ,et al."State succinctness of two-way finite automata with quantum and classical states".Theoretical Computer Science 499(2013):98-112. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment