• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Order Invariance on Decomposable Structures
【24h】

Order Invariance on Decomposable Structures

机译：可分解结构的阶不变性

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

摘要

Order-invariant formulas access an ordering on a structure's universe, but the model relation is independent of the used ordering. They are frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. we study the expressive power of order-invariant monadic second-order (MSO) and first-order (FO) logic on restricted classes of structures that admit certain forms of tree decompositions (not necessarily of bounded width). While order-invariant MSO is more expressive than MSO and, even, CMSO (MSO with modulo-counting predicates) in general, we show that order-invariant MSO and CMSO are equally expressive on graphs of bounded tree width and on planar graphs. This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant FO are also definable in MSO on these classes. These results are applications of a theorem that shows how to lift up definability results for order-invariant logics from the bags of a graph's tree decomposition to the graph itself.
机译：不变顺序公式访问结构的Universe上的顺序，但是模型关系独立于所使用的顺序。它们在计算机科学中经常用于基于逻辑的方法。顺序不变的公式捕获了复杂性类的无序问题，并且它们从数据库的低端方面对数据库查询答案的独立性进行建模。我们研究了在允许某些类型的树分解形式（不一定是有界宽度）的受限结构上，阶不变一元二阶（MSO）和一阶（FO）逻辑的表达能力。尽管顺序不变的MSO比MSO甚至是CMSO（具有模数谓词的MSO）通常更具表现力，但我们证明了顺序不变的MSO和CMSO在有界树宽图和平面图上均具有相同的表现力。由于Courcelle，这扩展了树木的早期结果。此外，我们表明在MSO上这些类中，在定序FO中可定义的所有属性也是可定义的。这些结果是一个定理的应用，该定理显示了如何从图的树分解包到图本身提升顺序不变逻辑的可定义性结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号