Tight Complexity Bounds for Reasoning in the Description Logic BEL

Abstract. Recently, Bayesian extensions of Description Logics, and in particular the logic BEL, were introduced as a means of representing certain knowledge that depends on an uncertain context. In this paper we introduce a novel structure, called proof structure, that encodes the contextual information required to deduce subsumption relations from a BEL knowledge base. Using this structure, we show that probabilis-tic reasoning in BEL can be reduced in polynomial time to standard Bayesian network inferences, thus obtaining tight complexity bounds for reasoning in BEL.