Trees, grids, and MSO decidability: From graphs to matroids

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr SEESE Detlef

Year of publication 2006
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1016/j.tcs.2005.10.006
Field Informatics
Keywords matroid; branch-width; MSO theory; decidability
Description We show that, for every finite field $\pf F$, the class of all $\pf F$-representable matroids of branch-width at most a constant~$t$ has a decidable MSO theory. In the other direction, we prove that every class of $\pf F$-representable matroids with a decidable MSO theory must have uniformly bounded branch-width.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info