Algebraic and Logical Characterizations of Quantum Bchi Automata
Han Zhao-wei · Dianzi xuebao · 2013
The notion of quantum Bchi 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 Bchi 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 Bchi theorem to quantum setting.