Tractable Cover Compilations

Boufkhad, Yacine; Grégoire, Éric; Marquis, Pierre; Mazure, Bertrand; Sais, Lakhdar

Tractable Cover Compilations

Yacine Boufkhad, Éric Grégoire, Pierre Marquis, Bertrand Mazure, Lakhdar Sais

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 122-126.

Abstract

Tractable covers are introduced as a new approach to equivalence-preserving compilation of propositional knowledge bases. First, a general framework is presented. Then, two specific cases are considered. In the first one, partial interpretations are used to shape the knowledge base into tractable formulas from several possible classes. In the second case, they are used to derive renamable Horn formulas. This last case is proved less space-consuming than prime implicants cover compilations for every knowledge base. Finally, experimental results show that the new approaches can prove efficient w.r.t. direct query answering and offer significant time and space savings w.r.t. prime implicants covers.

Yacine Boufkhad, Éric Grégoire, Pierre Marquis, Bertrand Mazure, and Lakhdar Sais. 1997. Tractable Cover Compilations. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 122–126. https://ijcai.org/proceedings/1997/19

@inproceedings{ijcai1997p19,
  title     = {Tractable Cover Compilations},
  author    = {Boufkhad, Yacine and Grégoire, Éric and Marquis, Pierre and Mazure, Bertrand and Sais, Lakhdar},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {122--126},
  year      = {1997},
  note      = {Automated Reasoning},
  url       = {https://ijcai.org/proceedings/1997/19},
}

TY  - CPAPER
TI  - Tractable Cover Compilations
AU  - Boufkhad, Yacine
AU  - Grégoire, Éric
AU  - Marquis, Pierre
AU  - Mazure, Bertrand
AU  - Sais, Lakhdar
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 122
EP  - 126
UR  - https://ijcai.org/proceedings/1997/19
ER  -