Lune

LICS2025Top-tier venue

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

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

2025Year
4Citations

Abstract

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.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

lune papers fulltext ba706c5f-a448-40a5-88f4-90500d6c006a

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines