量子计算的思想源于物理与计算之间的联系.由于可逆性是量子物理的一个重要特征,所以该问题可追溯到Bennett于1973年证明了任意的Turing机都能被可逆的Turing机有效地模拟Benioff于1980年构造了一类基于量子力学原理的Turing计算模型,并证明它能模拟经典的可逆Turing机.其后不久,Feynman提出了一个本质的猜想：经典Turing机模拟一些量子现象的计算速度很可能呈指数下降Deutsch于1985年重新考察Church-Turing原理,并将Feynman的思想形式化,从而定义了量子Turing机.特别是Shor于1994年发现了在量子计算机上进行大数分解的多项式时间算法,Grover于1996年发现了平方根时间的量子搜索算法之后,量子计算日益受到人们的关注和重视.量子计算模型的研究是量子计算中的一个重要的研究问题,而量子有穷自动机可看作一类具有有限内存的量子计算机模型,作为量子计算理论中最简单的数学模型.最近由应明生等建立的基于量子逻辑的有穷自动机理论是量子计算模型方面的一个重要研究方向.目前已经得到了很多与经典逻辑意义下不同的结果,并试图揭示量子计算的逻辑基础问题,其本身可以认为是一般有穷自动机理论的深化和推广.特别地,应明生给出了基于量子逻辑的自动机的重要定理的成立都依赖于正交模格中子集的交换子的条件,即就是对应的定理的完全成立依赖于正交模格的分配律,从而又还原到布尔逻辑或者经典逻辑的情形.其后,通过对应明生建立的基于量子逻辑的自动机理论和正交模格的深入分析,李永明等提出了广义子集构造技术,籍此证明了量子逻辑意义下自动机的重要定理和相关结论的成立本身并不需要分配律(交换子)作为支撑,这使得基于量子逻辑的自动机理论得到了更进一步的深化和提升.本文主要利用语义分析和量子状态构造方法,在不满足分配律的量子逻辑意义下进一步对下推自动机和Buchi自动机以及Muller自动机进行详细研究,同时讨论了它们的代数与逻辑刻画,得到了量子逻辑意义下比较完善和本质以及深刻的结果.本文的主要工作具体有以下几个方面：(1)基于量子逻辑的下推自动机的代数刻画.提出了基于量子逻辑的下推自动机—量子下推自动机(简记为LVPDA)的概念,利用量子状态构造方法,给出此类自动机的代数刻画,即证明了一般LVPDA与状态转移为经典函数且具有量子终状态的CVSPDA的等价性,证明了以终态方式接受语言与以空栈方式接受语言的下推自动机之间的相互等价性；其次提出了量子上下文无关文法(简记为LVCFG)的概念,并研究了其具有的代数刻画,证明了量子上下文无关文法LVCFG和Chomsky范式文法(简记为LVCNF)以及Greibach范式文法(简记为LVGNF)的相互等价性；再次证明了量子下推自动机(LVPDA)和量子上下文无关文法(LVCFG)的相互等价性；最后详细研究了量子上下文无关语言的代数刻画和层次刻画以及对于正则运算的封闭性,利用得到的LVCFG的代数刻画给出了判定L-值上下文无关语言的泵引理.(2)基于量子逻辑的Buchi自动机的代数刻画.提出基于量子逻辑的Buchi自动机(简记为LVBA)的概念,从代数角度出发详细研究了此类自动机的性质,注意到LVBA识别语言的像集是有限的,通过引入(?)-值有限步ω-语言,并结合量子状态构造方法,给出了(?)-值ω-正则语言的代数刻画、层次刻画以及Buchi刻画；研究了几类Buchi自动机之间的等价关系以及确定型Buchi自动机识别语言的代数刻画；另外将经典的ω-正则表达式理论建立在量子逻辑意义下,通过引入(?)-值ω-正则表达式的概念,建立了(?)-值ω-Kleene定理,从而给出(?)VMA识别的(?)-值ω-语言的等价代数刻画.(3)基于量子逻辑的Muller自动机的代数刻画.首先,提出基于量子逻辑的Muller自动机(简记为LVMA)的概念,从代数角度出发详细研究了此类自动机的性质,注意到LVMA识别语言的像集是有限的,通过引入(?)-值有限步ω-语言,并结合量子状态构造方法,证明了在量子逻辑意义下非确定型Muller自动机和确定型Muller自动机(简记为LVDMA)是相互等价的,同时详细研究了(?)-值ω-正则语言的代数刻画和层次刻画；其次,讨论了LVMA识别的语言对于ω-正则运算的封闭性；再次,证明了量子逻辑意义下Muller自动机和Buchi自动机是等价的,得到了推广的McNaughton定理.(4)基于量子逻辑的Muller自动机的逻辑刻画.首先,通过引入单体二阶量子逻辑的概念,给出量子Muller自动机识别语言的单体二阶逻辑描述,深化和推广了量子逻辑意义下的ω-Buchi基本定理；其次,通过引入(?)-值星自由ω-正则语言与(?)-值非周期ω-正则语言,给出了相应语言的代数刻画,完全刻画了可以用一阶量子逻辑定义的量子语言,得到量子逻辑意义下的分类定理.
