Lower bounds on the size of semi-quantum finite automata

详细信息    查看全文

• 作者：Lvzhou Li ; ^{lilvzh@mail.sysu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Daowen Qiu ^{issqdw@mail.sysu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Quantum finite automata ; Semi-quantum finite automata ; Descriptional complexity
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：11 April 2016
• 年：2016
• 卷：623
• 期：Complete
• 页码：75-82
• 全文大小：295 K

文摘

In the literature, there exist several interesting hybrid models of finite automata which have both quantum and classical states. We call them semi-quantum finite automata. In this paper, we compare the descriptional power of these models and DFA. Specifically, we present a uniform method that gives a lower bound on the size of the three existing main models of semi-quantum finite automata, and this bound shows that semi-quantum finite automata can be at most exponentially more concise than DFA. Compared with a recent work [4], our method has the following two advantages: (i) it is much more concise; and (ii) it is universal, since it is applicable to the three existing main models of semi-quantum finite automata, instead of only one specific model.