• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
【24h】

Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction

机译：减少有限界同构结构，并提高有限域约束满足的可处理性

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

摘要

Many natural decision problems can be formulated as constraint satisfaction problems for reducts of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of topological polymorphism clones. Moreover, we study the subclass C of CSPs for structures that are first-order definable over equality with parameters. Also this class C properly extends the class of all finite-domain CSPs. We show that the tractability conjecture for reducts of finitely bounded homogeneous structures is for C equivalent to the finite-domain tractability conjecture.
机译：可以将许多自然决策问题表述为约束有限均质结构的约简的约束满足问题。这类问题是CSP在有限域上的广泛概括。我们的第一个结果是从此类无限域CSP到有限域CSP的一般多项式时间约简。我们使用这种减少来获得可以根据拓扑多态性克隆表示的新的强大的多项式时间可处理性条件。此外，我们研究了CSP的子类C，该子类对于可以在带参数的相等性上进行一阶定义的结构。而且，此类C适当地扩展了所有有限域CSP的类。我们表明，有限界齐次结构的约简的可预测性对于C等于有限域可预测性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号