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 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.

Další info