D 2012

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

GAJARSKÝ, Jakub a Petr HLINĚNÝ

Základní údaje

Originální název

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

Autoři

GAJARSKÝ, Jakub (703 Slovensko, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

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

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Indie

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

Kód RIV

RIV/00216224:14330/12:00057865

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-47-7

ISSN

DOI

Klíčová slova anglicky

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

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 31. 3. 2013 13:22, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

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

Návaznosti

GAP202/11/0196, projekt VaV
Název: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Investor: Grantová agentura ČR, Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
MUNI/A/0758/2011, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0914/2009, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty