• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Graphs of relational structures: restricted types
【24h】

Graphs of relational structures: restricted types

机译：关系结构图：受限类型

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In our LICS 2004 paper we introduced an approach to the study of the local structure of finite algebras and relational structures that aims at applications in the Constraint Satisfaction Problem (CSP). This approach involves a graph associated with an algebra A or a relational structure A, whose vertices are the elements of A (or A), the edges represent subsets of A such that the restriction of some term operation of A is `good' on the subset, that is, act as an operation of one of the 3 types: semilattice, majority, or affine. In this paper we significantly refine and advance this approach. In particular, we prove certain connectivity and rectangularity properties of relations over algebras related to components of the graph connected by semilattice and affine edges. We also prove a result similar to 2-decomposition of relations invariant under a majority operation, only here we do not impose any restrictions on the relation. These results allow us to give a new, somewhat more intuitive proof of the bounded width theorem: the CSP over algebra A has bounded width if and only if A does not contain affine edges. Actually, this result shows that bounded width implies width (2,3). We also consider algebras with edges from a restricted set of types. In particular, it can be proved that type restrictions are preserved under the standard algebraic constructions. Finally, we prove that algebras without semilattice edges have few subalgebras of powers, that is, the CSP over such algebras is also polynomial time.
机译：在我们的LICS 2004论文中，我们引入了一种方法来研究有限代数的局部结构和关系结构，其目的是在约束满足问题（CSP）中的应用。这种方法涉及与代数A或关系结构A相关联的图，其顶点是A（或A）的元素，边表示A的子集，因此对A的某些项运算的限制为“好”。子集，即作为以下三种类型之一的运算：半格，多数或仿射。在本文中，我们将显着改进和改进这种方法。特别地，我们证明了与由半晶格和仿射边缘连接的图的分量有关的代数上的关系的某些连通性和矩形性。我们还证明了一个与多数操作下不变的关系的2分解相似的结果，仅在这里我们不对该关系施加任何限制。这些结果使我们能够给出关于边界宽度定理的新的，更直观的证明：当且仅当A不包含仿射边时，代数A上的CSP才具有边界宽度。实际上，此结果表明，有界宽度表示宽度（2,3）。我们还考虑边缘有限的代数形式的代数。特别是，可以证明在标准代数结构下保留了类型限制。最后，我们证明没有半晶格边的代数几乎没有幂次子代，也就是说，此类代数上的CSP也是多项式时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号