量子Müller自动机与单体二阶量子逻辑  

Quantum Müller Automata and Monadic Second-Order Quantum Logic

作　　者：韩召伟[1,2] 李永明[2] 

机构地区：[1]陕西师范大学数学与信思科学学院,陕西西安710062 [2]陕西师范大学计算机科学学院,陕西西安710062

出　　处：《软件学报》2014年第1期27-36,共10页Journal of Software

基　　金：国家自然科学基金(11271237,11226266);陕西师范大学科研启动基金(999553)

摘　　要：给出量子Müller自动机(简称LVMA)的概念,通过引入量子有限步可识别语言和量子状态构造方法,证明了在量子逻辑意义下4类量子Müller自动机彼此相互等价.利用该等价性,建立了量子无穷正则语言的代数刻画和层次刻画,籍此研究了量子无穷正则语言关于无穷正则运算的封闭性.同时,给出了量子Müller自动机所识别语言的单体二阶逻辑描述,深化和推广了量子逻辑意义下的Büchi基本定理.This paper introduces the notion of quantum Miiller automaton （LVMA）, provides the concept of quantum recognizable finite step language and the means of quantum state construction, and then proves the fact that four types of LVMA can equivalently constructed from each other. By using those equivalent relations, it establishes the algebraic and level characterizations of quantum regular infinite languages, and also explores the closed properties of these quantum infinite languages in details under some infinite regular operations in particular at the same time. Meanwhile, this study shows that the behaviors of quantum Mtlller automata are precisely the quantum languages definable with sentences of the monadic second-order quantum logic （LVMSO）, expanding the fundamental Biichi theorem to quantum setting.

关 键 词：量子逻辑 正交模格 量子Müller自动机 量子无穷正则语言 单体二阶量子逻辑 Büchi定理 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]