ECAI-2000 Conference Paper

[full paper]

Compiling Stratified Belief Bases

Sylvie Coste-Marquis, Pierre Marquis

Many coherence-based approaches to inconsistency handling within propositional belief bases have been proposed so far. They consist in selecting one or several preferred consistent subbases of the given (usually inconsistent) stratified belief base (SBB), then using classical inference from some of the selected subbases. Unfortunately, deciding the corresponding inference relations is typically hard from the computational complexity point of view. In this paper, we show how some knowledge compilation techniques for classical inference can be used to circumvent the intractability of such sophisticated inference relations. For several families of compiled SBBs and several selection policies, the complexity of skeptical inference is identified. Interestingly, some tractable restrictions are exhibited.

Keywords: Automated reasoning

Citation: Sylvie Coste-Marquis, Pierre Marquis: Compiling Stratified Belief Bases. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.23-27.