A Logical Approach to Decomposable Matroids.

link: http://arxiv.org/abs/0908.4499
Abstract

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.