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”

Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00057865" target="_blank" >RIV/00216224:14330/12:00057865 - isvavai.cz</a>

  • Výsledek na webu

    <a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112" target="_blank" >10.4230/LIPIcs.FSTTCS.2012.112</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

  • Popis výsledku v původním jazyce

    We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of $m$. This yields a faster MSO model checking algorithm for trees od bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO2) and shrub-depth (MSO1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).

  • Název v anglickém jazyce

    Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

  • Popis výsledku anglicky

    We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of $m$. This yields a faster MSO model checking algorithm for trees od bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO2) and shrub-depth (MSO1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

    IN - Informatika

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/GAP202%2F11%2F0196" target="_blank" >GAP202/11/0196: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů</a><br>

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Ostatní

  • Rok uplatnění

    2012

  • 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

  • Název statě ve sborníku

    IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

  • ISBN

    9783939897477

  • ISSN

    1868-8969

  • e-ISSN

  • Počet stran výsledku

    12

  • Strana od-do

    112-123

  • Název nakladatele

    Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

  • Místo vydání

    Dagstuhl, Germany

  • Místo konání akce

    India

  • Datum konání akce

    1. 1. 2012

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku