描述逻辑μALCIO的语义及推理

循环术语集是描述逻辑长期以来的研究难点,它的最基本的问题即语义及推理问题没有得到合理的解决.分析了描述逻辑循环术语集的研究现状和存在的问题,基于混合μ-演算将不动点构造算子引入到含有枚举构造算子的描述逻辑ALCIO中,提出了一种允许包含循环术语集的描述逻辑μALCIO.给出了μALCIO的语法和语义,证明了μALCIO的可满足性推理等价于混合μ-演算的可满足性推理,并利用树自动机理论给出了μALCIO的可满足性推理算法以及给出了推理算法正确性证明和复杂性定理.     

描述逻辑εLN 循环术语集的不动点语义及推理

循环术语集是描述逻辑长期以来的研究难点,其最基本的问题即语义及推理问题没有得到合理的解决.分析了描述逻辑循环术语集的研究现状和存在的问题,将Baader 的工作扩展到新的方向.针对更大的描述逻辑系统研究了循环术语集的语义及推理机制,即在描述逻辑εL 的基础上添加数量约束构造算子,提出了描述逻辑εLN,给出了εLN 的语义(包括不动点语义和描述语义).针对εLN 的需要,重新定义了描述图(包括语法描述图和语义描述图).使用描述图之间的模拟关系给出了不动点语义下εLN 循环术语集的可满足性和包含关系推理算法,并证明了推理算法是多项式时间复杂的.     

描述逻辑FL-循环术语集的语义及推理

循环术语集是描述逻辑长期以来的研究难点,它的最基本的问题即语义及推理问题没有得到合理的解决.文中分析了描述逻辑循环术语集的研究现状和存在的问题,在Baader的基础上进一步研究了描述逻辑FL~-循环术语集的语义及推理问题.给出了FL~-循环术语集的语法、语义和不动点模型的构造方法.针对FL~-循环术语集的需要,提出了一种新的有限自动机,使用有限自动机给出了不动点语义和描述语义下FL~-循环术语集的可满足性和包含推理算法,证明了推理算法的正确性,并给出了推理算法的复杂性定理.     

描述逻辑εL循环术语集的混合推理

循环术语集是描述逻辑长期以来的研究难点,它最基本的问题即语义及推理问题没有得到合理的解决.分析了描述逻辑循环术语集的研究现状和存在的问题,在Baader和Brandt的基础上进一步研究了描述逻辑εL循环术语集的混合推理问题.给出了εL的混合循环知识库的语法和语义(包括不动点语义和描述语义).针对εL循环术语集混合推理的需要.提出了TBox-完全的概念,并重新定义了描述图(包括语法描述图和语义描述图).使用描述图之间的模拟关系和TBox-完全概念给出了最大不动点语义和描述语义下εL混合循环知识库的实例检测推理算法,证明了推理算法的正确性,并给出了推理算法的复杂性定理.     

带RVM的描述逻辑εL混合循环术语集的语义及推理

分析描述逻辑循环术语集的研究现状和存在的问题,在F.Baader和S.Brandt的基础上进一步研究带RVM的描述逻辑εL混合循环术语集的语义及推理问题.给出带RVM的εL混合循环术语集的语法和语义.针对带RVM的εL混合循环术语集包含推理的需要,提出TBox-完全的概念,并重新定义描述图,使用描述图之间的模拟关系和TBox-完全给出最大不动点语义和描述语义下带RVM的εL混合循环术语集的概念包含推理算法,证明推理算法的正确性,并证明推理算法是多项式时间复杂的.     

描述逻辑εL混合循环术语集的LCS和MSC推理

分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为εL混合循环术语集的LCS和MSC推理提供了理论基础.     

描述逻辑εL混合循环术语集的LCS和MSC推理

