导读:本文包含了可判定性论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:逻辑,自动机,语义,正则,命题,模型,模糊。
可判定性论文文献综述
张炎[1]（2017）在《Z-型Rabin树理论的可判定性》一文中研究指出Z-型Rabin树是Rabin树的一种变体,它们与Rabin树的主要区别在于不要求树根的存在,而只限制其中的极大枝与整数上的序同构。本文通过归约的方法证明,Z-型Rabin树的一目二阶理论是可判定的。(本文来源于《逻辑学研究》期刊2017年02期）
李兴香,栾峻峰[2]（2015）在《可计算性逻辑中CoL2系统的可判定性分析》一文中研究指出可计算性(Computability)即算法有解性,是数学和计算机科学领域中重要的概念之一。可计算性逻辑(Computability Logic,CoL)是关于可计算性的形式理论,是一种交互的资源逻辑。其中,CoL2系统采用博弈的语义,是对经典命题逻辑的扩展,在经典命题逻辑的基础上添加了选择运算和一般原子,比经典命题逻辑更富有表达力,具有更广阔的应用前景,并且有较高的证明效率。分析了CoL2系统的可判定性,即通过提出一个算法来判断任意一个CoL2公式是否是可证明的,并且证明了该算法是多项式空间内运行的。(本文来源于《计算机科学》期刊2015年07期）
薛倩倩[3]（2014）在《格值模糊正则语言的分级与可判定性》一文中研究指出作为自动机识别的语言,正则语言已应用于计算机程序语言编译的词法分析、开关电路设计等方面,并且在形式语言中有着重要的性质.从20世纪60年代以来,模糊自动机及其接受的语言得到了深入的研究.通常的模糊自动机,即取值在[0,1]单位区间的自动机,只能从层次结构的观点识别所接受的语言,为了克服这个问题,李永明将值域扩展到一般的格结构上,提出了格值自动机,因此有必要研究格值模糊正则语言的性质.对于取值在[0,1]区间上的模糊正则语言,确定的与非确定的是等价的,而对于格值正则语言,这个结论未必成立.Klimann [24]等人已经研究了不同种类加权自动机接受语言在tropical半环下的分级关系,在此我们讨论不同种格值模糊正则语言的分级及可判定性等问题.本文的主要工作如下：1.首先对格值模糊自动机分类,将其分为确定的、序列的、无歧义的、有限歧义的以及无限歧义的.其次,探讨了局部有限格序幺半群L对格值模糊正则语言等价性的影响,证明了L非局部有限时正则语言间存在真包含关系,并给出了几类格值模糊正则语言等价的充分条件.特别地,讨论了当L中的运算取阿基米德t-模时,格值模糊正则语言的性质.2.研究了格值模糊正则语言的可判定性问题.首先,给出了格值模糊正则语言相等(Eq)、不等(Ineq)、局部不等(LocalIneq)和局部相等(LocalEq)这几个待研究的可判定性问题.其次,证明了格值模糊正则语言的可判定性问题与格序幺半群的结构有关,即：若L局部有限,上述几类问题是可判定的,若L非局部有限,上述问题是不可判定的.最后探讨了有穷自动机的有穷分解,证明了任意的Boolen型矩阵都可以分解为余共合矩阵与共合矩阵的复合,并根据这一性质对共轭的自动机进行分解.(本文来源于《陕西师范大学》期刊2014-05-01）
程昆,高佳乐[4]（2013）在《一种命题逻辑的可判定性算法》一文中研究指出针对命题逻辑的可判定性中真值表法复杂度高的问题,提出了一种基于命题逻辑联结符号完备性和与或树规则的命题逻辑的可判定性算法。算法首先利用常见的等价公式和与或树规则对命题逻辑的公式进行分解,然后参照分解后的树形结构将公式转换成范式形式,最后对照所得的判别式对命题逻辑公式进行判定。理论证明这种算法相比于具有指数级复杂度的真值表法效率高得多。(本文来源于《微型机与应用》期刊2013年24期）
张艳[5]（2013）在《可计算性逻辑中CL2系统的可判定性及空间复杂性分析》一文中研究指出可计算性(computability),即算法有解性,是数学和计算机科学领域中最重要的概念之一。可计算性逻辑(Computability Logic,简写为CoL)是研究可计算性的形式理论,它将问题看作是计算机(或者以计算机为表现形式的人)与外部环境之间的博弈,问题的可计算性是指存在一台计算机能赢得这个博弈。传统逻辑主要回答什么是永真的、有效的,而可计算性逻辑试图系统的回答什么是可计算的及应如何计算。CoL中的公式代表交互计算问题,逻辑运算代表在可计算问题上的交互操作,一个公式是有效的是指存在解决相应问题的方法(或者等价的,存在赢得博弈的策略)。本文首先介绍了可计算性逻辑的博弈语义及其形式化的定义,给出了CoL中的(?)、(?)、(?)、(?)、(?)和→等逻辑运算表达的意义及其形式化定义。博弈分为静态博弈和动态博弈,静态博弈是与博弈双方反应速度无关的博弈,其最终结果只取决于博弈的策略。CoL所研究的博弈问题都是静态博弈。HPM (hard-play machine)是交互计算机模型的最基本模型,它是在一种图灵机模型基础上修改得到的计算机模型。另一种计算模型是EPM (easy-play machine),它与HPM在设计上唯一的区别在于只有当计算机明确的允许环境行动时环境才可以做一个行动。对于静态博弈问题来说,这两种模型是等价的。在实际解决问题的过程中,我们更倾向于采用EPM模型。CL2逻辑采用博弈的语义,是对经典命题逻辑的保守扩展,比经典命题逻辑更富有表达力和更广阔的应用前景,并且有较高的证明效率。与经典命题逻辑相比,CL2逻辑包含两类原子：简单原子和一般原子。简单原子代表简单计算问题,它与经典命题逻辑中的谓词相对应；一般原子代表一般的交互计算问题,在意义上有别于谓词。经典逻辑的真的概念就相当于CL2中的可计算性的概念。CL2逻辑系统已经被证明了是完备的、可靠的逻辑系统。本文的创新点在于：(1).分析CL2系统的可判定性。提出判断CL2公式可证明性的算法,并且证明该算法是多项式空间内运行的。(2).分析CL2系统的空间复杂性。通过将PSPACE完全问题——量词化布尔公式(Truth of Quantified Boolean Formula,简写为TQBF)问题归约到CL2公式的可证明性问题,我们证明了CL2系统是PSPACE完全的。这样结果表明了CL2公式的可证明性问题是比NP-hard更难的一类问题。(本文来源于《山东大学》期刊2013-04-05）
章衡[6]（2011）在《非单调逻辑的可判定性与可译性》一文中研究指出如何使计算机能运用常识进行推理和问题求解是人工智能领域最困难的问题之一,非单调逻辑是以此为目标的知识表示语言中最重要的一类。本论文致力于几种一阶非单调逻辑的可判定性和可译性研究。所获得的主要结果如下：第一,比较全面地研究了一阶限定理论及稳定语义下的一阶语言中各种前缀-符号集类在模型存在性意义下的可判定性。其中前缀-符号集类是通过对量词前缀、谓词、函词及等词作限制而定义的一种分类方式。具体地,本文找到了一阶限定理论中六个可判定的极大前缀-符号集类,找到了在稳定语义下可判定的一个极大前缀-符号集类,并找出了一大批不可判定类,从而得到了这两种语言在前述分类下关于可判定性与不可判定性比较精确的一个分界线。第二,系统研究了一阶限定理论、稳定语义下的一阶语言和各种析取逻辑程序之间的可译性关系。其中,根据翻译中是否允许辅助谓词和函词,以及问题的论域是有穷或不作限制,可译性关系被细分为四种。本文证明了上述语言在这四种关系下的绝大多数可译性或不可译性结果。这些结果对于理解存在量词、辅助谓词和函词、否定词的性质具有重要意义。特别地,由这些结果可以得到关于编码自然性方面的一些有趣结论,譬如可以推断存在一大类由逻辑程序可以表达的问题却不能使用一般论域中的编码技术在逻辑程序中进行编码。第叁,研究了上述几种语言的模型论性质。特别地,证明了析取逻辑程序在稳定语义下满足下降Lowenheim-Skolem性质,即析取逻辑程序有稳定模型当且仅当它有可数稳定模型；证明了一阶稳定语义可刻画实数系统。因此,除非引入存在量词或其他机制,否则析取逻辑程序不能描述实数论域上的知识。第四,在可译性研究的基础上,对从稳定语义下一阶语言到逻辑程序的翻译进行了优化,设计并实现了稳定语义下一阶理论的一个原型求解器；通过在两个基准问题上的若干实验,验证了这一原型求解器的效率。此外,本文也给出了从一阶限定理论到稳定语义下一阶语言的一个非常简单的翻译,这将为设计高效的一阶限定理论求解器提供一条可行的技术途径。(本文来源于《清华大学》期刊2011-10-01）
符鸿飞[7]（2010）在《进程验证问题的可判定性和复杂性》一文中研究指出本文涉及的研究领域是无穷状态系统的验证。无穷状态系统上的验证问题主要包括两个方面:一个方面是等价验证,另一个方面是模型检测。等价验证主要是给定两个无穷状态系统,判定这两个系统是否等价。模型检测则是给定一个无穷状态系统和一个逻辑公式,判定这个系统是否满足这个公式。在实际应用中,我们可以通过等价验证来判定两个系统是否在某个意义下相等;我们也可以通过模型检测来判定一个系统是否满足某个给定的性质。对这个领域的研究使得我们能从一定程度上对安全协议,程序,工业设计等潜在的无穷状态系统进行验证。在等价验证中,通常选择互模拟作为等价关系。其基本思想为,如果一个状态与另一个状态互模拟,则任一个状态的迁移都要能被另一个状态模拟,模拟完以后的两个状态还要互模拟。目前最具代表性的互模拟是由Park提出的强互模拟和由Milner提出的弱互模拟。本文研究的是branching bisimulation的判定,它由van Glabbeek提出。Branching bisimulation通常作为弱互模拟的备选。相较弱互模拟,它保持了系统静态迁移中的中间状态,从而比弱互模拟更细;它还拥有弱互模拟没有的优点,如代数刻画和模态逻辑刻画。在本文中,我们研究BPA与有限状态系统,以及normed BPP与有限状态系统之间branching bisimulation的判定。其中BPA是一个基本的顺序计算模型,BPP是一个基本的并发计算模型,而normed BPP是BPP的一个子类。对于BPA,我们给出一个多项式算法,它改进了之前由Kucˇera et al给出的算法;而对于normedBPP,我们证明它与有限状态系统间的branching bisimilarity是多项式可判定的。模型检测的一个要键是用来描述系统行为的逻辑,其通常是时态逻辑。在这里,我们研究EGF逻辑。EGF逻辑由To et al形式地提出,它由EF逻辑和EGF算子组成。EGF算子与regular model checking有很大的联系。在regular model check-ing中,EGF算子被称为recurrence或recurrent reachability。同时,EGF算子也表示某种fairness的性质,表示“某种好的性质会不断发生”。在本文中,我们研究下推系统和BPP上EGF逻辑的模型检测问题。我们证明这两个模型检测问题都是PSPACE完全的,并在固定公式情形下给出一些结果。(本文来源于《上海交通大学》期刊2010-01-01）
张伟[8]（2009）在《关于开放逻辑的可判定性》一文中研究指出开放逻辑是用于刻画知识的增长,更新及假说进化的一个引人注目的形式逻辑理论。文中描述了在开放逻辑中什么是典型的证明论问题,并形式地定义了开放证明的概念。关于开放逻辑中的判定性问题,得到的结论是:(1)一致的开放逻辑系统的开放证明问题是半可判定的(文中给出了一个判定算法);(2)不一致的开放逻辑系统的开放证明问题不是半可判定的。(本文来源于《中国科学(F辑:信息科学)》期刊2009年07期）
刘万伟,王戟,陈火旺[9]（2008）在《线性μ-演算交换深度的可判定性及其复杂度》一文中研究指出模态μ-演算被十分广泛地应用在模型验证技术中.影响模态μ-演算检验复杂度的主要瓶颈来源于规约公式的交换深度.讨论了线性μ-演算交换深度的可判定性以及求解复杂度.证明了线性μ-演算交换深度是可判定的;同时证明了对于长为l的公式判定及求解的复杂度为2O(llogl).(本文来源于《计算机研究与发展》期刊2008年S1期）
田聪[10]（2007）在《命题投影时序逻辑的可判定性》一文中研究指出本文主要研究命题投影时序逻辑(Propositional Projection Temporal Logic, PPTL)的可判定性问题。文中简要地介绍了PPTL公式的语法、语义及逻辑规则,定义了PPTL公式的正则形(Normal Form)和完备正则形(Complete Normal Form)。在正则形的基础上,给出PPTL公式正则图(Normal Form Graph)的归纳定义和可执行的算法,证明了该算法的可终止性。基于正则图,PPTL公式在无穷区间范围的可判定性问题得到解决。另外,本文也给出了命题区间时序逻辑(Propositional Interval Temporal Logic, PITL)在无穷区间范围的判定过程。逻辑的可判定性是基于该逻辑的模型检测方法的基础,本文给出的判定算法证实了基于PPTL的模型检测方法的可行性。文章最后回顾了模型检测工具的发展现状,分析了以PPTL为逻辑基础的模型检测工具的优越性,阐明了开发基于PPTL的模型检测器的必要性,且给出了基于PPTL的模型检测器的概要设计。(本文来源于《西安电子科技大学》期刊2007-01-01）
可判定性论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
可计算性(Computability)即算法有解性,是数学和计算机科学领域中重要的概念之一。可计算性逻辑(Computability Logic,CoL)是关于可计算性的形式理论,是一种交互的资源逻辑。其中,CoL2系统采用博弈的语义,是对经典命题逻辑的扩展,在经典命题逻辑的基础上添加了选择运算和一般原子,比经典命题逻辑更富有表达力,具有更广阔的应用前景,并且有较高的证明效率。分析了CoL2系统的可判定性,即通过提出一个算法来判断任意一个CoL2公式是否是可证明的,并且证明了该算法是多项式空间内运行的。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
可判定性论文参考文献
[1].张炎.Z-型Rabin树理论的可判定性[J].逻辑学研究.2017
[2].李兴香,栾峻峰.可计算性逻辑中CoL2系统的可判定性分析[J].计算机科学.2015
[3].薛倩倩.格值模糊正则语言的分级与可判定性[D].陕西师范大学.2014
[4].程昆,高佳乐.一种命题逻辑的可判定性算法[J].微型机与应用.2013
[5].张艳.可计算性逻辑中CL2系统的可判定性及空间复杂性分析[D].山东大学.2013
[6].章衡.非单调逻辑的可判定性与可译性[D].清华大学.2011
[7].符鸿飞.进程验证问题的可判定性和复杂性[D].上海交通大学.2010
[8].张伟.关于开放逻辑的可判定性[J].中国科学(F辑:信息科学).2009
[9].刘万伟,王戟,陈火旺.线性μ-演算交换深度的可判定性及其复杂度[J].计算机研究与发展.2008
[10].田聪.命题投影时序逻辑的可判定性[D].西安电子科技大学.2007
论文知识图
