On matroid properties definable in the MSO logic
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On matroid properties definable in the MSO logic
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2003
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Math Foundations of Computer Science MFCS 2003, Lecture Notes in Computer Science 2747
ISBN
—
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
470-479
Publisher name
Springer-Verlag Berlin Heidelberg
Place of publication
Berlin Heidelberg
Event location
Berlin
Event date
Jan 1, 2003
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—