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.
|