Tree Automata
IMS, Wintersemester 2012/13 — LSF link
Vorlesung
| Übung
|
This class is an introduction to the theory of tree automata and their applications. Properties of recognizable tree languages as well as their relation to natural language parsing will be studied. The lecture (Vorlesung) will be supplemented by a tutorial (Übung) where the contents of the lecture will be recapitulated with weekly assignments and programming exercises.
The theory of tree automata and tree grammars has been studied since the 1960s. Tree automata and tree transducers have proved a useful tool in compiler construction, XML processing, verification and not least natural language processing.
The language of this class will be English. It is aimed at both BSc and MSc as well as Diploma students.
Modules (see also LSF)
| Modulnummer | Name des Moduls | Unitnummer | Unitname |
|---|---|---|---|
| 35160 | Concentration Computational Syntax und Semantics | 351601 | Vorlesung Grammar formalisms and grammar engineering |
| 35200 | Topics in Computational Syntax | 352004 | Course Advanced Computational Syntax |
| 41070 | Fortgeschrittene Methoden in der Maschinellen Sprachverarbeitung | 410701 | Vorlesung Fortgeschrittene Methoden in der Maschinellen Sprachverarbeitung |
| 35180 | Concentration Statistical Natural Language Processing | 351801 | Vorlesung Advanced Statistical Natural Language Processing |
| 351803 | Vorlesung Statistical constituent parsing | ||
| 351808 | Vorlesung Statistical NLP applications | ||
| 351809 | Vorlesung Probabilistic models of language and cognition |
Schedule
| Date | Vorlesung | Übung |
|---|---|---|
| October 15 | NO MEETING due to BSc/MSc introductory meeting | NO MEETING |
| October 22 | First meeting (slides will be made available in due time) | |
| October 29 | ||
| November 5 | ||
| November 12 | ||
| November 19 | ||
| November 26 | ||
| December 3 | ||
| December 10 | Berkeley parser hands-on | |
| December 17 | ||
| January 7 | ||
| January 14 | ||
| January 21 | ||
| January 28 | ||
| February 4 | ||
General reading
J. Engelfriet. 1975. Tree automata and tree grammars. Technical report. Available from the lecturers.
F. Gécseg and M. Steinby. 1997. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer. Available from the university library.
F. Gécseg and M. Steinby. 1984. Tree Automata. Akadémiai Kiadó, Budapest. Available from the university library.
H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. 2007. Tree Automata Techniques and Applications. Available on: http://www.grappa.univ-lille3.fr/tata.
Berkeley parser
- Sourcecode: http://code.google.com/p/berkeleyparser/
- Online demo: http://tomato.banatao.berkeley.edu:8080/parser/parser.html
Daniel Quernheim | © Universität Stuttgart | Legal notice