On decidability of MSO theories of combinatorial structures: Towards general matroids?

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F06%3A00013589" target="_blank" >RIV/61989100:27240/06:00013589 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On decidability of MSO theories of combinatorial structures: Towards general matroids?

Original language description

We study the problem of decidability of MSO theories on various (restricted) matroid classes. When considering the matroids representable over a finite field (which is in structural sense similar to graphs embedded on a surface), the situation resemblesordinary graphs as incidence structures. The MSO theory of all matroids over a finite field of bounded branch-width is decidable [Hlineny 2003]. Conversely, decidability of matroid MSO theory (over a finite field) implies a universal bound on branch-width [Hlineny, Seese 2005]. The situation gets much more versatile and interesting when considering matroids in general (as "abstract", without a particular representation). We shall focus mainly on this part, and present some particular observations and results, and mainly open questions and directions for future research. This is related to another interesting question already raised by [Hlineny, Seese, 2006], what is a "good" width measure for general matroids?

Czech name

On decidability of MSO theories of combinatorial structures: Towards general matroids?

Czech description

We study the problem of decidability of MSO theories on various (restricted) matroid classes. When considering the matroids representable over a finite field (which is in structural sense similar to graphs embedded on a surface), the situation resemblesordinary graphs as incidence structures. The MSO theory of all matroids over a finite field of bounded branch-width is decidable [Hlineny 2003]. Conversely, decidability of matroid MSO theory (over a finite field) implies a universal bound on branch-width [Hlineny, Seese 2005]. The situation gets much more versatile and interesting when considering matroids in general (as "abstract", without a particular representation). We shall focus mainly on this part, and present some particular observations and results, and mainly open questions and directions for future research. This is related to another interesting question already raised by [Hlineny, Seese, 2006], what is a "good" width measure for general matroids?

Type

W - Workshop organization

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Structural properties and algorithmic complexity of discrete problems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2006

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Event location

Szeged, Hungary

Event country

MG - MADAGASCAR

Event starting date

—

Event ending date

—

Total number of attendees

22

Foreign attendee count

21

Type of event by attendee nationality

EUR - Evropská akce