Relative definability of boolean functions via hypergraphs.
Antonio BucciarelliPasquale MalacariaPublished in: Theor. Comput. Sci. (2002)
Keyphrases
- boolean functions
- uniform distribution
- relevant variables
- dnf formulae
- fixed point
- multi valued
- threshold functions
- functional properties
- learning algorithm
- membership queries
- read once formulas
- bi decomposition
- propositional logic
- binary decision diagrams
- dnf formulas
- prime implicants
- disjunctive normal form
- polynomial size
- decomposition methods
- decision trees