p 2006

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

HLINĚNÝ, Petr

Základní údaje

Originální název

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

Název česky

O rozhodnutelnosti MSO teorií kombinatorických struktur: Obecné matroidy?

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant)

Vydání

Logic and Combinatorics (organized by Bruno Courcelle), Workshop at CSL'06, 2006

Další údaje

Jazyk

angličtina

Typ výsledku

Vyžádané přednášky

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Maďarsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Kód RIV

RIV/00216224:14330/06:00024640

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

MSO logic; matroid; MSO decidability; branch-width

Štítky

Příznaky

Mezinárodní význam
Změněno: 27. 6. 2008 12:38, Ing. Dana Komárková

Anotace

ORIG CZ

V originále

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 resembles ordinary graphs as incidence structures. The monadic second-order theory of all matroids over a finite field of bounded branch-width is decidable [H]. Conversely, the decidability of monadic second-order theory of a class of matroids over a finite field implies a bound on the branch-widths of the matroids in this class [HS]. 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 [HS] : What could be a "good" width measure for general matroids ?

Česky

Studujeme problém rozhodnutelnosti MSO teorií v kombinatorice se speciálním zřetelem na matroidy.

Návaznosti

GA201/05/0050, projekt VaV
Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů