Courcelles Theorem: Auf der Suche nach Papieren

Ich suche ein einfaches und einführendes Papier zum Beweis von Courcelles Theorem . Ich interessiere mich auch für den Zusammenhang mit der parametrisierten Komplexität in Bezug auf die Baumbreite .

Ich bin nur ein Anfänger auf diesem Gebiet.

Irgendwelche Vorschläge?

Es gibt eine sanfte Einführung in Rolf Niedermeiers Buch Einladung zu Algorithmen mit festen Parametern . Daniel Marx hat auch einige Folien auf seiner Homepage verfügbar , die kurze Beispiele für die Modellierung eines Problems in MSOL enthalten. Ein Satz relevanter Folien ist hier . Weitere Links finden Sie in einer verwandten Frage zu CSTheory .

Der Satz von Courcelle ist eines der Dinge, die (im Vergleich zu Niedermeiers Buch) im Buch von Flum und Grohe (siehe Kapitel über die Breite) besser erklärt werden , da dort Probleme bei der Modellprüfung usw. ausführlich behandelt werden. Von denselben Autoren und Frick gibt es auch eine Verallgemeinerung von Courcelles Theorem: Abfragebewertung über Baumzerlegungen . Sie können sich auch ähnliche Metasätze für die Cliquenbreite und die Strauchtiefe ansehen .

Schauen Sie auch hier für einen kurzen Überblick über einige Courcelle früheren Papieren.