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

Algebraic and Logical Characterizations of Quantum Bchi Automata

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

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 secondorder quantum logic（LVMSO in short）,the monadic second-order logic characterizations of infinite regular languages recognized by quantum Biichi automata are presented,which deepen and generalize the fundamental Bchi theorem to quantum setting.