描述逻辑εLU概念及术语公理集的表达能力刻画

表达能力和推理复杂性是一个逻辑的两个重要特征,也是一对相互制约的关系.解释之间的互模拟关系是从语义的角度刻画逻辑表达能力的一个有效途径,其代表性的结果是命题模态逻辑表达能力的刻画定理——vanBenthem 刻画定理.给出了描述逻辑εLU（含构造子：原子概念、顶概念、概念交、概念并、完全存在约束）的模拟关系,建立了εLU中概念和术语公理集的表达能力刻画定理,即一阶逻辑公式与ELU中概念和术语公理集等价的充分必要条件.上述结果为寻求表达能力与推理复杂性之间的最佳平衡提供了有效的支持.     

一般术语公理下的模糊描述逻辑FALCN推理

分析了一般术语公理下推理的主要难点:在模糊解释中的隶属度不是离散值,而是区间[0,1]上的连续值.为解决该难点,提出了模糊描述逻辑FALCN下的模糊解释离散化方法,从而使解释中的隶属度都属于一个特殊的有限离散集合.基于该离散化方法,给出一般术语公理下FALCN推理问题的离散Tableau推理技术,包括离散Tableau的定义以及离散Tableau的构造算法,并证明了算法的正确性、完备性和复杂度.     

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

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

描述逻辑εL循环术语集的保守扩充

在计算机科学中,本体是动态的实体。为了适应新领域的发展,需要对原始本体增加新的公理或者与另一个本体融合。在本体的开发过程中,用户根据不同的需求和应用领域选择合适的本体导入另一个本体,从而实现对已建本体的扩充。判定扩充后的本体是否是扩充前本体的保守扩充是非常重要的。如果扩充后的本体不是扩充前本体的保守扩充,那么用户使用扩充后的本体将产生不可预知的影响。Lutz 等研究了描述逻辑εL的保守扩充问题,并且论证了εL的保守扩充是指数时间完全的。在Lutz等人的研究基础上研究了描述逻辑循环术语集的保守扩充问题。首先,给出了循环术语集在最大不动点语义下的保守扩充的充分条件是两个TBox 具有相同的原始概念,并论证了该算法是多项式时间复杂的。其次,给出最大不动点模型来处理循环术语集的保守扩充,并论证了该算法是指数时间复杂的。     

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

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

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

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

描述逻辑系统vL循环术语集的可满足性及推理机制

文中分析了描述逻辑循环术语集的研究现状和存在的问题,将近年来Baader F和Nebel B等人的工作扩展到新的方向.首先定义了描述逻辑的子系统vL,重新定义描述图G_T和G_J,使用互模拟的方法,给出了描述逻辑系统vL循环TBox非平凡的模型存在的、基于描述图的一个语法条件.证明:vL的包含推理算法是多项式时间复杂的.     

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

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

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

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

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

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

描述数据库的双层描述逻辑

为了表示元组和属性值的逻辑区别,引入了一个双层描述逻辑,其中概念分为两类:元组概念和属性值概念。给出双层描述逻辑的语言、语法和语义;然后定义从数据库中的关系到双层描述逻辑的知识库以及双层描述逻辑的模型的转换;最后扩展双层描述逻辑,使得其中的角色分为3类:元组之间的角色、元组与属性值之间的角色以及属性值之间的角色。     

基于描述逻辑的模糊ER模型的表示与推理

重点分析了将ER模型分别转化为描述逻辑ALNUI知识库和DLR知识库的不同之处.在深入研究了描述逻辑DLR的基础之上,对DLR进行了模糊化扩展,提出了一种新的模糊描述逻辑FDLR(fuzzyDLR).定义了FDLR的语法结构、语义解释以及知识库的形式,研究了如何将模糊ER模型转化为FDLR的知识库.通过一个转化实例例证了FDLR能够很好地对模糊ER模型进行表示,并利用FDLR的推理机制研究了模糊ER模型的自动推理问题,同时给出了上述转化和推理问题的正确性证明.     

一种RBAC的描述逻辑表示方法

基于角色的访问控制(RBAC)通过角色来控制用户对资源的访问,极大地简化了安全管理。虽然对RBAC的研究比较成熟,但由于RBAC目前缺乏形式化的表示,使得RBAC中的一些概念和性质存在不同的理解。描述逻辑(DL)是一种基于对象的知识表示的形式化系统,它是一阶逻辑的一个可判定的子集,具有合适定义的语义,并且具有很强的表示能力。为了给出RBAC的形式化方法,以描述逻辑为工具,RBAC96模型为基础,提出了RBAC的描述逻辑DLRBAC。用描述逻辑的符号给出了RBAC中主要的元素和关系的形式化定义,并证明了这种描述逻辑表示对于RBAC模型的忠实性。所提出的RBAC形式化模型可以作为进一步研究RBAC的理论基础。     

描述逻辑程序系统的设计与实现

Eiter等人为语义网提出的回答集程序和描述逻辑相结合的描述逻辑程序,获得了本体上的非单调表达和推理能力。王以松等人证明了描述逻辑程序的完备化和环公式可以精确刻画描述逻辑程序的回答集。在此基础上,进一步证明了若完备化公式的模型不是回答集则一定存在终止环公式反例,它们是多项式时间可计算的。设计并实现了借助SAT求解器MiniSAT以及描述逻辑推理机RacerPro计算描述逻辑强回答集的原型DLP_SAT。实验结果表明,该原型能有效地计算一些熟知的描述逻辑程序的强回答集。     

描述逻辑FL0的包含推理及其保守扩充

本体作为知识库表示知识已经成为计算机理论与应用的研究热点.在描述逻辑中,将本体看作一个逻辑理论,一个本体被形式化为给定的描述逻辑系统的一个Tbox.本体是动态的实体,为了适应新领域的发展,需要对原始本体进行扩充.但是扩充后的本体与原始本体是否保持逻辑一致性是目前研究者们所关注的焦点.在Lutz等人研究的基础上探究FL0的保守扩充问题.首先构建了FL0的典范模型,将包含推理问题转换为典范模型的模拟问题;其次由典范模型之间的最大模拟是多项式时间复杂的,证明了FL0的包含推理是多项式时间复杂的;最后给出描述逻辑FL0的保守扩充及其判定算法,证明了FL0的保守扩充的判定算法是指数时间复杂的.     

时间区间时序逻辑的判定性与表达能力

模型检测技术在实时系统验证中被广泛使用。离散时间区间时序逻辑满足性是可判定的,因而也是可模型检测的。连续时间域时间区间时序逻辑是否可模型检测,则并不清楚。约束时间域到非负实数,证明了其可满足性是不可判定的,但存在该逻辑的可判定子集,并发现了这样的子集。由于模型检测问题可归约为时序逻辑满足性判定问题,因此结果表明,时间区间时序逻辑不可模型检测,但其可判定子集可模型检测。