Positive and Horn Decomposability of Partially Defined Boolean Functions.
Kazuhisa MakinoKojin YanoToshihide IbarakiPublished in: Discret. Appl. Math. (1997)
Keyphrases
- boolean functions
- uniform distribution
- statistical queries
- positive and negative
- np hard
- threshold functions
- prime implicants
- membership queries
- dnf formulae
- linear threshold
- functional properties
- relevant variables
- read once formulas
- propositional logic
- dnf formulas
- bounded treewidth
- knowledge compilation
- bi decomposition
- knowledge base