Computer Science – Artificial Intelligence
Scientific paper
2002-07-11
Computer Science
Artificial Intelligence
Proceedings of the Ninth International Workshop on Non-Monotonic Reasoning (NMR'02), Toulouse, 2002 (6-14)
Scientific paper
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.
Darwiche Adnan
Marquis Pierre
No associations
LandOfFree
Compilation of Propositional Weighted Bases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Compilation of Propositional Weighted Bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compilation of Propositional Weighted Bases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-185232