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

• 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