Caterpillar Duality for Constraint Satisfaction Problems
Caterpillar Duality for Constraint Satisfaction Problems
复制标题
约束满足问题的 Caterpillar 对偶性
DOI：
10.1109/lics.2008.19
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Carvalho C
中科院分区：
文献类型：
--
作者：
Carvalho C
约束满足问题的研究可定义在各种片段的数据库最近获得了相当的重要性。我们认为，约束满足问题，是可定义的最小的自然递归片段的Datasheet-一元线性Datasheet，最多一个教育局每规则。我们给出了这些问题的组合和代数特征，在卡特彼勒对偶和格运算，分别。然后，我们应用我们的结果来研究图H-着色问题。
The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog - monadic linear Datalog with at most one EDB per rule. We give combinatorial and algebraic characterisations of such problems, in terms of caterpillar dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems.