paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Rank-decreasing transductions

秩递减转换
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 1/10 · 该论文属于纯逻辑与自动机理论研究,讨论 MSO 可定义转换与割秩刻画,不涉及 LLM、Agent、程序静态分析、浮点分析或贝叶斯程序分析,与用户当前研究画像几乎没有直接交集。引用 1 inbox
Mikołaj Bojańczyk, Pierre Ohlmann
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:用割秩刻画 MSO 可定义转换:在有界树宽输入上,渐近降低割秩的转换恰为 MSO 可定义转换。

本文提出从割秩(cut-rank)角度研究图与更一般结构上的转换:比较输入与输出同一底层集合中各子集割秩的变化。核心结果给出逻辑可定义转换的一种纯结构刻画:在输入结构树宽有界的假设下,转换在渐近意义下递减割秩,当且仅当它可由一元二阶逻辑(MSO)定义。该刻画避免直接诉诸逻辑,用割秩这一结构量统一描述 MSO 转换的语义。作者进一步证明,若取消输入树宽有界这一假设,该等价刻画不再成立,从而说明该假设的本质性。

问题
如何在不直接引用逻辑的情况下,刻画可由逻辑(尤其 MSO)定义的图或结构转换?
方法
利用 Oum 的割秩,比较输入与输出在同一底层集合上子集割秩的变化,并在输入树宽有界时分析转换的渐近割秩递减性质。
评估
通过证明有界树宽下割秩递减与 MSO 可定义性的等价,并构造反例说明取消树宽有界假设后该等价不再成立。
原文摘要(Abstract)

We propose to study transformations on graphs, and more generally structures, by looking at how the cut-rank (as introduced by Oum) of subsets is affected when going from the input structure to the output structure. We consider transformations in which the underlying sets are the same for both the input and output, and so the cut-ranks of subsets can be easily compared. The purpose of this paper is to give a characterisation of logically defined transductions that is expressed in purely structural terms, without referring to logic: transformations which decrease the cut-rank, in the asymptotic sense, are exactly those that can be defined in monadic second-order logic. This characterisation assumes that the transduction has inputs of bounded treewidth; we also show that the characterisation fails in the absence of any assumptions.

链接与引用

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

BibTeX
@inproceedings{BojanczykO24,
  title = {Rank-decreasing transductions},
  author = {Mikołaj Bojańczyk and Pierre Ohlmann},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662083}
}