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

Warning

This publication doesn't include Faculty of Economics and Administration. 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:	Highly Parallel and Distributed Computing Systems