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
—