Disjunctive closures for knowledge compilation

doi:10.1016/j.artint.2014.07.004

Disjunctive closures for knowledge compilation

2014-11-01

11

OA

AI

DOI：10.1016/j.artint.2014.07.004

原文链接

查看原文

摘要

En 中文

The knowledge compilation (KC) map [1] can be viewed as a multi-criteria evaluation of a number of target classes of representations for propositional KC. Using this map, the choice of a class for a given application can be made, considering both the space efficiency of it (i.e., its ability to represent information using little space), and its time efficiency, i.e., the queries and transformations which can be achieved in polynomial time, among those of interest for the application under consideration. When no class of propositional representations offers all the transformations one would expect, some of them can be left implicit. This is the key idea underlying the concept of closure introduced here: instead of performing computationally expensive transformations, one just remembers that they have to be done. In this paper, we investigate the disjunctive closure principles, i.e., disjunction, existential quantification, and their combinations. We provide several characterization results concerning the corresponding closures. We also extend the KC map with new propositional languages obtained as disjunctive closures of several incomplete propositional languages, including the well-known KROM (the CNF formulae containing only binary clauses), HORN (the CNF formulae containing only Horn clauses), and AFT (the affine language, which is the set of conjunctions of XOR-clauses). Each introduced language is evaluated along the lines of the KC map. (C) 2014 Elsevier B.V. All rights reserved.

Keyword:

Knowledge representation

Knowledge compilation

Computational complexity

Disjunctive closures for knowledge compilation

摘要

AI总结

期刊

机构