Irrelevant Updates of Nonmonotonic Knowledge Bases
Ján Šefránek, Jozef Šiška · European Conference on Artificial Intelligence · 2006
The second postulate of Katsuno and Mendelzon, 2[KM] hereafter, characterizes irrelevant updates: if ψ implies μ, then ψ μ is equivalent to ψ, where ψ is a knowledge base, μ is an update and is an update operator [3]. We show that the postulate has to be modified, if nonmonotonic assumptions are considered. Our characterization of irrelevant updates is based on a dependency framework [5], which provides an alternative semantics of multidimensional dynamic logic programming (MDyLP). MDyLP [4] can be viewed as a logical idealization of nonmonotonic knowledge bases (NMKB). Unwanted generation of new models caused by cyclic or tautological updates has been a serious problem of MDyLP for a time. Recently, the problem has been solved for dynamic logic programs in [1] and for the general MDyLP in [2]. The solution of [1] is based on Refined Extension Principle with ambition to express features essential for a “right” semantics of logic program updates. Unfortunately, the principle has not been extended to the general case of MDyLP and the trivial semantics assigning empty set of models to each dynamic logic program satisfies the principle, see [2]. We believe that the role of nonmonotonic assumptions (and dependencies on assumptions) is crucial for understanding the semantic problems of NMKBs and also for understanding unwanted generation of models.