A Logical Approach to Decomposable Matroids
Yann Strozecki · arXiv (Cornell University) · 2009
A notion of branch-width may be defined for matroids, which generalizes the one known for graphs. We first give a proof of the polynomial time model checking of MSOM on representable matroids of bounded branch-width, by reduction to MSO on trees, much simpler than the one previously known. We deduce results about spectrum of MSOM formulas and enumeration on matroids of bounded branch-width. We also provide a link between our logical approach and a grammar that allows to build matroids of bounded branch-width. Finally we introduce a new class of non-necessarily representable matroids described by a grammar, on which MSOM is decidable in linear time.