TR05-119 Authors: Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini

Publication: 23rd October 2005 21:11

Downloads: 2046

Keywords:

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.