Open Access Te Herenga Waka-Victoria University of Wellington
Browse
Automata-II-arXiv.pdf (516.64 kB)

Tree automata and pigeonhole classes of matroids -- II

Download (516.64 kB)
journal contribution
posted on 2021-12-01, 19:46 authored by Daryl Funk, Dillon Mayhew, Mike Newman
Let $\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

    Journal articles

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC