Trees, grids, and MSO decidability: From graphs to matroids

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Stromy, mříže a MSO rozhodnutelnost: Od grafů k matroidům
Autoři

HLINĚNÝ Petr SEESE Detlef

Rok publikování 2006
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://dx.doi.org/10.1016/j.tcs.2005.10.006
Obor Informatika
Klíčová slova matroid; branch-width; MSO theory; decidability
Popis Dokazujeme, že na každým konečným tělesem má třída všech reprezentovatelných matroidů omezené branch-width rozhodnutelnou MSO teorii. Naopak každá taková třída reprezentovatelných matroidů s rozhodnutelnou MSO teorií musí mít omezenou branch-width.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.