ECCC-Report TR05-119https://eccc.weizmann.ac.il/report/2005/119Comments and Revisions published for TR05-119en-usSun, 23 Oct 2005 21:11:46 +0200
Paper TR05-119
| Preferred representations of Boolean relations |
Nadia Creignou,
Phokion G. Kolaitis,
Bruno Zanuttini
https://eccc.weizmann.ac.il/report/2005/119We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables as C; this differs from the usual notion of a basis in that existential quantification of auxiliary variables is not allowed. We give such a basis for every co-clone and in particular for those in the infinite part of the lattice; it turns out that most of these bases correspond to sets of propositional clauses, thus providing a strong link between classes of formulas defined for CSP and CNF representations. We then show that a so-called preferred representation of a relation over one of its bases can be computed efficiently, as well as the minimal co-clone including a given relation, which solves some open structure identification problem as well as the open expressibility problem from database theory.
Sun, 23 Oct 2005 21:11:46 +0200https://eccc.weizmann.ac.il/report/2005/119