Theory and Applications of Tree Automata and Tree Transducers2015VT
|
|
Course plan
Lectures
10 lectures, 8 exercises, and 4 seminars.
Recommended for
PhD students with an interest in formal language theory and its practical applications.
The course was last given
The course has not been given before.
Goals
The course aims to give a solid introduction to the theory of tree automata, tree grammars, and tree transducers, as well as an overview of current applications of these models in various areas of computer science.
Prerequisites
A previous course on formal language theory.
Contents
Finite tree automata and recognizable tree languages. Regular tree grammars. Finite tree automata and monadic second-order logic. Finite tree transducers. Regular tree grammars with interpretations. Applications of tree automata and tree transducers.
Organization
The course consists of lectures, labs, and seminars. The lectures present the central theoretical concepts. The lab sessions deepen the understanding of the theory by focussing on relevant mathematical problems. The seminars introduce and discuss specialist topics and applications. The language of instruction will be English.
Literature
Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez,
Christof Löding, Sophie Tison, and Marc Tommasi. Tree Automata Techniques and
Applications. Available online at http://tata.gforge.inria.fr
Ferenc Gécseg and Magnus Steinby. Tree Languages. In Grzegorz Rozenberg and
Arto Salomaa, editors, *Handbook of Formal Languages*, volume 3, pages 1–68.
Springer, 1997.
Joost Engelfriet. Tree Automata and Tree Grammars. DAIMI FN-10, University of
Aarhus, Aarhus, Denmark, 1975. (Lecture notes; will be distributed to
participants.)
Research papers depending on the students' interests.
Lecturers
Marco Kuhlmann, one or more guest lecturers
Examiner
Marco Kuhlmann
Examination
Written report on the material presented in a chosen lecture. Active participation during the seminars. Written report on a self-chosen research paper. Peer review on other students' reports.
Credit
6 ECTS credits
Comments
A previous version of this course has been given at the 25th European Summer School in Logic, Language, and Information (ESSLLI), Düsseldorf, 2013.
Page responsible: Director of Graduate Studies