.png){kind=icon}
返回
Compiling propositional weighted bases
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2004.04.005.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we investigate the extent to which knowledge compilation can be used to improve model checking and inference from propositional weighted bases. We first focus on the compilability issue for both problems, deriving mainly non-compilability results in the case preferences are subject to change. Then, we present a general notion of C-normal weighted base that is parametrized by a tractable class C for the clausal entailment problem. We show how every weighted base can be turned (compiled) into a query-equivalent C-normal base whenever C is a complete class for propositional logic. Both negative and positive results are presented. On the one hand, complexity results are identified, showing that the inference problem from a C-normal 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 both the model checking and the (clausal) inference problem become tractable whenever DNNF-normal bases are considered. Moreover, we show that the set of all preferred models of a DNNF-normal weighted base can be computed in time polynomial in the output size, and as a consequence, model checking is also tractable for such bases. Finally, we sketch how our results can be used in model-based diagnosis in order to compute the most likely diagnoses of a system. (C) 2004 Published by Elsevier B.V.
Keyword:
knowledge representation
belief bases
penalty logic
knowledge compilation
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。