Lower Bounds on the Complexity of MSO_1 Model-Checking (2014)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/14:00073428 |
|---|---|
| Název v anglickém jazyce | Lower Bounds on the Complexity of MSO_1 Model-Checking |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2014 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 2 |
| Počet tvůrců celkem | 6 |
| Počet domácích tvůrců | 3 |
| Výčet všech uvedených jednotlivých tvůrců | Robert Ganian (státní příslušnost: US - Spojené státy americké, domácí tvůrce: A, vedidk: 6376290) Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646) Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) Alexander Langer (státní příslušnost: DE - Spolková republika Německo) Peter Rossmanith (státní příslušnost: DE - Spolková republika Německo) Somnath Sikdar (státní příslušnost: IN - Indická republika) |
| Popis výsledku v anglickém jazyce | Kreutzer and Tazari proved in 2010 that MSO2 model-checking is not polynomial (XP) wrt. the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. We prove that MSO1 model-checking with a fixed set of vertex labels---i.e., without edge-set quantification---is not solvable even in quasi-polynomial time for fixed MSO-formulas in such graph classes. Both the lower bounds hold modulo a certain complexity-theoretic assumption, namely, theExponential Time Hypothesis (ETH) in the former case and the nonuniform ETH in the latter case. In comparison to Kreutzer and Tazari, we show a different set of problems to be intractable, and our stronger complexity assumption of nonuniform ETH slightlyweakens assumptions on the graph class and greatly simplifies important lengthy parts of the former proof. Our result also has an interesting consequence in the realm of digraph width measures. |
| Klíčová slova oddělená středníkem | Monadic Second-Order Logic; Treewidth; Lower Bounds; Exponential Time Hypothesis; Parameterized Complexity |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1016/j.jcss.2013.07.005 |
Údaje o výsledku v závislosti na druhu výsledku
| Název periodika | Journal of Computer and System Sciences |
|---|---|
| ISSN | 0022-0000 |
| Svazek periodika | 80 |
| Číslo periodika v rámci uvedeného svazku | 1 |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 15 |
| Strana od-do | 180-194 |
| Kód UT WoS článku podle Web of Science | 000325386500013 |
| EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2015 |
| Specifikace | RIV/00216224:14330/14:00073428!RIV15-MSM-14330___ |
| Datum poslední aktualizace výsledku | 29.05.2015 |
| Kontrolní číslo | 152392992 |
Informace o dalších výskytech výsledku dodaného stejným předkladatelem
| Dodáno GA ČR v roce 2015 | RIV/00216224:14330/14:00073428 v dodávce dat RIV15-GA0-14330___/01:1 |
|---|
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GA | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011 - 2013) |
|---|---|
| Podpora / návaznosti | Specifický výzkum na vysokých školách, poskytovatel MŠMT |