Lower Bounds on the Complexity of MSO_1 Model-Checking

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Dolní meze složitosti MSO1 model checking
Autoři

GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan LANGER Alexander ROSSMANITH Peter SIKDAR Somnath

Rok publikování 2012
Druh Článek ve sborníku
Konference 29th International Symposium on Theoretical Aspects of Computer Science STACS2012
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www STACS2012
Doi http://dx.doi.org/10.4230/LIPIcs.STACS.2012.326
Obor Informatika
Klíčová slova Monadic Second-Order Logic; Treewidth; Lower Bounds; Exponential Time Hypothesis; Parameterized Complexity
Popis Rozšiřujeme výsledky Kreutzera a Tazariho o neřešitelnosti MSO2 logiky na třídách grafů s výrazně rostoucí tree-width na MSO1 logiku s barvami vrcholů.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.