Extending the Knowledge Compilation mAP: Krom, Horn, Affine and Beyond

Abstract

We extend the knowledge compilation map introduced by Darwiche and Marquis with three influential propositional fragments, the Krom CNF one (also known as the bijunctive fragment), the Hom CNF fragment and the affine fragment (also known as the biconditional fragment) as well as seven additional languages based on them, and composed respectively of Krom or Hom CNF formulas, renamable Hom CNF formulas, disjunctions of Krom CNF formulas, disjunctions of Hom CNF formulas, disjunctions of Krom or Hom CNF formulas, disjunctions of renamable Hom CNF formulas, and disjunction of fine formulas. Each fragment is evaluated w.r.t. several criteria, including the complexity of basic quaries and transformation, and its spatial efficiency is also analysed.