paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Axiomatization of betweenness in order-theoretic trees

序理论树中 betweenness 关系的公理化
LMCS vol.Volume 17, Issue 12021匹配度 1/10 · 该论文是序理论树中介于关系的 MSO/一阶逻辑公理化研究,属于纯数学逻辑与图论方向,与用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析没有直接交集。虽然涉及逻辑形式化,但未面向程序分析、验证或工业落地场景。引用 4 inbox
Bruno Courcelle
crossref: 2026-09-10

AI 速览

一句话:给出序理论树中介于关系的 MSO 公理化,并证明拟树上的诱导介于关系可由一阶语句刻画。

树的三元 betweenness 关系 B(x,y,z) 表示 y 在 x 与 z 的唯一路径上。本文将其推广到序理论树:任意节点的上集为全序的偏序,此时两节点间路径可有无限多节点。前人针对 join-tree(任意两节点有最小上界)的 betweenness 定义了 quasi-tree,并给出一阶公理化,动机是定义可数图的 rank-width。本文得到序理论树中 betweenness 的 monadic second-order 公理化;定义并比较若干诱导 betweenness 关系,即不同广义树中 betweenness 对节点子集的限制;并证明 quasi-tree 中诱导 betweenness 可由一阶语句刻画,证明借助序理论树。

问题
如何为树及序理论树中的三元 betweenness 关系给出逻辑公理化,并刻画其诱导版本?
方法
使用一阶与 monadic second-order 逻辑,在序理论树、join-tree 与 quasi-tree 框架下定义并比较 betweenness 及其节点子集限制。
评估
理论证明:给出序理论树中 betweenness 的 MSO 公理化,证明 quasi-tree 诱导 betweenness 的一阶可刻画性,并与前人 join-tree 结果比较。
原文摘要(Abstract)

The ternary betweenness relation of a tree, B(x,y,z) expresses that y is on the unique path between x and z. This notion can be extended to order-theoretic trees defined as partial orders such that the set of nodes larger than any node is linearly ordered. In such generalized trees, the unique "path" between two nodes can have infinitely many nodes. We generalize some results obtained in a previous article for the betweenness of join-trees. Join-trees are order-theoretic trees such that any two nodes have a least upper-bound. The motivation was to define conveniently the rank-width of a countable graph. We called quasi-tree the structure based on the betweenness relation of a join-tree. We proved that quasi-trees are axiomatized by a first-order sentence. Here, we obtain a monadic second-order axiomatization of betweenness in order-theoretic trees. We also define and compare several induced betweenness relations, i.e., restrictions to sets of nodes of the betweenness relations in generalized trees of different kinds. We prove that induced betweenness in quasi-trees is characterized by a first-order sentence. The proof uses order-theoretic trees.

链接与引用

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

BibTeX
@article{paperbot1340,
  title = {Axiomatization of betweenness in order-theoretic trees},
  author = {Bruno Courcelle},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 1},
  year = {2021},
  doi = {10.23638/lmcs-17(1:11)2021}
}