J 2015

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

GAJARSKÝ, Jakub a Petr HLINĚNÝ

Základní údaje

Originální název

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

Autoři

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

Vydání

Logical Methods in Computer Science, Německo, Logical Methods in Computer Science e.V. 2015, 1860-5974

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.569

Kód RIV

RIV/00216224:14330/15:00081185

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000353193000002

Klíčová slova anglicky

model-checking; MSO logic; kernelization

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 28. 4. 2016 15:12, RNDr. Pavel Šmerk, 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

GA14-03501S, projekt VaV
Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
MUNI/A/1159/2014, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV.
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1206/2014, 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