Teorema de Courcelle: Procurando papéis

Estou procurando um artigo fácil e introdutório sobre a prova do Teorema de Courcelle . Também estou interessado em sua conexão com a complexidade parametrizada em relação à largura da árvore .

Eu sou apenas um iniciante neste campo.

Alguma sugestão?

Há uma introdução suave no livro de Rolf Niedermeier, Invitation to Fixed Parameter Algorithms . Daniel Marx também tem alguns slides disponíveis em sua página inicial que contêm pequenos exemplos de modelagem de um problema no MSOL. Um conjunto de slides relevantes está aqui . Para mais links, consulte uma pergunta relacionada no CSTheory .

O Teorema de Courcelle é uma das coisas que é melhor explicada (em comparação com o livro de Niedermeier) no livro de Flum e Grohe (consulte o capítulo sobre largura de árvore), uma vez que problemas de verificação de modelo etc. são abordados em detalhes. Pelos mesmos autores e Frick, há também uma generalização do Teorema de Courcelle: avaliação de consultas por decomposição de árvores . Você também pode observar meta-teoremas semelhantes para largura de clique e profundidade de arbusto .

Também procure aqui uma breve visão geral de alguns dos documentos anteriores de Courcelle.