Automata-II-arXiv.pdf (516.64 kB)

# Tree automata and pigeonhole classes of matroids -- II

journal contribution

posted on 2021-12-01, 19:46 authored by Daryl Funk, Dillon Mayhew, Mike NewmanLet $\psi$ be a sentence in the counting monadic second-order logic of
matroids. Let F be a finite field. Hlineny's Theorem says there is a
fixed-parameter tractable algorithm for testing whether F-representable
matroids satisfy $\psi$, with respect to the parameter of branch-width. In a
previous paper we proved there is a similar fixed-parameter tractable algorithm
for 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.

## History

## Preferred citation

Funk, D., Mayhew, D. & Newman, M. (2019). Tree automata and pigeonhole classes of matroids -- II. http://arxiv.org/abs/1910.04361v3## Publication date

2019-10-10## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC