Compilation of static and evolving conditional knowledge bases for computing induced nonmonotonic inference relations

摘要

Several different semantics have been proposed for conditional knowledge bases R containing qualitative conditionals of the form "If A, then usually B", leading to different nonmonotonic inference relations induced by R. For the notion of c-representations which are a subclass of all ranking functions accepting R, a skeptical inference relation, called c-inference and taking all c-representations of R into account, has been suggested. In this article, we develop a 3-phase compilation scheme for both knowledge bases and skeptical queries to constraint satisfaction problems. In addition to skeptical c-inference, we show how also credulous and weakly skeptical c-inference can be modelled as constraint satisfaction problems, and that the compilation scheme can be extended to such queries. We further extend the compilation approach to knowledge bases evolving over time. The compiled form of R is reused for incrementally compiling extensions, contractions, and updates of R. For each compilation step, we prove its soundness and completeness, and demonstrate significant efficiency benefits when querying the compiled version of R. These findings are also supported by experiments with the software system InfOCF that employs the proposed compilation scheme.