Graph Structures for Knowledge Representation and Reasoning - 6th International Workshop, GKR 2020, Virtual Event, September 5, 2020, Revised Selected Papers
Graph Structures for Knowledge Representation and Reasoning - 6th International Workshop, GKR 2020, Virtual Event, September 5, 2020, Revised Selected Papers
复制标题
知识表示和推理的图结构 - 第六届国际研讨会，GKR 2020，虚拟活动，2020 年 9 月 5 日，修订后的精选论文
DOI：
10.1007/978-3-030-72308-8_9
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Cohen D
中科院分区：
文献类型：
--
作者：
Cohen D
模式是二进制约束满足问题（CSP）的一个通用实例，其中某些变量值分配对的兼容性可能是未指定的。禁止模式的概念导致了CSP的几个新的易处理类的发现。然而，这个领域的年龄来的时候，理论研究的代数模式。我们提出了一个伽罗瓦之间的连接，由禁止模式集和通用实例集组成的格，并调查其后果。然后，我们扩展模式，增强模式，并表现出类似的伽罗瓦连接。增强模式是一种比平面模式（即非增强模式）更强大的语言，正如我们所证明的那样，对于任何情况，树宽以k为界的实例不能通过禁止有限的平面模式集来指定，但可以通过有限的增强模式集来指定。一个有限的扩充模式集也可以描述类的实例，使每个实例有一个弱的arityk近多态性（从而覆盖所有易处理的语言类）。我们调查的权力，禁止扩充模式，并讨论其潜在的描述新的易处理的类。
A pattern is a generic instance of a binary constraint satisfaction problem (CSP) in which the compatibility of certain pairs of variable-value assignments may be unspecified. The notion of forbidden pattern has led to the discovery of several novel tractable classes for the CSP. However, for this field to come of age it is time for a theoretical study of the algebra of patterns. We present a Galois connection between lattices composed of sets of forbidden patterns and sets of generic instances, and investigate its consequences. We then extend patterns to augmented patterns and exhibit a similar Galois connection. Augmented patterns are a more powerful language than flat (i.e. non-augmented) patterns, as we demonstrate by showing that, for any, instances with tree-width bounded bykcannot be specified by forbidding a finite set of flat patterns but can be specified by a finite set of augmented patterns. A single finite set of augmented patterns can also describe the class of instances such that each instance has a weak near-unanimity polymorphism of arityk(thus covering all tractable language classes).We investigate the power of forbidding augmented patterns and discuss their potential for describing new tractable classes.