Two new homomorphism dualities and lattice operations
Two new homomorphism dualities and lattice operations
复制标题
两个新的同态对偶性和晶格运算
DOI：
10.1093/logcom/exq030
复制
发表时间：
2010
影响因子：
0.7
通讯作者：
Carvalho C
中科院分区：
文献类型：
--
作者：
Carvalho C
近年来，可定义在数据日志的不同片段中的约束满足问题的研究变得相当重要。我们考虑可定义在数据日志的最小自然递归片段中的约束满足问题，即每个规则至多有一个扩展数据库谓词(EDB)的一元线性数据日志的最小自然递归片段中的约束满足问题，以及该片段的最小非线性扩展中的约束满足问题。我们用同态对偶和格运算分别给出了这类问题的组合和代数刻画，并将我们的结果应用于研究图H-染色问题。
The study of constraint satisfaction problems (CSPs) definable in various fragments of Datalog has recently gained considerable importance.We consider CSPs that are definable in the smallest natural recursive fragment of Datalog—monadic linear Datalog with at most one EDB (extensional database predicates) per rule, and also in the smallest nonlinear extension of this fragment. We give combinatorial and algebraic characterizations of such problems, in terms of homomorphism dualities and lattice operations, respectively.We then apply our results to study graph H-colouring problems.
登录
查看更多内容
DOI：
10.1142/s0218196797000253
发表时间：
1997
期刊：
Int. J. Algebra Comput.
影响因子：
--
作者：
L. Zádori
通讯作者：
L. Zádori
闭包函数和宽度 1 问题
DOI：
--
发表时间：
1999
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
V. Dalmau;J. Pearson
通讯作者：
J. Pearson
关于有向图着色问题和树宽对偶性
DOI：
10.1016/j.ejc.2007.11.004
发表时间：
2005
期刊：
20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05)
影响因子：
--
作者：
Albert Atserias
通讯作者：
Albert Atserias
对指数长问题的简短回答：同态对偶的极值方面
DOI：
10.1137/s0895480104445630
发表时间：
2005
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
J. Nesetril;Claude Tardif
通讯作者：
Claude Tardif
有限对偶结构上的多数函数
DOI：
10.1016/j.ejc.2007.11.007
发表时间：
2008
期刊：
Eur. J. Comb.
影响因子：
--
作者：
C. Loten;Claude Tardif
通讯作者：
Claude Tardif