Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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

Identifikátory výsledku

  • Kód výsledku v 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>

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • 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 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?

  • 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 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?

Klasifikace

  • Druh

    W - Uspořádání workshopu

  • CEP obor

    IN - Informatika

  • OECD FORD obor

Návaznosti výsledku

  • 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)

Ostatní

  • 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ů

Údaje specifické pro druh výsledku

  • Místo konání akce

    Szeged, Hungary

  • Stát konání akce

    MG - Madagaskarská republika

  • Datum zahájení akce

  • Datum ukončení akce

  • Celkový počet účastníků

    22

  • Počet zahraničních účastníků

    21

  • Typ akce podle státní přísl. účastníků

    EUR - Evropská akce