Reasoning about evolving nonmonotonic knowledge bases
Reasoning about evolving nonmonotonic knowledge bases
复制标题
关于演化非单调知识库的推理
DOI：
10.1145/1055686.1055693
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
H. Tompits
中科院分区：
文献类型：
--
作者：
Thomas Eiter;Michael Fink;Giuliana Sabbatini;H. Tompits
最近，几种方法来更新知识库建模为扩展的逻辑程序已经推出，从基本的方法，将（序列）的规则集到一个逻辑程序，更精细的方法，使用更新策略，指定如何更新必须纳入。在这篇文章中，我们介绍了一个框架，推理不断发展的知识库，这是表示为扩展的逻辑程序和维护的更新政策。我们首先描述了一个正式的模型，捕捉各种更新方法，我们定义了一个逻辑语言表达不断变化的知识库的属性。然后，我们调查我们的框架，在那里我们专注于知识状态的属性相对于规范推理任务的一个给定的公式是否持有在一个给定的不断发展的知识库的语义和计算属性。特别是，我们提出了有限的特征的演变为某些类别的框架实例，可以利用获得可判定性的结果。更详细地说，我们描述了一些有意义的类不断发展的知识库的推理的复杂性，从多项式到双指数空间的复杂性。
Recently, several approaches to updating knowledge bases modeled as extended logic programs have been introduced, ranging from basic methods to incorporate (sequences of) sets of rules into a logic program, to more elaborate methods which use an update policy for specifying how updates must be incorporated. In this article, we introduce a framework for reasoning about evolving knowledge bases, which are represented as extended logic programs and maintained by an update policy. We first describe a formal model which captures various update approaches, and we define a logical language for expressing properties of evolving knowledge bases. We then investigate semantical and computational properties of our framework, where we focus on properties of knowledge states with respect to the canonical reasoning task of whether a given formula holds in a given evolving knowledge base. In particular, we present finitary characterizations of the evolution for certain classes of framework instances, which can be exploited for obtaining decidability results. In more detail, we characterize the complexity of reasoning for some meaningful classes of evolving knowledge bases, ranging from polynomial to double exponential space complexity.