Tree automata and pigeonhole classes of matroids. I
From MaRDI portal
Publication:2149094
Abstract: Hlineny's Theorem shows that any sentence in the monadic second-order logic of matroids can be tested in polynomial time, when the input is limited to a class of F-representable matroids with bounded branch-width (where F is a finite field). If each matroid in a class can be decomposed by a subcubic tree in such a way that only a bounded amount of information flows across displayed separations, then the class has bounded decomposition-width. We introduce the pigeonhole property for classes of matroids: if every subclass with bounded branch-width also has bounded decomposition-width, then the class is pigeonhole. An efficiently pigeonhole class has a stronger property, involving an efficiently-computable equivalence relation on subsets of the ground set. We show that Hlineny's Theorem extends to any efficiently pigeonhole class. In a sequel paper, we use these ideas to extend Hlineny's Theorem to the classes of fundamental transversal matroids, lattice path matroids, bicircular matroids, and H-gain-graphic matroids, where H is any finite group. We also give a characterisation of the families of hypergraphs that can be described via tree automata: a family is defined by a tree automaton if and only if it has bounded decomposition-width. Furthermore, we show that if a class of matroids has the pigeonhole property, and can be defined in monadic second-order logic, then any subclass with bounded branch-width has a decidable monadic second-order theory.
Recommendations
Cites work
- scientific article; zbMATH DE number 863480 (Why is no real title available?)
- scientific article; zbMATH DE number 7354705 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- Approximating clique-width and branch-width
- Automata Studies. (AM-34)
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Characterizations of transversal and fundamental transversal matroids
- Decomposition width of matroids
- Defining Bicircular Matroids in Monadic Logic
- Elements of finite model theory.
- Enumeration of the monomials of a polynomial and related complexity classes
- Fundamentals of parameterized complexity
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Lattice path matroids: the excluded minors
- Mathematical Foundations of Computer Science 2003
- Monadic second-order model-checking on decomposable matroids
- On the excluded minors for the matroids of branch-width \(k\)
- Solving Rota's conjecture
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The structure of the models of decidable monadic theories of graphs
- Trees, grids, and MSO decidability: from graphs to matroids
- When does a biased graph come from a group labelling?
- Yes, the ``missing axiom of matroid theory is lost forever
Cited in
(3)
This page was built for publication: Tree automata and pigeonhole classes of matroids. I
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149094)
