| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/12:00057595 |
| Název v původním jazyce | Lower Bounds on the Complexity of MSO_1 Model-Checking |
| 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 | 66,7 % | 5,333 | 4,137 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 6 |
| Počet domácích tvůrců | 3 |
| Tvůrce | Ganian Robert (státní příslušnost: US - Spojené státy americké; A - domácí tvůrce; vedidk: 6376290) |
| Tvůrce | Hliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 7595646) |
| Tvůrce | Obdržálek Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 3294099) |
| Tvůrce | Langer Alexander (státní příslušnost: DE - Spolková republika Německo) |
| Tvůrce | Rossmanith Peter (státní příslušnost: DE - Spolková republika Německo) |
| Tvůrce | Sikdar Somnath (státní příslušnost: IN - Indická republika) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. |
| Klíčová slova | Monadic Second-Order Logic; Treewidth; Lower Bounds; Exponential Time Hypothesis; Parameterized Complexity |
| Název sborníku | 29th International Symposium on Theoretical Aspects of Computer Science STACS2012 |
| Rozsah stran | 326-337 |
| Forma vydání | E - Elektronická verze „online“ |
| ISSN | 1868-8969 |
| ISBN | 9783939897354 |
| Počet stran výsledku | 12 |
| Název nakladatele | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS |
| Místo vydání | Dagstuhl, Germany |
| Místo konání akce | Paris |
| Rok konání akce | 2012 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| Adresa www stránky s výsledkem | http://stacs2012.lip6.fr/ |
| DOI výsledku | 10.4230/LIPIcs.STACS.2012.326 |
| Ú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:00057595!RIV13-GA0-14330___ |
| Kontrolní kód | [800792753F08] |
| 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:00057595 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 |