Prime Compilation of Non-Clausal Formulae

Previti, Alessandro; Ignatiev, Alexey; Morgado, Antonio; Silva, João P. Marques

Prime Compilation of Non-Clausal Formulae

Alessandro Previti, Alexey Ignatiev, António Morgado, João P. Marques Silva

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1980-1987.

Abstract

Formula compilation by generation of prime implicates or implicants finds a wide range of applications in AI. Recent work on formula compilation by prime implicate/implicant generation often assumes a Conjunctive/Disjunctive Normal Form (CNF/DNF) representation. However, in many settings propositional formulae are naturally expressed in non-clausal form. Despite a large body of work on compilation of non-clausal formulae, in practice existing approaches can only be applied to fairly small formulae, containing at most a few hundred variables. This paper describes two novel approaches for the compilation of non-clausal formulae either with prime implicants or implicates, that is based on propositional Satisfiability (SAT) solving. These novel algorithms also find application when computing all prime implicates of a CNF formula. The proposed approach is shown to allow the compilation of non-clausal formulae of size significantly larger than existing approaches.

Alessandro Previti, Alexey Ignatiev, Antonio Morgado, and João P. Marques Silva. 2015. Prime Compilation of Non-Clausal Formulae. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1980–1987. https://ijcai.org/proceedings/2015/281

@inproceedings{ijcai2015p281,
  title     = {Prime Compilation of Non-Clausal Formulae},
  author    = {Previti, Alessandro and Ignatiev, Alexey and Morgado, Antonio and Silva, João P. Marques},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1980--1987},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/281},
}

TY  - CPAPER
TI  - Prime Compilation of Non-Clausal Formulae
AU  - Previti, Alessandro
AU  - Ignatiev, Alexey
AU  - Morgado, Antonio
AU  - Silva, João P. Marques
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1980
EP  - 1987
UR  - https://ijcai.org/proceedings/2015/281
ER  -