TUD Logo

TUD Home » ... » Teaching » Summer term 2013 » Weighted Tree Automata

Chair of Foundations of Programming

Weighted Tree Automata in the summer term 2013

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.

Last modified: 11th Jul 2013, 10.08 AM
Author: Dipl.-Inf. Toni Dietze

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

Sorry — there was an error in gathering the desired information