Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Combinatorial Theory, Ser B |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.jctb.2005.08.005 |
| Field | General mathematics |
| Keywords | matroid representation; branch-width; monadic second-order logic; tree automaton; fixed-parameter complexity |
| Description | We introduce ``matroid parse trees'' which, using only a limited amount of information at each node, can build up the vector representations of matroids of bounded branch-width over a finite field. We prove that if $\mf M$ is a family of matroids described by a sentence in the monadic second-order logic of matroids, then there is a finite tree automaton accepting exactly those parse trees which build vector representations of the bounded-branch-width representable members of $\mf M$. Since the cycle matroids of graphs are representable over any field, our result directly extends the so called ``$MS_2$-theorem'' for graphs of bounded tree-width by Courcelle, and others. Moreover, applications and relations in areas other than matroid theory can be found, like for rank-width of graphs, or in the coding theory. |
| Related projects: |