Existential Closures for Knowledge Compilation

Marquis, Pierre

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

Existential Closures for Knowledge Compilation

Pierre Marquis

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 996-1000.

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

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.

Pierre Marquis. 2011. Existential Closures for Knowledge Compilation. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 996–1000. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-171

@inproceedings{ijcai2011p171,
  title     = {Existential Closures for Knowledge Compilation},
  author    = {Marquis, Pierre},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {996--1000},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-171},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-171},
}

TY  - CPAPER
TI  - Existential Closures for Knowledge Compilation
AU  - Marquis, Pierre
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 996
EP  - 1000
DO  - 10.5591/978-1-57735-516-8/IJCAI11-171
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-171
ER  -