2006
Trees, grids, and MSO decidability: From graphs to matroids
HLINĚNÝ, Petr a Detlef SEESEZákladní údaje
Originální název
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
HLINĚNÝ, Petr (203 Česká republika, garant) a Detlef SEESE (276 Německo)
Vydání
Theoretical Computer Science, Amsterdam, Elsevier, 2006, 0304-3975
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.843
Kód RIV
RIV/00216224:14330/06:00015570
Organizační jednotka
Fakulta informatiky
UT WoS
000235646800008
Klíčová slova anglicky
matroid; branch-width; MSO theory; decidability
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 16. 11. 2006 11:49, prof. RNDr. Petr Hliněný, Ph.D.
V originále
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.
Česky
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.
Návaznosti
| GA201/05/0050, projekt VaV |
| ||
| MSM0021622419, záměr |
|