TUD Logo

TUD Startseite » ... » Lehre » Sommersemester 2013 » Weighted Tree Automata

Grundlagen der Programmierung

Weighted Tree Automata im Sommersemester 2013 (nur auf Englisch)

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.


There will be no lecture on Monday, July 8!


Lecture – Room INF E005
Mon 11:10 - 12:40 (3rd DS)
Wed 13:00 - 14:30 (4th DS)
Tutorial – Room INF E005
Thu 07:30 - 09:00 (1st DS)


The slides about weighted recognizable tree languages Prof. Vogler mentioned can be downloaded here.

Dr. Mark-Jan Nederhof's lecture notes: part 1, part 2, part 3


The tutorial's time might not suffice for presenting all solutions. Please prepare yourself so you can ask for those solutions you are most interested in.

Lecture topics

The content matter covered in the various lessons can be viewed in the list of lecture topics.


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 and articles which might help in one area or the other. If not stated otherwise, they are available in the library (SLUB).

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

Stand: 11.7.2013, 10:08 Uhr
Autor: Dipl.-Inf. Toni Dietze

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

Tel.: +49 (0) 351 463-38232
Fax: +49 (0) 351 463-37959

Bitte entschuldigen Sie – beim Einbinden der Informationen ist ein Fehler aufgetreten