Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems In answer set logic progremming. Solving these problems using Gelfond and Llfschltz＇s original defin...Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems In answer set logic progremming. Solving these problems using Gelfond and Llfschltz＇s original definition of answer sets Is not an easy task. Alternative charaoterlzatlons of answer sets for nested logic programs by Erdem and Llfschltz, Lee and Llfschltz, and You at el. are based on the completion semantics and various notions of tlghtnese. However, the notion of tightness Is a local notion In the sense that for different answer sets there are, In general, different level mappings capturing their tlghtnese. This makes It hard to be used In the deelgn of algorithms for computing answer sets. This paper proposes a charecterization of answer sets based on sets of generetlng rules. From this charaoterlzation new algorithms are derived for computing answer sets and for performing some other reasoning teaks. As an application of the charecterlzatlon a sufficient and necessary condition for the equivalence between answer set sementics and completion semantics has been proven, and a basic theorem Is shown on computing answer sets for nested logic programs baaed on an extended notion of loop formulas. These results on tlghtnese and loop formulas are more general than that in You and Lin＇a work.展开更多
基于回答集语义的逻辑程序(Answer Set Programming,ASP)是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强ASP的表达能力,一些工作在ASP引入了数据库系统中的聚合函数约束,并提出了SPT,FLP等语义,抽...基于回答集语义的逻辑程序(Answer Set Programming,ASP)是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强ASP的表达能力,一些工作在ASP引入了数据库系统中的聚合函数约束,并提出了SPT,FLP等语义,抽象约束剥离聚合函数约束的具体形式成为研究ASP语义等性质的重要工具,并得到了抽象约束逻辑程序的各种回答集语义之间的关系和复杂性问题等的相关结果。对此,进一步研究了仅含凸抽象约束原子抽象约束逻辑的性质,证明了仅含凸抽象约束原子的正规逻辑程序判定是否存在FLP回答集是Σ_(2)^(p)完全的,其审慎推理和大胆推理分别是Π_(2)^(p)完全的和Σ_(2)^(p)完全的。这些复杂性结果进一步理清了各类逻辑程序间的表达能力关系,为设计有效的回答集求解器提供了新的思路,也为进一步探索ASP在解决用凸抽象约束表示的问题中的应用提供了理论基础。展开更多
作为一种广为接受的语义数据模型,E-R模型被广泛地应用于数据库设计阶段.但是E-R模型自身却存在某些缺陷,这些缺陷制约了对其进一步的应用.针对E-R模型的改进,目前主要存在基于图形表示和描述性逻辑表示两种途径.但是,前者仍然不具有自...作为一种广为接受的语义数据模型,E-R模型被广泛地应用于数据库设计阶段.但是E-R模型自身却存在某些缺陷,这些缺陷制约了对其进一步的应用.针对E-R模型的改进,目前主要存在基于图形表示和描述性逻辑表示两种途径.但是,前者仍然不具有自动推理能力,而后者却存在表示能力弱、与数据库兼容性不足等缺陷.为克服以上缺陷,提出一种利用回答集编程(answer set programming)表示E-R模型的新方法.首先,对应于数据库的E-R模式被区分为基本和扩展两种类型,并分别完成它们的语法与语义定义.其次,利用回答集编程完成以上两类模式的逻辑编程表示.最后,完成表示的正确性证明.提出的方法不仅为E-R模型提供了一种新的逻辑表示途径,而且相对原有的两种E-R模型改进途径具有明显的优势.更为重要的是该研究成果使得应用E-R模型实现异构数据库之间的语义协作成为可能.展开更多
The purpose of this paper is to present the syntax and semantics of probabilistic logic programming to al-low for the correct representation of incomplete information. General logic programming is extended by a subint...The purpose of this paper is to present the syntax and semantics of probabilistic logic programming to al-low for the correct representation of incomplete information. General logic programming is extended by a subintervalof [0,1] that describes the range for the conditional probability of the head of a clause given the range for the proba-bility of each atom of its body. We define the semantics (answer sets semantics) of such probabilistic logic program-ming and illustrative their applications. We also show some properties of answer sets semantics for the probabilisticlogic programs.展开更多
基金Supported partially by the National Natural Science Foundation of China (Grant No. 60573009)Stadholder Foundation of Guizhou Province (Grant No. 2005(212)
文摘Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems In answer set logic progremming. Solving these problems using Gelfond and Llfschltz＇s original definition of answer sets Is not an easy task. Alternative charaoterlzatlons of answer sets for nested logic programs by Erdem and Llfschltz, Lee and Llfschltz, and You at el. are based on the completion semantics and various notions of tlghtnese. However, the notion of tightness Is a local notion In the sense that for different answer sets there are, In general, different level mappings capturing their tlghtnese. This makes It hard to be used In the deelgn of algorithms for computing answer sets. This paper proposes a charecterization of answer sets based on sets of generetlng rules. From this charaoterlzation new algorithms are derived for computing answer sets and for performing some other reasoning teaks. As an application of the charecterlzatlon a sufficient and necessary condition for the equivalence between answer set sementics and completion semantics has been proven, and a basic theorem Is shown on computing answer sets for nested logic programs baaed on an extended notion of loop formulas. These results on tlghtnese and loop formulas are more general than that in You and Lin＇a work.
文摘基于回答集语义的逻辑程序(Answer Set Programming,ASP)是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强ASP的表达能力,一些工作在ASP引入了数据库系统中的聚合函数约束,并提出了SPT,FLP等语义,抽象约束剥离聚合函数约束的具体形式成为研究ASP语义等性质的重要工具,并得到了抽象约束逻辑程序的各种回答集语义之间的关系和复杂性问题等的相关结果。对此,进一步研究了仅含凸抽象约束原子抽象约束逻辑的性质,证明了仅含凸抽象约束原子的正规逻辑程序判定是否存在FLP回答集是Σ_(2)^(p)完全的,其审慎推理和大胆推理分别是Π_(2)^(p)完全的和Σ_(2)^(p)完全的。这些复杂性结果进一步理清了各类逻辑程序间的表达能力关系,为设计有效的回答集求解器提供了新的思路,也为进一步探索ASP在解决用凸抽象约束表示的问题中的应用提供了理论基础。
文摘作为一种广为接受的语义数据模型,E-R模型被广泛地应用于数据库设计阶段.但是E-R模型自身却存在某些缺陷,这些缺陷制约了对其进一步的应用.针对E-R模型的改进,目前主要存在基于图形表示和描述性逻辑表示两种途径.但是,前者仍然不具有自动推理能力,而后者却存在表示能力弱、与数据库兼容性不足等缺陷.为克服以上缺陷,提出一种利用回答集编程(answer set programming)表示E-R模型的新方法.首先,对应于数据库的E-R模式被区分为基本和扩展两种类型,并分别完成它们的语法与语义定义.其次,利用回答集编程完成以上两类模式的逻辑编程表示.最后,完成表示的正确性证明.提出的方法不仅为E-R模型提供了一种新的逻辑表示途径,而且相对原有的两种E-R模型改进途径具有明显的优势.更为重要的是该研究成果使得应用E-R模型实现异构数据库之间的语义协作成为可能.
文摘CSP(Communicating Sequential Processes)是构建并发系统和网络安全协议的经典方法。当前主流的CSP模型验证方法需将进程转化为迁移系统,转化过程比较复杂;性质采用迹进行规范,不利于活性的描述。提出了一种基于进程迹的CSP模型验证框架,其性质采用通用的规范方法LTL进行描述。利用ASP(Answer Set Programming)技术实现了一个CSP验证系统。实验表明,与类似系统相比,该系统的描述能力更强,验证结果的准确性更高,在性质不满足时还可提供反例。
文摘The purpose of this paper is to present the syntax and semantics of probabilistic logic programming to al-low for the correct representation of incomplete information. General logic programming is extended by a subintervalof [0,1] that describes the range for the conditional probability of the head of a clause given the range for the proba-bility of each atom of its body. We define the semantics (answer sets semantics) of such probabilistic logic program-ming and illustrative their applications. We also show some properties of answer sets semantics for the probabilisticlogic programs.
