Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00081185" target="_blank" >RIV/00216224:14330/15:00081185 - isvavai.cz</a>

Result on the web

<a href="http://arxiv.org/pdf/1204.5194" target="_blank" >http://arxiv.org/pdf/1204.5194</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.2168/LMCS-11(1:19)2015" target="_blank" >10.2168/LMCS-11(1:19)2015</a>

Result language

angličtina

Original language name

Kernelizing 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

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GA14-03501S" target="_blank" >GA14-03501S: Parameterized algorithms and kernelization in the context of discrete mathematics and logic</a><br>

Continuities

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

Publication year

2015

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Volume of the periodical

11

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

26

Pages from-to

1-26

UT code for WoS article

000353193000002

EID of the result in the Scopus database

—