2006
Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids
HLINĚNÝ, PetrZákladní údaje
Originální název
Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids
Název česky
Branch-width, parsovací stromy a monadická logika druhého řádu pro matroidy
Autoři
Vydání
Journal of Combinatorial Theory, Ser B, Amsterdam, Elsevier B.V. 2006, 0095-8956
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.792
Kód RIV
RIV/00216224:14330/06:00015569
Organizační jednotka
Fakulta informatiky
UT WoS
000237476800002
Klíčová slova anglicky
matroid representation; branch-width;
monadic second-order logic; tree automaton;
fixed-parameter complexity
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 19. 12. 2006 13:22, prof. RNDr. Petr Hliněný, Ph.D.
V originále
We introduce ``matroid parse trees'' which, using only a limited amount of information at each node, can build up the vector representations of matroids of bounded branch-width over a finite field. We prove that if $\mf M$ is a family of matroids described by a sentence in the monadic second-order logic of matroids, then there is a finite tree automaton accepting exactly those parse trees which build vector representations of the bounded-branch-width representable members of $\mf M$. Since the cycle matroids of graphs are representable over any field, our result directly extends the so called ``$MS_2$-theorem'' for graphs of bounded tree-width by Courcelle, and others. Moreover, applications and relations in areas other than matroid theory can be found, like for rank-width of graphs, or in the coding theory.
Česky
Článek dokazuje obdobu tzv. MS2-věty pro matroidy reprezentované nad konečnými tělesy: Pro matroid reprezentovaný nad konečným tělesem s omezenou branch-width lze stromovými automaty rozhodnout všechny MSO definované vlastnosti.
Návaznosti
| GA201/05/0050, projekt VaV |
| ||
| MSM0021622419, záměr |
|