分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为(L混合循环术语集的LCS和MSC推理提供了理论基础.     

描述逻辑FL0循环术语集的可满足性

循环术语集是描述逻辑长期以来的研究难点,它的最基本的问题即语义及推理问题没有得到合理的解决。分析了描述逻辑循环术语集的研究现状和存在的问题,基于图的互模拟的方法,给出了描述逻辑FL0循环术语集的可满足性条件。结果证明循环术语集的可满足性的推理是多项式复杂的。     

基于OBDD的描述逻辑εL循环术语集推理

循环术语集推理是描述逻辑研究中面临的难点问题,尚未得到很好的解决.有序二叉决策图（ordered binary decision diagram,简称OBDD）是一种对布尔函数进行紧凑表示和高效操作的数据结构,适用于表示和处理大规模问题.将OBDD应用于描述逻辑循环术语集的推理.首先,针对描述逻辑εL中的循环术语集,给出了描述图上关于最大模拟关系的重要性质,并借助集合表示和集合运算对该性质进行了表述和证明.在此基础上,应用布尔函数对描述图进行编码,给出了基于OBDD求解最大模拟关系的方法,进而给出了最大不动点语义下基于OBDD对概念包含关系进行判定的算法;接下来,基于OBDD给出了求解描述图中可以到达循环路径的所有结点的方法,进而给出了最小不动点语义下基于OBDD对概念包含关系进行判定的算法;最后,对算法的正确性、复杂度等进行了分析和证明,并对算法进行了编程实现,给出了关于计算性能的实验结果.该工作为循环术语集的推理提供了一条有效途径,也为OBDD在逻辑推理中的应用提供了新的案例.     

基于Game理论的μ-演算公理化

随着软硬件系统复杂性的不断提高,各种验证技术被越来越广泛的使用.模型检验技术是一种保证软硬件设计、实现正确性的有效技术.在针对软硬件的模型验证技术中,一般采用时序逻辑作为规约语言.模态μ-演算是模态和时序逻辑中应用较为广泛的一种,它具有语法成分简洁、表达能力强等特点.扩展了Lange和Stirling基于Focus Game的LTL和CTL的公理化方法.提出了一种基于Game理论的μ-演算公式的可满足性的测试方法,该种方法能够将模态μ-演算公式的可满足性问题转化为Focus Game的求解问题.进一步,基于这套Game规则,给出了一个新的关于μ-演算可靠完备的推理系统.同已有的μ-演算公理系统相比,该推理系统相对直观、简洁.     

基于最大不动点模型的描述逻辑系统FLε的有穷基

研究了描述逻辑的有穷基问题,分析了有穷基在描述逻辑中的重要意义及其研究现状,并研究了形式概念分析中的属性蕴舍和Duguenne-Guigues基问题.利用形式概念分析中Duguenne-Guigues基存在的证明结果,在F.Baader工作基础上设置了描述逻辑的描述背景,重新定义了描述背景下的属性蕴含,证明了带循环术语的描述逻辑系统FLε存在最大不动点语义(greatest fixed-points,gfp)模型,给出了带循环术语的描述逻辑系统FLε在最大不动点模型下的有穷基的存在性定理,并证明有穷基的可靠性和完备性.描述逻辑有穷基可以帮助知识工程师构建一个更适用于推理的描述逻辑知识库.     

一类扩展的动态描述逻辑

作为描述逻辑的扩展,动态描述逻辑为语义Web服务的建模和推理提供了一种有效途径.在将语义Web服务建模为动作之后,动态描述逻辑从动作执行结果的角度提供了丰富的推理机制,但对于动作的执行过程却不能加以处理.借鉴Pratt关于命题动态逻辑的相关研究,一方面,对动态描述逻辑中动作的语义重新进行定义,将每个动作解释为由关于可能世界的序列组成的集合;另一方面,在动态描述逻辑中引入动作过程断言,用来对动作的执行过程加以刻画.在此基础上提出一类扩展的动态描述逻辑EDDL(X),其中的X表示从ALC(attributive language with complements)到SHOIN(D)等具有不同描述能力的描述逻辑.以X为描述逻辑ALCQO(attributive language with complements,qualified number restrictions and nominals)的情况为例,给出了EDDL(ALCQO)的表判定算法,并证明了算法的可终止性、可靠性和完备性.EDDL(X)可以从动作执行过程和动作执行结果两个方面对动作进行全面的刻画和推理,为语义Web服务的建模和推理提供了进一步的逻辑支持.     

分支时态描述逻辑ALC-CTL及其可满足性判定

时态描述逻辑是将描述逻辑与时态逻辑相结合后得到的逻辑系统,具有较强的描述能力;但是大部分的时态描述逻辑都是将时态算子同时引入到概念和公式中,使得公式可满足性问题的计算复杂度过高。将描述逻辑ALC与分支时态逻辑CTL相结合,提出新的分支时态描述逻辑ALC-CTL。该逻辑没有将时态算子用于概念的构造过程,而是将时态算子引入到公式的构造中;从分支时态逻辑的角度看,相当于将CTL中的原子命题提升为描述逻辑中的个体断言。最终得到的逻辑系统不仅具有较强的刻画能力,还使得公式可满足性问题的复杂度保持在EXPTIME-完全这个级别。通过将CTL的Tableau判定算法与描述逻辑ALC的推理机制有机结合,给出了ALC-CTL的Tableau判定算法并证明了算法的可终止性、可靠性和完备性。     

命题μ-演算局部模型检测高效算法设计

命题μ-演算局部模型检测算法中,目前最好的算法的时间复杂度与不动点算子交替嵌套深度d呈指数关系。针对命题μ-演算局部模型检测算法的计算过程进行分析,得到迭代计算的中间迭代值间满足的一组偏序关系,然后利用该偏序关系设计了一个局部模型检测算法,算法时间复杂度的指数部分为d/2,大大提高了算法的计算效率。     

μ-演算嵌套不动点表达式分块计算算法

利用叠代计算μ-演算公式时的单调特性,提出了一个分块计算嵌套μ-演算公式的全局算法,算法时间复杂度为 ,空间复杂度为 。由于算法的空间复杂度低,使得不动点算子嵌套深度很大的μ-演算公式的求解成为可能,这在模型检测方面有着非常重要的意义。     

面向语义Web语义表示的模糊描述逻辑

分析了语义Web语义表示理论的研究现状及存在的问题,提出了一种新的面向语义Web语义表示的模糊描述逻辑FSHOIQ(fuzzy SHOIQ).给出了FSHOIQ的语法和语义,提出了FSHOIQ的模糊Tableaux的概念,给出了一种基于模糊Tableaux的FSHOIQ的ABox约束下的可满足性推理算法,证明了可满足性推理算法的正确性.提出了FSHOIQ的TBox扩展和去除方法,并证明了FSHOIQ的TBox约束下的包含推理问题可以转化为ABox约束下的可满足性推理问题.FSHOIQ为语义Web表示和推理模糊知识提供了理论基础.     

一种带物元的动态描述逻辑

针对动态描述逻辑框架中只有概念和关系,在表述由于动作作用而引起的概念或个体的属性及值的变化和变化后的影响方面能力不强的问题,本文引入物元的概念及其发散规则扩充动态描述逻辑,给出了一种新的带物元的动态描述逻辑(MDDL).文中按照传统描述逻辑的语义解释方法给出了物元的语义解释,然后引入物元及物元"一物多征"的发散推理规则,扩充动态描述逻辑的Tableau算法,生成二种新的Tableau-M算法.最后根据该算法深入研究了MDDL的基本推理问题,即实例断言集的一致性检测问题和概念与物元的可满足性检测问题.     

命题μ-演算全局模型检测的高效算法设计

在Long, Browne, Jha 和 Marrero等人工作的基础上,详细分析了用Tarski不动点定理计算不动点交替嵌套深度为4的命题μ-演算公式的计算过程,找到了计算中间结果间具有的两组偏序关系,利用这两组偏序关系设计了一个高效的命题μ-演算全局模型检测算法,该算法与Long等人提出的算法有相似的时间复杂度(O((2n+1)- d/2 - +1)相对于O(n- d/2 - +1)),但空间复杂度有很大的改进(O(dn)相对于O(n- d/2 - +1)),其中n是变迁系统的状态规模,d是命题μ-演算公式中不动点算子的嵌套深度.算法性能的改进对于命题μ-演算模型检测技术的理论研究与实际推广应用都意义重大.     

gfp-模型的描述逻辑FLε的循环术语集推理

描述逻辑（DL）一族知识表示形式系统,是人工智能领域的一个热门研究方向。循环定义下描述逻辑系统的表达在许多情况下更符合人们的直觉,而且具有更强的表达力,是非循环定义下的描述逻辑系统不可代替的。首先给出描述逻辑系统FLε有最大不动点模型的证明,然后初步探讨基于最大不动点语义下描述逻辑系统FLε循环定义的包含关系推理算法,并给出算法的可靠性和完全性证明。     

直觉线性μ-演算中的合成推理

讨论了以基于前缀封闭集合的Heyting代数的直觉解释的线性μ-演算(IμTL)作为描述“假设-保证”的逻辑基础的问题,提出了一个基于IμTL的“假设-保证”规则.该规则比往常应用线性时序逻辑(LTL)作为规范语言的那些规则具有更好的表达能力,扩展了对形如“always ?”等安全性质的“假设-保证”的范围,具备更一般的“假设-保证”推理能力及对循环推理的支持.