一句话：证明有界路径宽的有限域可表示拟阵上，可识别性等价于 MSO 可定义性。
本文研究有限域上可表示且路径宽有界的拟阵中，可识别性质与 MSO 可定义性之间的关系。作者证明存在一个 MSO 转录：给定路径宽为 k 的 F-可表示拟阵，可产生宽度至多 f(k) 的分支分解。由此推出，任何有界路径宽 F-可表示拟阵类的可识别性质都可在 MSO 逻辑中定义，因此可识别性与 MSO 可定义性在该类拟阵上等价。该结果推广了 Bojańczyk、Grohe 与 Pilipczuk 关于有界线性团宽图上两概念等价的工作。
Let ${\mathbb{F}}$ be a finite field. We prove that there is an MSO-transduction which, given an ${\mathbb{F}}$-representable matroid of path-width k, produces a branch-decomposition of width at most f(k), for some function f. As a corollary, any recognizable property of ${\mathbb{F}}$-representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of ${\mathbb{F}}$-representable matroids of bounded path-width. This generalizes the result of Bojańczyk, Grohe and Pilipczuk [Logical Methods in Computer Science 17(1), 2021] which asserts the equivalence of the two notions on graphs of bounded linear clique-width.
DOI 原文 ·
@inproceedings{paperbot8625,
title = {Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width},
author = {Rutger Campbell and Bruno Guillon and Mamadou Moustapha Kanté and Eun Jung Kim and Sang-il Oum},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00057}
}