TUD Logo

TUD Home » ... » Teaching » Winter term 2010/2011 » Weighted Tree Automata

Chair of Foundations of Programming

Weighted Tree Automata in the winter term 2010/11

Course description

In many areas of Computer Science trees are used to structure data and to represent hierarchical dependencies between parts of data; for instance, the structure of a sentence of a natural language is represented as a tree (parse tree). Hence, it is of general interest to provide algorithms and machines which decide whether trees have certain properties, rank trees by associating a weight with each of them, or transform trees into other trees. Taking up the natural language scenario, it is e.g. important to know the probability that a sentence is well-structured with respect to some grammatical rules, or what the possible translations of a sentence of one language into another language are.

Weighted tree automata are appropriate structures for such algorithms. In this lecture we will introduce their basic definitions and properties on a theoretical level, however keeping the application to natural language processing in mind.


The first lecture is going to be on October 11, at 11.10 am, in room E005.


Exercise sheets will be made available online approximately one week before the respective tutorial session. The exercises are to be prepared by the students and will be discussed in the tutorial.


Since the lecture covers concepts from algebra, formal language theory, tree automata theory, and machine translation, some of them being very recent, there is no single book which students might use to for their studies. Here is a list of books which might help in one area or the other. If not stated otherwise, they are available in the library (SLUB).

  • Zoltán Fülöp and Heiko Vogler. Weighted tree automata and tree transducers. In: Manfred Droste, Werner Kuich, Heiko Vogler (eds.), Handbook of Weighted Automata, Chapter 9, Springer, 2009.
  • Ferenc Gécseg and Magnus Steinby. Tree Languages. In: Handbook of Formal Languages, Vol. 3: Beyond Words (eds. G. Rozenberg and A. Salomaa), Springer 1997, 1–68.

Books on other topics will be added to this list on demand.


Mon 11.10 - 12.40 (3rd DS)
Tue 09.20 - 10.50 (2nd DS)
INF E005
Last modified: 20th Sep 2010, 11.30 AM
Author: Dr. rer. nat. Matthias Büchse

Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
Heiko Vogler

Phone: +49 (0) 351 463-38232
Fax: +49 (0) 351 463-37959
e-mail contact form