Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Sang-il Oum
摘要
Let be a finite field. We prove that there is an MSO-transduction which, given an -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 -representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of -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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
相关 Paper
- Linear rankwidth meets stabilityJaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian SiebertzSODA 2020
- Regular Grammars for Sets of Graphs of Tree-Width 2Marius Bozga, Radu Iosif, Florian ZulegerLICS 2025
- Low Rank MSOMikolaj Bojanczyk, Michal Pilipczuk, Wojciech Przybyszewski, Marek Sokolowski 等LICS 2026
- Graphs of unbounded linear cliquewidth must transduce all treesMikolaj Bojanczyk, Pierre OhlmannLICS 2025
- Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank InequalitiesKristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász 等SODA 2026
