一句话：刻画了偏序禁止模式定义的二元 CSP 中弧相容可解的五个模式，扩展 BTP 并发现新易解类。
约束满足问题（CSP）可处理片段的刻画是理论计算机科学与人工智能的重要挑战。禁止模式（泛型子实例）可定义既非纯语言也非纯结构的 CSP 片段。已知二元 CSP 实例若不出现 broken-triangle pattern（BTP），则属于包含所有树结构实例的类，并可由弧相容（AC）判定。本文刻画了具有 AC 可解性质的简单偏序禁止模式，证明 BTP 只是五个此类 AC 可解模式之一；其余四个模式导出了新的可处理类。
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic sub-instances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of simple partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes.
@article{paperbot89,
title = {The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns},
author = {Martin C. Cooper and Stanislav Živný},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 4},
year = {2017},
doi = {10.23638/lmcs-13(4:26)2017}
}