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í 2014
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Computer and System Sciences
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1016/j.jcss.2013.07.005
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.