Other formats:
BibTeX
LaTeX
RIS
@article{1316739,
author = {Gajarský, Jakub and Hliněný, Petr},
article_location = {Německo},
article_number = {1},
doi = {http://dx.doi.org/10.2168/LMCS-11(1:19)2015},
keywords = {model-checking; MSO logic; kernelization},
language = {eng},
issn = {1860-5974},
journal = {Logical Methods in Computer Science},
title = {Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences},
url = {http://arxiv.org/pdf/1204.5194},
volume = {11},
year = {2015}
}
TY - JOUR
ID - 1316739
AU - Gajarský, Jakub - Hliněný, Petr
PY - 2015
TI - Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences
JF - Logical Methods in Computer Science
VL - 11
IS - 1
SP - 1-26
EP - 1-26
PB - Logical Methods in Computer Science e.V.
SN - 18605974
KW - model-checking
KW - MSO logic
KW - kernelization
UR - http://arxiv.org/pdf/1204.5194
L2 - http://arxiv.org/pdf/1204.5194
N2 - 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).
ER -
GAJARSKÝ, Jakub and Petr HLINĚNÝ. Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences. \textit{Logical Methods in Computer Science}. Německo: Logical Methods in Computer Science e.V., 2015, vol.~11, No~1, p.~1-26. ISSN~1860-5974. Available from: https://dx.doi.org/10.2168/LMCS-11(1:19)2015.
|
