Preferred representations of Boolean relations
Preferred representations of Boolean relations
复制标题
布尔关系的首选表示
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
B. Zanuttini
中科院分区：
文献类型：
--
作者：
N. Creignou;Phokion G. Kolaitis;B. Zanuttini
我们在邮政晶格中介绍了一个统一的基础的概念。 B和C的相同变量是从一个基础的常规概念中，因为我们不允许使用辅助变量的量化。 ; 它事实证明，这些基础中的大多数对应于一组命题子句，因此在CSP和CNF表示的一类公式之间提供了牢固的联系。计算出的Ecien Tly以及最小的共同犯罪，包括给定的关系，该关系解决了一些开放的结构识别问题以及数据库理论中的开放表达性问题。
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 diers from the usual notion of a basis in that existential quantication of auxiliary variables is not allowed. We give such a basis for every co-clone and in particular for those in the innite 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 dened 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 ecien tly, as well as the minimal co-clone including a given relation, which solves some open structure identication problem as well as the open expressibility problem from database theory.