Publication details

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

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