Existential Closures for Knowledge Compilation

Marquis, Pierre

doi:10.5591/978-1-57735-516-8/IJCAI11-171

Existential Closures for Knowledge Compilation

Pierre Marquis

IJCAI 2011 pp. 996-1001

doi:10.5591/978-1-57735-516-8/IJCAI11-171 /ijcai/2011/marquis2011ijcai-existential/

Abstract

We study the existential closures of several propositional languages L considered recently as target languages for knowledge compilation (KC), namely the incomplete fragments KROM-C, HORN-C, K/H-C, renH-C, AFF, and the corresponding disjunction closures KROM-C[V], HORN-C[V], K/H-C[V], renH-C[V], and AFF[V]. We analyze the queries, transformations, expressiveness and succinctness of the resulting languages L[E] in order to locate them in the KC map. As a by-product, we also address several issues concerning disjunction closures that were left open so far. From our investigation, the language HORN-C[V, E] (where disjunctions and existential quantifications can be applied to Horn CNF formulae) appears as an interesting target language for the KC purpose, challenging the influential DNNF languages.

PDF IJCAI Semantic Scholar

Cite

Text

Marquis. "Existential Closures for Knowledge Compilation." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-171

Markdown

[Marquis. "Existential Closures for Knowledge Compilation." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/marquis2011ijcai-existential/) doi:10.5591/978-1-57735-516-8/IJCAI11-171

BibTeX

@inproceedings{marquis2011ijcai-existential,
  title     = {{Existential Closures for Knowledge Compilation}},
  author    = {Marquis, Pierre},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {996-1001},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-171},
  url       = {https://mlanthology.org/ijcai/2011/marquis2011ijcai-existential/}
}