Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-119 | 15th September 2005 00:00

Preferred representations of Boolean relations


Authors: Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini
Publication: 23rd October 2005 21:11
Downloads: 3378


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

ISSN 1433-8092 | Imprint