| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/12:00057865 |
| Název v původním jazyce | Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2012 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 2 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | D - Článek ve sborníku |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Výsledek hodnocený již v předchozím hodnocení, body se přebírají |
| Bodové ohodnocení | 8,000 |
| Faktor korekce | 77,6 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 6,205 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 100,0 % | 8,000 | 6,205 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 2 |
| Počet domácích tvůrců | 2 |
| Tvůrce | Gajarský Jakub (státní příslušnost: SK - Slovenská republika; A - domácí tvůrce; vedidk: 9663207) |
| Tvůrce | Hliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 7595646) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | 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). |
| Klíčová slova | MSO graph property; tree-with; tree-depth; shrub-depth |
| Rozsah stran | 112-123 |
| Název sborníku | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) |
| Forma vydání | E - Elektronická verze „online“ |
| ISSN | 1868-8969 |
| Počet stran výsledku | 12 |
| ISBN | 9783939897477 |
| Název nakladatele | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS |
| Místo vydání | Dagstuhl, Germany |
| Místo konání akce | India |
| Rok konání akce | 2012 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| DOI výsledku | 10.4230/LIPIcs.FSTTCS.2012.112 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2013 |
| Systémové označení dodávky dat | RIV13-GA0-14330___/02:2 |
| Specifikace | RIV/00216224:14330/12:00057865!RIV13-GA0-14330___ |
| Kontrolní kód | [559E353F541D] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno MŠMT v roce 2013 | Záznam s identifikačním kódem RIV/00216224:14330/12:00057865 v dodávce dat RIV13-MSM-14330___/02:2 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011-2013, GA0/GA) |
| S - Specifický výzkum na vysokých školách |