量子Büchi自动机的等价刻画

Quantum computing is currently an important research area in computer science, however, one of the scientific issues of crucial importance in this field is the computing model of quantum computation. The main purpose of this study is to generalize the theory of Büchi automata and the related research results of ω -regular languages of classical automata into the frame of quantum logic setting by using semantic analysis. Firstly, by dint of refine and modify the extended subset constructions which we proposed, we obtain the relevant algebraic descriptions of Büchi automata based on quantum logic, and we also establish the corresponding ω-Kleene theorem, which constitute the equivalent algebraic characterizations of Büchi automata in the underlying quantum logic. Secondly, by introducing the concept of the monadic second-order quantum logic, and also based on the “levelization ” processing techniques ,we present the equivalent monadic second-order quantum logic description of quantum Büchi automata. Thirdly, we deal with the closed properties of quantum ω-regular languages in details under some ω-regular operations , and also by providing the notions of first-order quantum logic, ω-star-free quantum ω-language and ω-aperiodic quantum ω-language respectively, we investigate the first-order description of ω-regular quantum languages, and in the mean time, we obtain the classification theorem in the quantum logic setting, which constitutes a sorting scheme of quantum ω-regular languages. Based on these, finally we integrate the computation theory in the quantum logic setting, which aims to provide the theoretical support for quantum model checking based on Büchi automata.

量子计算是当代计算机科学领域重要的研究方向，而量子计算模型是其关键科学问题之一。本项目旨在采用语义分析方法，将Büchi自动机理论以及ω-正则语言相关研究结果推广到量子逻辑框架下。首先，通过细化和改造广义子集构造技术，给出量子逻辑意义下Büchi自动机的相关代数描述，建立对应的ω-Kleene定理，给出Büchi自动机的等价代数刻画。其次，通过引入单体二阶量子逻辑的概念，利用“层次化”处理技巧，给出Büchi自动机的等价单体二阶量子逻辑描述。再次，详细研究了量子ω-正则语言对于ω-正则运算的封闭性，并通过引入ω-星自由和ω-非周期量子ω-语言，建立ω-正则语言的一阶逻辑描述，得到了量子逻辑意义下的分类定理，对量子ω-正则语言给出了一种分类方法。基于此，最终完善基于量子逻辑的计算理论，为基于Büchi自动机的量子模型检测做理论基础准备。

量子计算是当代计算机科学领域重要的研究方向，而量子计算模型是其关键科学问题之一。本项目利用语义分析方法，针对量子逻辑框架下Büchi自动机和ω -正则语言理论进行了深入研究。首先，通过量子状态构造技术，建立量子逻辑意义下Büchi自动机识别语言的相关代数刻画、层次刻画和Büchi刻画，即给出Büchi自动机的等价代数刻画。其次，通过引入单体二阶量子逻辑的概念，利用“层次化”处理技巧，给出Büchi自动机识别语言的等价单体二阶量子逻辑刻画，推广了量子逻辑意义下的Büchi基本定理。再次，通过引入量子有限步可识别语言和量子状态构造方法,建立量子Müller自动机识别语言的代数刻画和层次刻画，同时给出Müller自动机识别语言的等价单体二阶量子逻辑刻画，深化了量子逻辑意义下的Büchi基本定理。最后，分别详细研究了Büchi自动机和Müller自动机识别的量子ω -正则语言对于ω -正则运算的封闭性。另外，通过引入ω -星自由和ω -非周期量子ω -语言，研究了量子ω -正则语言的一阶逻辑描述，得到了量子逻辑意义下的分类定理，对量子ω -正则语言给出了一种分类方法。通过上述工作，我们得到了一些结论，目前已在国内权威学术期刊上发表论文3篇，还有部分工作即将投稿于国内国内及国际学术期刊。