Hélène Fargier, Pierre Marquis
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 Horn 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 Horn CNF formulas, renamable Horn CNF formulas, disjunctions of Krom CNF formulas, disjunctions of Horn CNF formulas, disjunctions of Krom or Horn CNF formulas, disjunctions of renamable Horn CNF formulas, and disjunction of affine formulas. Each fragment is evaluated w.r.t. several criteria, including the complexity of basic queries and transformations, and its spatial efficiency is also analyzed.
Subjects: 3. Automated Reasoning; 11. Knowledge Representation
Submitted: Apr 9, 2008