Constraint satisfaction tractability from semi-lattice operations on infinite sets
Constraint satisfaction tractability from semi-lattice operations on infinite sets
复制标题
无限集上半格操作的约束满足可处理性
DOI：
10.1145/2528933
复制
发表时间：
2013
影响因子：
0.5
通讯作者：
Bodirsky M
中科院分区：
文献类型：
--
作者：
Bodirsky M
Jeavons，Cohen和Gyssens的一个著名结果表明，每个约束满足问题（CSP），其中约束是由半格操作保持可以在多项式时间内解决。这是一个基本的事实，所谓的通用代数方法的系统理论的易处理性和硬度在有限域约束的满意度。毫不奇怪，Jeavons等人的定理对任意无限域CSP都失败了。然而，许多实际感兴趣的CSP，特别是那些由人工智能的定性推理演算驱动的CSP，可以用从模型理论的角度来看表现良好的约束语言来制定。特别是，这些约束语言的自同构群往往很大，因为自同构群的n个子集的轨道数量受某个函数inn的限制。在本文中，我们将Jeavons等人的定理推广到无限域CSP，其中n个子集的轨道数量在inn中呈亚指数增长，并证明了这种CSP在半格运算下的保持性意味着多项式时间的可处理性。与Jeavons等人的结果不同，这包括Datatron无法解决的CSP。
A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from artificial intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to belargein the sense that the number of orbits ofn-subsets of the automorphism group is bounded by some function inn.In this article we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits ofn-subsets grows subexponentially inn, and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes CSPs that cannot be solved by Datalog.
登录
查看更多内容
闭包函数和宽度 1 问题
DOI：
--
发表时间：
1999
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
V. Dalmau;J. Pearson
通讯作者：
J. Pearson
局部有限簇中的有限偏序集和拓扑空间
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
B. Larose;L. Zádori
通讯作者：
L. Zádori
随机图上的最小函数
影响因子：
1
作者：
M. Bodirsky;M. Pinsker
通讯作者：
M. Pinsker
DOI：
--
发表时间：
1985
期刊：
影响因子：
--
作者：
H. D. Macpherson
通讯作者：
H. D. Macpherson
用于时间推理的快速算法和数据记录不可表达性
DOI：
--
发表时间：
2008
期刊：
TOCL
影响因子：
--
作者：
M. Bodirsky;Jan Kára
通讯作者：
Jan Kára