Tree-decompositions and Logic
Instructor:
Prof. Dr. Jörg Flum
Albert-Ludwigs-Universität Freiburg
Abteilung für mathematische Logik
Time:
Sep.4 - Sep. 7. (4 Talks)
9:30am - 10:30am
Place:
Dianxin Building
House III, Room 416
Minhang Campus
Contents:
(1) NP-complete problems restricted to trees.
(2) Tree-decompositions and tree-width.
(3) Dynamic programming on a tree-decomposition.
(4) Dynamic programming and automata on trees.
(5) Automata and monadic second-order logic.
(6) Courcelle's Theorem.
(7) Applications and extensions.
Downloadable Slides in Postsript
and PDF.
To view them, you need
GSview
or Acrobat Reader.
Back
Yijia Chen, last modified: 3. 9. 2006