几类基于量子逻辑的自动机的代数及逻辑刻画

发布时间：2023-02-20 22:14

　　量子计算的思想源于物理与计算之间的联系.由于可逆性是量子物理的一个重要特征,所以该问题可追溯到Bennett于1973年证明了任意的Turing机都能被可逆的Turing机有效地模拟Benioff于1980年构造了一类基于量子力学原理的Turing计算模型,并证明它能模拟经典的可逆Turing机.其后不久,Feynman提出了一个本质的猜想：经典Turing机模拟一些量子现象的计算速度很可能呈指数下降Deutsch于1985年重新考察Church-Turing原理,并将Feynman的思想形式化,从而定义了量子Turing机.特别是Shor于1994年发现了在量子计算机上进行大数分解的多项式时间算法,Grover于1996年发现了平方根时间的量子搜索算法之后,量子计算日益受到人们的关注和重视. 量子计算模型的研究是量子计算中的一个重要的研究问题,而量子有穷自动机可看作一类具有有限内存的量子计算机模型,作为量子计算理论中最简单的数学模型.最近由应明生等建立的基于量子逻辑的有穷自动机理论是量子计算模型方面的一个重要研究方向.目前已经得到了很多与经典逻辑意义下不同的结果,并试图揭示量子计算的...

【文章页数】：124 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
前言
第1章 预备知识
    1.1 量子逻辑中的基本概念
    1.2 经典自动机理论中的相关知识
    1.3 L-值有穷自动机理论中的相关概念及结论
第2章 基于量子逻辑的下推自动机的代数刻画
    2.1 基于量子逻辑的下推自动机定义及其性质
    2.2 基于量子逻辑的上下文无关语言的代数刻画
    2.3 量子上下文无关文法及其范式文法
    2.4 LVPDA与LVCFG的等价性
    2.5 量子上下文无关语言对于正则运算的封闭性
    2.6 基于量子逻辑的上下文无关语言的泵引理
第3章 基于量子逻辑的Büchi自动机的代数刻画
    3.1 基于量子逻辑的Büchi自动机的定义及其性质
    3.2 基于量子逻辑的Büchi自动机的代数刻画
    3.3 几类基于量子逻辑的Büchi自动机间的关系
    3.4 基于量子逻辑的确定型Büchi自动机的代数刻画
    3.5 基于量子逻辑的Büchi自动机的等价刻画
第4章 基于量子逻辑的Müller自动机的代数刻画
    4.1 基于量子逻辑的Müller自动机的定义及其性质
    4.2 基于量子逻辑的Müller自动机的代数刻画
    4.3 L-值ω-正则语言关于正则运算的封闭性
    4.4 LVBA与LVMA的等价性
第5章 基于量子逻辑的Müller自动机的逻辑刻画
    5.1 单体二阶量子逻辑以及它可定义的语言
    5.2 基于量子逻辑的Müller自动机的单体二阶量子逻辑描述
    5.3 一阶量子逻辑以及它可定义的语言
    5.4 基于量子逻辑的Müller自动机的一阶量子逻辑描述
总结
参考文献
致谢
攻读博士学位期间的研究成果



本文编号：3747412