Teorema Courcelle: Mencari kertas

Saya mencari makalah yang mudah dan pengantar tentang bukti Teorema Courcelle . Saya juga tertarik dengan hubungannya dengan kompleksitas parameter tentang treewidth .

Saya hanya pemula di bidang ini.

Ada saran?

Ada pengantar lembut dalam buku Rolf Niedermeier, Invitation to Fixed Parameter Algorithms . Daniel Marx juga memiliki beberapa slide yang tersedia di beranda yang berisi contoh-contoh pendek pemodelan masalah di MSOL. Satu set slide yang relevan ada di sini . Untuk tautan lainnya, lihat pertanyaan terkait di CSTheory .

Teorema Courcelle adalah salah satu hal yang lebih baik dijelaskan (dibandingkan dengan buku Niedermeier) dalam buku Flum dan Grohe (lihat bab treewidth), karena masalah pengecekan model dll dibahas secara rinci di sana. Oleh penulis dan Frick yang sama ada juga generalisasi Teorema Courcelle: Evaluasi kueri melalui dekomposisi pohon . Anda mungkin juga melihat teorema meta yang serupa untuk lebar klik dan kedalaman semak .

Lihat juga di sini untuk ikhtisar singkat beberapa makalah Courcelle sebelumnya.