Lower Bounds on the Complexity of MSO_1 Model-Checking

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:	Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity