Decomposition width of matroids

AbstractHliněný [P. Hliněný, Branch-width, parse trees, and monadic second-order logic for matroids, J. Combin. Theory Ser. B 96 (2006), 325–351] showed that every matroid property expressible in the monadic second-order logic can be decided in linear time for matroids with bounded branch-width that are represented over finite fields. To be able to extend these algorithmic results to matroids not representable over finite fields, we introduce a new width parameter for matroids, the decomposition width, and show that every matroid property expressible in the monadic second-order logic can be computed in linear time for matroids given by a decomposition with bounded width. We also relate the decomposition width to matroid branch-width and discuss implications of our results with respect to known algorithms