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í: 2012
• Druh: Článek ve sborníku
• Konference: 29th International Symposium on Theoretical Aspects of Computer Science STACS2012
• Fakulta / Pracoviště MU: Fakulta informatiky
• 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