On Singleton Arc Consistency for CSPs Defined by Monotone Patterns.
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns.
复制标题
关于单调模式定义的 CSP 的单例弧一致性。
DOI：
10.1007/s00453-018-0498-2
复制
发表时间：
2019
期刊：
影响因子：
1.1
通讯作者：
Carbonnel C
中科院分区：
文献类型：
--
作者：
Carbonnel C
单例圆弧一致性是局部一致性的一种重要类型，最近被证明可以解决所有宽度有界的约束语言上的约束满足问题。我们的目标是刻画由禁止模式定义的所有类CSP，这些CSP通过单弧一致性求解并在去除约束下闭合。我们确定了五个新的模式，它们的缺失确保了单点弧相容的可解性，其中四个模式是可证明的最大模式，三个模式推广了2-SAT。结合其他模式的简单反例，我们在实现完整分类方面取得了重大进展。
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.