Branch-width, parse trees, and monadic second-order logic for matroids

We introduce "matroid parse trees" which, using only a limited amount of information, can build up all matroids of bounded branch-width representable over a finite field. We prove that if M is a family of matroids described by a sentence in the second-order monadic logic of matroids, then the parse trees of bounded-width representable members of M can be recognized by a finite tree automaton. Since the cycle matroids of graphs are representable over any finite field, our result directly extends the well-known "MS2-theorem" for graphs of bounded tree-width by Courcelle and others. This work has algorithmic applications in matroid or coding theories.