Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
Original language description
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).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F11%2F0196" target="_blank" >GAP202/11/0196: Well-structured combinatorial classes, width parameters, and design of efficient algorithms</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
ISBN
9783939897477
ISSN
1868-8969
e-ISSN
—
Number of pages
12
Pages from-to
112-123
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
Place of publication
Dagstuhl, Germany
Event location
India
Event date
Jan 1, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—