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.

Schedule

The first lecture will take place on Monday, October 14.
The first tutorial will take place on Wednesday, October 16.
The third tutorial has been moved to Friday, November 1, 16.40 in INF 3027.
The sixth tutorial has been moved to Friday, November 22, 16.40 in INF 3027 due to a official holiday on the original date.
The lecture on Monday, December 16 and the tutorial on Wednesday, December 18 will be exchanged.
There will be no lecture on Monday, February 3 and also no tutorial on Wednesday, February 5.

Literature

• Joost Engelfriet, 1975. Bottom-Up and Top-Down Tree Transformations — A Comparison. In: Mathematical systems theory.
• Joost Engelfriet, 1975. Tree Automata and Tree Grammars. In: Lecture Notes, DAIMI FN-10, University of Aarhus.
• Joost Engelfriet, 1977. Top-down tree transducers with regular look-ahead. In: Mathematical systems theory.
• Brenda S. Baker, 1979. Composition of top-down and bottom-up tree transductions. In: Information and Control.
• Joost Engelfriet, 1982. Three hierarchies of transducers. In: Mathematical systems theory.
• Ferenc Gécseg and Magnus Steinby, 1984. Tree Automata. Akadémiai Kiadó, Budapest.

Exercises

• Exercise sheet 1 (October 16)
• Exercise sheet 2, solution for 6b (October 23)
• Exercise sheet 3, updated (November 1)
• Exercise sheet 4 (November 6)
• Exercise sheet 5, updated (November 13)
• Exercise sheet 6 (November 22)
• Exercise sheet 7 (November 27)
• Exercise sheet 8, updated (December 4)
• Exercise sheet 9 (December 11)
• Exercise sheet 10, updated (December 16)
• Exercise sheet 11 (January 8)
• Exercise sheet 12 (January 15)
• Exercise sheet 13, updated (January 22)
• Please prepare questions for the last tutorial on Wednesday, January 29.