Hide menu

Theory and Applications of Tree Automata and Tree Transducers

2015VT

Status Cancelled
School National Graduate School in Computer Science (CUGS)
Division CILT
Owner Marco Kuhlmann

  Log in  




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