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) |
| 刊名 | Theoretical Computer Science
 |
| 出版日期 | 2013 |
| 卷号 | 499页码:98-112 |
| 关键词 | Computing models Quantum finite automata State complexity Succinctness |
| ISSN号 | 3043975 |
| 通讯作者 | Qiu, D.(issqdw@mail.sysu.edu.cn) |
| 中文摘要 | 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. |
| 收录类别 | SCI ; EI |
| 语种 | 英语 |
| WOS记录号 | WOS:000323809200007 |
| 公开日期 | 2014-12-16 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16918]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 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 .(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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。