Let $\psi$ be a sentence in the counting monadic second-order logic of matroids and let F be a finite field. Hlineny's Theorem says that we can test whether F-representable matroids satisfy $\psi$ 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 Hlineny'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.
@article{10_37236_11660,
author = {Daryl Funk and Dillon Mayhew and Mike Newman},
title = {Tree automata and pigeonhole classes of matroids. {II}},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {3},
doi = {10.37236/11660},
zbl = {7725122},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11660/}
}
TY - JOUR
AU - Daryl Funk
AU - Dillon Mayhew
AU - Mike Newman
TI - Tree automata and pigeonhole classes of matroids. II
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/11660/
DO - 10.37236/11660
ID - 10_37236_11660
ER -
%0 Journal Article
%A Daryl Funk
%A Dillon Mayhew
%A Mike Newman
%T Tree automata and pigeonhole classes of matroids. II
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11660/
%R 10.37236/11660
%F 10_37236_11660
Daryl Funk; Dillon Mayhew; Mike Newman. Tree automata and pigeonhole classes of matroids. II. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11660
