News

Examinations are possible on September 20. Please fix a time with Mrs Achtruth.

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.

1. tutorial (April 15, 2010): please read Section 1 of the following paper.
   Adam Lopez, 2008. Statistical Machine Translation. ACM Computing Surveys, Volume 40, Number 3, Article 8
   download as pdf
2. tutorial (April 22, 2010): please solve as many exercises from the following exercise sheet as possible.
   download as pdf
3. tutorial (April 29, 2010): we will complete the excercise sheet from last time
4. tutorial (May 20, 2010): please solve as many exercises from the following exercise sheet as possible.
   download as pdf
5. tutorial (June 3, 2010): please solve as many exercises from the following exercise sheet as possible.
   download as pdf
6. tutorial (June 10, 2010): please solve as many exercises from the following exercise sheet as possible.
   download as pdf
7. tutorial (July 1, 2010): please solve as many exercises from the following exercise sheet as possible.
   download as pdf

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).

• 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.
• Ferenc Gécseg and Magnus Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.
• Wolfgang Wechler. Universal Algebra for Computer Scientists, Springer 1992.
• George Grätzer. Universal Algebra, Springer 2008.
• Udo Hebisch. Semirings: Algebraic theory and applications in computer science, World Scientific 1998.

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

Schedule

Lecture

Mon 11.10 - 12.40 (3rd DS)
Tue 11.10 - 12.40 (3rd DS)

Tutorial

Thu 11.10 - 12.40 (3rd DS)

Room

INF E005

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 or transform trees into other trees. Taking up the natural language scenario, it is e.g. important to know whether 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.

Tree automata and tree transducers are formal models for such algorithms and machines. In this lecture we will introduce their basic definitions and properties, keeping the application to natural language processing in mind.