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.

News

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

Exercises

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.

Literature

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.

Schedule

Lecture

Mon 11.10 - 12.40 (3rd DS)

Tutorial

Tue 09.20 - 10.50 (2nd DS)

Room

INF E005