Gajarsky, Jakub ;
Hlineny, Petr
Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
Abstract
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 of 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 treedepth (MSO_2) and shrubdepth (MSO_1), 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 MSO_1 on the graph classes of bounded shrubdepth. This makes bounded shrubdepth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO_1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).
BibTeX  Entry
@InProceedings{gajarsky_et_al:LIPIcs:2012:3855,
author = {Jakub Gajarsky and Petr Hlineny},
title = {{Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {112123},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3855},
URN = {urn:nbn:de:0030drops38553},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112},
annote = {Keywords: MSO graph property, treewidth, treedepth, shrubdepth}
}
2012
Keywords: 

MSO graph property, treewidth, treedepth, shrubdepth 
Seminar: 

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

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 