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

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


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.