Abstract of Paper

On Matroid Properties Definable in the MSO Logic
by Petr Hlineny


It has been proved by the author that all matroid properties
definable in the monadic second-order (MSO) logic can be recognized in
polynomial time for matroids of bounded branch-width which are
represented by matrices over finite fields.
(This result extends so called "MS2-theorem" of graphs
by Courcelle and others.)
In this work we show some interesting matroid properties
which are MSO-definable.
In particular, all minor-closed properties are recognizable in such way.

matroid, branch-width, MSO logic, parametrized complexity.