paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Algebraic and logical descriptions of generalized trees

广义树的代数与逻辑描述
LMCS vol.Volume 13, Issue 32017匹配度 1/10 · 论文研究拟树/联接树的代数生成与 MSO 逻辑刻画,属于纯逻辑与自动机理论;虽与形式化方法相关,但不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。与用户当前研究画像几乎没有直接交集。引用 7 inbox
Bruno Courcelle
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:用有限代数运算与无穷项生成拟树、联接树,并证明其正则对象恰为 MSO 句子的唯一模型。

本文研究拟树(quasi-trees)与联接树(join-trees)两类广义树:拟树允许两节点间唯一路径为无穷且具有任意可数序型,可用于把可数图的 rank-width 定义为有限诱导子图 rank-width 的上确界;联接树是对应有向树,用于可数图的模分解,并扩展出节点儿子集合带线性序的有序联接树。作者用有限多个运算的代数、经无穷项生成这些结构,并定义由正则项给出的正则对象。主要结论是:这些正则对象恰好是单子二阶(MSO)句子的唯一模型。该结果推广了 W. Thomas 关于可数线性序的定理。

问题
如何为拟树、联接树及有序联接树等广义树结构提供统一的代数生成方式,并用逻辑刻画其正则对象?
方法
定义有限多个运算构成的代数,通过无穷项生成这些广义树;再用正则项定义正则对象,并建立其与单子二阶逻辑唯一模型之间的对应。
评估
理论证明:证明正则对象恰为 MSO 句子的唯一模型,从而推广 W. Thomas 关于可数线性序的定理;未涉及实现或实验。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@article{Courcelle16,
  title = {Algebraic and logical descriptions of generalized trees},
  author = {Bruno Courcelle},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 13, Issue 3},
  year = {2017},
  doi = {10.23638/lmcs-13(3:7)2017}
}