Name
Abstract | ||
|---|---|---|
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, respec- tively. This leads to recursive representation-independent characterisa- tions of Boolean approximation for a large class of classes. We show that Boolean development can be applied in a representation-independent set- ting to develop approximation algorithms for a broad range of Boolean classes, including Horn and Krom functions. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73580-9_26 | Symposium on Abstraction, Reformulation and Approximation |
Keywords | Field | DocType |
boolean function,krom function,representation-independent characterisations,boolean development,classical application,lattice-theoretic setting,broad range,approximation algorithm,boolean approximation,boolean class,independent set,conjunctive normal form,propositional logic,closure operator | Boolean function,Maximum satisfiability problem,Stone's representation theorem for Boolean algebras,Discrete mathematics,Boolean circuit,Boolean algebras canonically defined,Parity function,Product term,Boolean expression,Mathematics | Conference |
Volume | ISSN | Citations |
4612 | 0302-9743 | 4 |
PageRank | References | Authors |
0.43 | 17 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Schachteand | 1 | 4 | 0.43 |
| Harald Søndergaard | 2 | 858 | 79.52 |