2019/10/10 by Daryl Funk, Funk, Daryl, Dillon Mayhew +2
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1910.04361
openalex publication_date 2019/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let ψ be a sentence in the counting monadic second-order logic of matroids and let \mathbbF be a finite field. Hliněný's Theorem says that we can test whether \mathbbF-representable matroids satisfy ψ using an algorithm that is fixed-parameter tractable with respect to branch-width. In a previous paper we proved there is a similar fixed-parameter tractable algorithm that can test the members of any efficiently pigeonhole class. In this sequel we apply results from the first paper and thereby extend Hliněný's Theorem to the classes of fundamental transversal matroids, lattice path matroids, bicircular matroids, and H-gain-graphic matroids, when H is a finite group. As a consequence, we can obtain a new proof of Courcelle's Theorem.