Tree automata and pigeonhole classes of matroids. I

DOI10.1007/S00453-022-00939-7zbMATH Open1494.68136arXiv1910.04360OpenAlexW4214595959MaRDI QIDQ2149094FDOQ2149094

Dillon Mayhew, Daryl Funk, Mike Newman

Publication date: 28 June 2022

Published in: Algorithmica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1910.04360

zbMATH Keywords

monadic second-order logictree automatamatroid theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Elements of finite model theory.
• Branch-width, parse trees, and monadic second-order logic for matroids.
• On the excluded minors for the matroids of branch-width \(k\)
• Solving Rota's conjecture
• Lattice path matroids: the excluded minors
• Enumeration of the Monomials of a Polynomial and Related Complexity Classes
• The structure of the models of decidable monadic theories of graphs
• Automata Studies. (AM-34)
• Decomposition width of matroids
• Mathematical Foundations of Computer Science 2003
• Monadic second-order model-checking on decomposable matroids
• Title not available (Why is that?)
• Characterizations of transversal and fundamental transversal matroids
• When does a biased graph come from a group labelling?
• Trees, grids, and MSO decidability: from graphs to matroids
• Title not available (Why is that?)
• Yes, the “missing axiom” of matroid theory is lost forever
• Defining Bicircular Matroids in Monadic Logic

Cited In (2)

• Title not available (Why is that?)
• Tree automata and pigeonhole classes of matroids. II

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)