一句话:用有限代数运算与无穷项生成拟树、联接树,并证明其正则对象恰为 MSO 句子的唯一模型。
本文研究拟树(quasi-trees)与联接树(join-trees)两类广义树:拟树允许两节点间唯一路径为无穷且具有任意可数序型,可用于把可数图的 rank-width 定义为有限诱导子图 rank-width 的上确界;联接树是对应有向树,用于可数图的模分解,并扩展出节点儿子集合带线性序的有序联接树。作者用有限多个运算的代数、经无穷项生成这些结构,并定义由正则项给出的正则对象。主要结论是:这些正则对象恰好是单子二阶(MSO)句子的唯一模型。该结果推广了 W. Thomas 关于可数线性序的定理。
Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any countable order type. They are used to define the rank-width of a countable graph in such a way that it is equal to the least upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are the corresponding directed trees. They are useful to define the modular decomposition of a countable graph. We also consider ordered join-trees, that generalize rooted trees equipped with a linear order on the set of sons of each node. 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 that are the unique models of monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders.