Other formats:
BibTeX
LaTeX
RIS
@article{589863,
author = {Hliněný, Petr},
article_location = {Amsterdam},
article_number = {3},
keywords = {matroid representation; branch-width;
monadic second-order logic; tree automaton;
fixed-parameter complexity},
language = {eng},
issn = {0095-8956},
journal = {Journal of Combinatorial Theory, Ser B},
title = {Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids},
url = {http://dx.doi.org/10.1016/j.jctb.2005.08.005},
volume = {96},
year = {2006}
}
TY - JOUR
ID - 589863
AU - Hliněný, Petr
PY - 2006
TI - Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids
JF - Journal of Combinatorial Theory, Ser B
VL - 96
IS - 3
SP - 325-351
EP - 325-351
PB - Elsevier B.V.
SN - 00958956
KW - matroid representation
KW - branch-width
KW - monadic second-order logic
KW - tree automaton
KW - fixed-parameter complexity
UR - http://dx.doi.org/10.1016/j.jctb.2005.08.005
N2 - 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.
ER -
HLINĚNÝ, Petr. Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids. \textit{Journal of Combinatorial Theory, Ser B}. Amsterdam: Elsevier B.V., 2006, vol.~96, No~3, p.~325-351. ISSN~0095-8956.
|
