• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Fields of logic and computation II: Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday >Regularity Equals Monadic Second-Order Definability for Quasi-trees
【24h】

Regularity Equals Monadic Second-Order Definability for Quasi-trees

机译：正则性等于拟树的二阶二阶可定义性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any finite or countable order type, in particular that of rational numbers. They are used to define the rank-width of a countable graph in such a way that it is the least upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are the corresponding directed "trees" and they are also useful to define the modular decomposition of a countable graph. We define algebras with finitely many operations that generate (via infinite terms) these generalized trees. We prove that the associated regular objects (those defined by regular terms) are exactly the ones definable by (i.e., are the unique models of) monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders.
机译：拟树对树进行了概括，因为两个节点之间的唯一“路径”可以是无限的，并且可以具有任何有限或可数的阶次类型，尤其是有理数。它们用于定义可数图的秩宽度，以使其成为其有限诱导子图的秩宽度的最小上限。连接树是相应的有向“树”，它们对于定义可数图的模块化分解也很有用。我们用有限的许多运算来定义代数，这些运算生成（通过无限项）这些广义树。我们证明关联的常规对象（由常规术语定义的对象）正是由一元二阶句子定义的对象（即是其唯一模型）。这些结果使用并推广了W. Thomas对于可数线性阶数的相似结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号