Parameterized Complexity Of Representing Models Of MSO Formulas

O artigo estende o teorema de Courcelle, demonstrando que modelos de fórmulas MSO2 com variáveis livres podem ser representados por diagramas de decisão de tamanho linearmente parametrizado. Ele estabelece limites superiores lineares parametrizados para SDDs com base na treewidth e para OBDDs com base na pathwidth.