On matroid properties definable in the MSO logic

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F03%3A00008404" target="_blank" >RIV/61989100:27240/03:00008404 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
On matroid properties definable in the MSO logic
Popis výsledku v původním jazyce
It has been proved by the author that all matroid properties definable in the monadic second-order (MSO) logic can be recognized in polynomial time for matroids of bounded branch-width which are represented by matrices over finite fields. (This result extends so called ``$MS_2$-theorem'' of graphs by Courcelle and others.) In this work we review the MSO theory of finite matroids and show some interesting matroid properties which are MSO-definable. In particular, all minor-closed properties are recognizable in such way.
Název v anglickém jazyce
On matroid properties definable in the MSO logic
Popis výsledku anglicky
It has been proved by the author that all matroid properties definable in the monadic second-order (MSO) logic can be recognized in polynomial time for matroids of bounded branch-width which are represented by matrices over finite fields. (This result extends so called ``$MS_2$-theorem'' of graphs by Courcelle and others.) In this work we review the MSO theory of finite matroids and show some interesting matroid properties which are MSO-definable. In particular, all minor-closed properties are recognizable in such way.

Rok uplatnění
2003
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Math Foundations of Computer Science MFCS 2003, Lecture Notes in Computer Science 2747
ISBN
—
ISSN
—
e-ISSN
—
Počet stran výsledku
10
Strana od-do
470-479
Název nakladatele
Springer-Verlag Berlin Heidelberg
Místo vydání
Berlin Heidelberg
Místo konání akce
Berlin
Datum konání akce
1. 1. 2003
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)