2002/07/11 by Adnan Darwiche, Darwiche, Adnan, Pierre Marquis +1
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #I.2.3 #I.2.4 #Machine Learning and Algorithms #cs.AI
paper · pdf · doi:10.48550/arxiv.cs/0207045
Proceedings of the Ninth International Workshop on Non-Monotonic Reasoning (NMR'02), Toulouse, 2002 (6-14)
arxiv created 2002/07/11 · openalex publication_date 2002/07/11 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we investigate the extent to which knowledge compilation can be used to improve inference from propositional weighted bases. We present a general notion of compilation of a weighted base that is parametrized by any equivalence--preserving compilation function. Both negative and positive results are presented. On the one hand, complexity results are identified, showing that the inference problem from a compiled weighted base is as difficult as in the general case, when the prime implicates, Horn cover or renamable Horn cover classes are targeted. On the other hand, we show that the inference problem becomes tractable whenever DNNF-compilations are used and clausal queries are considered. Moreover, we show that the set of all preferred models of a DNNF-compilation of a weighted base can be computed in time polynomial in the output size. Finally, we sketch how our results can be used in model-based diagnosis in order to compute the most probable diagnoses of a system.