Conference Proceedings

Boolean approximation revisited

P SCHACHTE, H SONDERGAARD, I Miguel (ed.), W Ruml (ed.)

Abstraction, Reformulation and Approximation - 7th International Symposium, SARA 2007 | Springer Berlin Heidelberg | Published : 2007


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 cla..

View full abstract