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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00024640" target="_blank" >RIV/00216224:14330/06:00024640 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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 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 fieldimplies 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

Název v anglickém jazyce

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

Popis výsledku anglicky

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 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 fieldimplies 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

Druh

O - Ostatní výsledky

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Strukturální vlastnosti a algoritmická složitost diskrétních problémů</a><br>

Návaznosti

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

Rok uplatnění

2006

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ů