|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. Keywords: matroid, branch-width, MSO logic, parametrized complexity.