论文摘要
量子计算的思想源于物理与计算之间的联系.由于可逆性是量子物理的一个重要特征,所以该问题可追溯到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基本定理；其次,通过引入（?）-值星自由ω-正则语言与（?）-值非周期ω-正则语言,给出了相应语言的代数刻画,完全刻画了可以用一阶量子逻辑定义的量子语言,得到量子逻辑意义下的分类定理.
论文目录
相关论文文献
- [1].欧洲自动机艺术的兴盛与衰败[J]. 新美术 2019(12)
- [2].某导气式火炮自动机身管磨损后的性能分析[J]. 兵器装备工程学报 2020(08)
- [3].某高速自动机冷却系统分析[J]. 机械制造与自动化 2017(02)
- [4].量子自动机的交换性[J]. 计算机工程与应用 2016(20)
- [5].自动机终结字查找算法的设计与实现[J]. 计算机科学 2020(S2)
- [6].自动机凸轮曲线动力学性能改进[J]. 兵器装备工程学报 2020(09)
- [7].基于虚拟样机技术对手枪新型自动机的研究[J]. 河北农机 2016(03)
- [8].树自动机超最小化[J]. 南昌航空大学学报(自然科学版) 2015(02)
- [9].确定权重有限自动机的同余及极小自动机[J]. 纯粹数学与应用数学 2015(05)
- [10].可逆加权树自动机[J]. 模糊系统与数学 2015(04)
- [11].高射频武器自动机测试实验研究及分析[J]. 中北大学学报(自然科学版) 2012(06)
- [12].高射速自动机后坐力控制[J]. 火炮发射与控制学报 2011(02)
- [13].基于模糊物元的舰炮自动机性能评价[J]. 舰船电子工程 2009(07)
- [14].一类同步自动机及损耗函数分析[J]. 计算机科学 2019(S2)
- [15].一种自治操作条件反射自动机[J]. 控制理论与应用 2012(11)
- [16].基于分形理论的高速自动机故障诊断[J]. 机械工程与自动化 2014(02)
- [17].学习加权自动机[J]. 计算机工程与设计 2014(06)
- [18].火炮自动机故障诊断研究综述[J]. 机械管理开发 2013(01)
- [19].外能源转管自动机机电耦合动力学键合图建模及应用[J]. 火炮发射与控制学报 2013(01)
- [20].基于混成自动机的车联网服务建模方法[J]. 南通大学学报(自然科学版) 2013(02)
- [21].改进的八近邻区域边界标定自动机[J]. 华东师范大学学报(自然科学版) 2009(01)
- [22].模糊自动机的强连通性及群自动机[J]. 纯粹数学与应用数学 2009(03)
- [23].单模式串匹配自动机的设计与实现[J]. 南通职业大学学报 2008(01)
- [24].基于分时段规范变量残差分析的高速自动机动态特性监测[J]. 振动与冲击 2019(20)
- [25].有关本原自动机的研究[J]. 空军工程大学学报(自然科学版) 2016(02)
- [26].使用事件自动机规约的C语言有界模型检测[J]. 软件学报 2014(11)
- [27].某转管自动机停射故障分析[J]. 火炮发射与控制学报 2014(04)
- [28].基于场景自动机的网构软件演化[J]. 计算机科学 2014(11)
- [29].多模式匹配自动机的构造与极小化[J]. 铜仁学院学报 2011(03)
- [30].状态转移函数对加权自动机计算能力的影响[J]. 模糊系统与数学 2020(03)
标签：量子计算论文; 量子逻辑论文; 正交模格论文; 量子下推自动机论文; 量子上下文无关语言论文; 量子上下文无关文法论文; 量子自动机论文; 量子正则语言论文; 单体二阶量子逻辑论文; 量子正则表达式论文;