Tree automata and pigeonhole classes of matroids. I (Q2149094)

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.