Faster Deciding MSO Properties of Trees of Fixed Height, and
Some Consequences

D 2012

Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

GAJARSKÝ, Jakub and Petr HLINĚNÝ

Basic information

Original name

Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

Authors

GAJARSKÝ, Jakub (703 Slovakia, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution)

Edition

2012. vyd. Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), p. 112-123, 12 pp. 2012

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

India

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

URL

RIV identification code

RIV/00216224:14330/12:00057865

Organization unit

Faculty of Informatics

ISBN

978-3-939897-47-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112

Keywords in English

MSO graph property; tree-with; tree-depth; shrub-depth

Abstract

V originále

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).

Links

GAP202/11/0196, research and development project

Name: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů

Investor: Czech Science Foundation, Well-structured combinatorial classes, width parameters, and design of efficient algorithms

MUNI/A/0758/2011, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

MUNI/A/0914/2009, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)

Investor: Masaryk University, Category A

Citovat

GAJARSKÝ, Jakub and Petr HLINĚNÝ. Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences. Online. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). 2012th ed. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2012, p. 112-123. ISBN 978-3-939897-47-7. Available from: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112.

@inproceedings{1075307,
   author = {Gajarský, Jakub and Hliněný, Petr},
   address = {Dagstuhl, Germany},
   booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112},
   edition = {2012},
   keywords = {MSO graph property; tree-with; tree-depth; shrub-depth},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-939897-47-7},
   pages = {112-123},
   publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS},
   title = {Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences},
   url = {http://www.fsttcs.org/},
   year = {2012}
}

TY  - JOUR
ID  - 1075307
AU  - Gajarský, Jakub - Hliněný, Petr
PY  - 2012
TI  - Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
PB  - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
CY  - Dagstuhl, Germany
SN  - 9783939897477
KW  - MSO graph property
KW  - tree-with
KW  - tree-depth
KW  - shrub-depth
UR  - http://www.fsttcs.org/
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Ý. Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences. Online. In \textit{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}. 2012th ed. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2012, p.~112-123. ISBN~978-3-939897-47-7. Available from: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112.

Detailed Information on Publication Record