Estoy buscando un documento fácil e introductorio sobre la prueba del Teorema de Courcelle . También estoy interesado en su conexión con la complejidad parametrizada con respecto al ancho del árbol .
Solo soy un principiante en este campo.
¿Alguna sugerencia?
Hay una introducción suave en el libro Invitación a Algoritmos de Parámetros Fijos de Rolf Niedermeier . Daniel Marx también tiene bastantes diapositivas disponibles en su página de inicio que contienen ejemplos breves de modelado de un problema en MSOL. Un conjunto de diapositivas relevantes está aquí . Para obtener más enlaces, consulte una pregunta relacionada en CSTheory .
El teorema de Courcelle es una de las cosas que se explica mejor (en comparación con el libro de Niedermeier) en el libro de Flum y Grohe (vea el capítulo sobre el ancho del árbol), ya que los problemas de verificación de modelos, etc., están cubiertos en detalle allí. Por los mismos autores y Frick también hay una generalización del Teorema de Courcelle: Evaluación de consultas a través de descomposiciones de árboles . También puede mirar metateoremas similares para ancho de camarilla y profundidad de arbusto .
También busque aquí una breve descripción de algunos de los documentos anteriores de Courcelle.