Informace o publikaci
Trees, grids, and MSO decidability: From graphs to matroids
| Název česky | Stromy, mříže a MSO rozhodnutelnost: Od grafů k matroidům |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| 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: |