量子B&uuml;chi自动机的代数及逻辑刻画

doi:10.3969/j.issn.0372-2112.2013.06.009

PDF(713 KB)

电子学报 ›› 2013, Vol. 41 ›› Issue (6) : 1093-1100. DOI: 10.3969/j.issn.0372-2112.2013.06.009

学术论文

量子Büchi自动机的代数及逻辑刻画

韩召伟

作者信息 +

Algebraic and Logical Characterizations of Quantum Büchi Automata

HAN Zhao-wei

Author information +

文章历史 +

摘要

提出量子Büchi自动机(简记为LVBA)的概念,利用量子状态构造方法证明了一般LVBA与状态转移为经典函数的LVSBA间的相互等价性,籍此研究了量子无穷正则语言的代数刻画、层次刻画和Büchi刻画以及对于正则运算的封闭性;通过引入单体二阶量子逻辑(简记为LVMSO)的概念,给出量子Büchi自动机所识别无穷语言的单体二阶逻辑描述,深化和推广了量子逻辑意义下的Büchi基本定理.

Abstract

The notion of quantum Büchi automaton (LVBA for short)is introduced,by means of quantum state construction,the equivalence of an LVBA and an LVSBA with crisp transition function is proved,based on this,the algebraic and level characterizations and also the Büchi characterization of quantum infinite regular languages are investigated,and also the closed properties of those quantum infinite regular languages under some regular operations are dealt with.By providing the concept of monadic second-order quantum logic(LVMSO in short),the monadic second-order logic characterizations of infinite regular languages recognized by quantum Büchi automata are presented,which deepen and generalize the fundamental Büchi theorem to quantum setting.

导出引用

韩召伟. 量子Büchi自动机的代数及逻辑刻画[J]. 电子学报, 2013, 41(6): 1093-1100. https://doi.org/10.3969/j.issn.0372-2112.2013.06.009

HAN Zhao-wei. Algebraic and Logical Characterizations of Quantum Büchi Automata[J]. Acta Electronica Sinica, 2013, 41(6): 1093-1100. https://doi.org/10.3969/j.issn.0372-2112.2013.06.009

中图分类号： TP301.1 O153.1

参考文献

[1] Gruska J,Quantum Computing[M].London:McGraw-Hill,1999.

[2] Nielsen MA,Chuang IL.Quantum Computation and Quantum Information[M].Cambridge:Cambridge University,2004.

[3] Zhong ShuQin,MA Zhi,XU YaJie,Constructing quantum error correcting code via logic function[J].Science China Information Sciences,2010,53(3):515-523.

[4] Cao HuaiXin,LI Li,Chen ZhengLi,Zhang Ye,Guo ZhiHua.Restricted allowable generalized quantum gates[J].Chinese Science Bulletin,2010,55 (20):2122-2125.

[5] Barenco A,Bennett CH,Cleve R.Elementary gates for quantum computation[J].Physical Review A,1995,52(5):3457-3467.

[6] Liu Y,Long GL,Sun Y.Analytic one-bit and CNOT gate constructions of general n-qubit controlled gates[J].International Journal of Quantum Information,2008,6(3):447-462.

[7] Ying Mingsheng.A theory of computation based on quantum logic(I)[J].Theoretical Computer Science,2005,344(2-3):134-207.

[8] Ying Mingsheng.Quantum logic and automata theory[A].Handbook of Quantum Logic and Quantum Structures[C].Amsterdam:Elsevier,2007.619-754.

[9] 李永明.基于量子逻辑的有穷自动机与单体二阶量子逻辑[J].中国科学F辑:信息科学,2009,39(11):1135-1145.

[10] 韩召伟,李永明.基于量子逻辑的下推自动机与上下文无关文法[J].软件学报,2010,21(9):2107-2117. Han Zhaowei,Li Yongming.Pushdown automata and context-free grammars based on quantum logic[J].Journal of Software,2010,21(9):2107-2117.(in Chinese)

[11] 韩召伟.量子无穷正则语言的代数性质[J].陕西师范大学学报(自然科学版),2012,40(5):9-13. Han Zhaowei.Algebraic properties of quantum infinite languages[J].Journal of Shaanxi Normal University(Natural Science Edition),2012,40(5):9-13.(in Chinese)

[12] Clarke EM,Grumberg O,Peled DA.Model Checking[M].Cambridge:MIT Press,2000.

[13] Baier C,Katoen JP.Principles of Model Checking[M].Massachusetts:The MIT Press,2008.

[14] Khoussainov B,Nerode A.Automata Theory and Its Applications[M].Boston:Birkuser,2001.

[15] Thomas W.Languages,automata and logic[A].Handbook of Formal Languages[C].Berlin,Heidelberg:Springer Verlag,1997.389-485.

[16] Thomas W.Automata on infinite objects[A].Handbook of Theoretical Computer Science[C].Amsterdam:Elsevier,1990.133-191.

[17] Farwer B.ω-automata[A].Automata,Logics,and Infinite Games,LNCS 2500[C].Berlin,Heidelberg:Springer-Verlag,2002.3-21.

[18] Perrin D,Pin J?.Infinite Words[M].Amsterdam:Elsevier,2004.

[19] Kalmbach G.Orthomodular Lattices[M].London:Academic Press,1983.

[20] Li Yongming,Li Zhihui.Free semilattices and strongly free semilattices generated by partially ordered sets[J].Northeastern Mathematical Journal,1993,9(3):359-366.