Informace o publikaci

Lower Bounds on the Complexity of MSO_1 Model-Checking

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

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.

Další info