Trees, grids, and MSO decidability: From graphs to matroids
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Theoretical Computer Science |
| MU Faculty or unit | |
| 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: |