Další formáty:
BibTeX
LaTeX
RIS
@article{589864,
author = {Hliněný, Petr and Seese, Detlef},
article_location = {Amsterdam},
article_number = {3},
keywords = {matroid; branch-width; MSO theory; decidability},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {Trees, grids, and MSO decidability: From graphs to matroids},
url = {http://dx.doi.org/10.1016/j.tcs.2005.10.006},
volume = {351},
year = {2006}
}
TY - JOUR
ID - 589864
AU - Hliněný, Petr - Seese, Detlef
PY - 2006
TI - Trees, grids, and MSO decidability: From graphs to matroids
JF - Theoretical Computer Science
VL - 351
IS - 3
SP - 372-393
EP - 372-393
PB - Elsevier
SN - 03043975
KW - matroid
KW - branch-width
KW - MSO theory
KW - decidability
UR - http://dx.doi.org/10.1016/j.tcs.2005.10.006
N2 - 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.
ER -
HLINĚNÝ, Petr a Detlef SEESE. Trees, grids, and MSO decidability: From graphs to matroids. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, 2006, roč.~351, č.~3, s.~372-393. ISSN~0304-3975.
|
