Extending the Knowledge Compilation Map: Closure Principles
Fargier Hélène, Pierre Marquis · Frontiers in artificial intelligence and applications · 2008
We extend the knowledge compilation map introduced by Darwiche and Marquis with new propositional fragments obtained by applying closure principles to several fragments studied so far. We investigate two closure principles: disjunction and implicit forgetting (i.e., existential quantification). Each introduced fragment is evaluated w.r.t. several criteria, including the complexity of basic queries and transformations, and its spatial efficiency is also analyzed.