Boolean Approximation Revisited. In Abstraction, Reformulation and Approximation: Proceedings of SARA 2007, volume 4612, of Lecture Notes in Artificial Intelligence, pages 329–343, 2007. Springer.
doi  abstract   bibtex   
Most work to date on Boolean approximation assumes that Boolean functions are represented by formulas in conjunctive normal form. That assumption is appropriate for the classical applications of Boolean approximation but potentially limits wider use. We revisit, in a lattice-theoretic setting, so-called envelopes and cores in propositional logic, identifying them with upper and lower closure operators, respectively. This leads to recursive representation-independent characterisations of Boolean approximation for a large class of classes. We show that Boolean development can be applied in a representation-independent setting to develop approximation algorithms for a broad range of Boolean classes, including Horn and Krom functions.

Downloads: 0