Lune

LICS2025顶会

Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width

Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Sang-il Oum

2025年份
4被引次数

摘要

Let F{\mathbb{F}} be a finite field. We prove that there is an MSO-transduction which, given an F{\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 F{\mathbb{F}}-representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of F{\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.

问问这篇 Paper

智能体会读完全文。

Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