Tree automata and pigeonhole classes of matroids. I

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

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.

Review text

The contribution translates the celebrated result of Courcelle, which shows that testing whether a graph of limited tree-width satisfies a given monadic second-order formula is efficient, to the realm of matroids, which are the algebraic structures used for correct greedy algorithms. More precisely, the theorem is adjusted for efficiently pigeonhole matroids. Roughly speaking, matroids are the algebraic structures that form the basis for the correctness of many greedy algorithms. The pigeonhole property of a class \(\mathcal{C}\) of matroids essentially requires that every subclass of \(\mathcal{C}\) that has bounded branch-width also has bounded decomposition-width. Efficiently pigeonhole additionally requires that a certain equivalence relation can efficiently be determined. With the help of the translation the contribution shows that for an efficiently pigeonhole class of matroids and a sentence in counting monadic second-order logic it can efficiently be tested whether a given matroid from the class fulfills the conditions expressed in the logic. The authors present full details on the tree automaton approach that is already used in the proof of Courcelle's theorem. All major basic constructions are presented and proved anew in their special setting, which benefits readers that are unfamiliar with tree automata theory. However, the main notions from matroid theory are glossed over rather quickly and it is essentially assumed that the reader is familiar with matroid theory. The relevant references are provided in all cases. Additional examples would have been welcome. Overall, the contribution is formally self-contained, but readers without a background in matroids will find it a difficult reading. Readers with some background in tree automata theory will be surprised to find many basic constructions (product, etc.) with full proof details.

Recommendations

Cites work

Cited in

(5)

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)