News

The 11th tutorial will be a chance for discussion, repetition, and consultation.

No lecture on July 14! Instead, you are invited to visit the defence of Janis Voigtländer's habilitation. There will be a talk with discussion from 8 am till 9:45 and a probationary lecture from 10:15 till 11:00.

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. list of exercises (to be discussed on April 16, 2009)
2. list of exercises (to be discussed on April 23, 2009)
3. list of exercises (to be discussed on April 30, 2009)
4. list of exercises (to be discussed on May 7, 2009)
5. list of exercises (to be discussed on May 14, 2009)
6. list of exercises (to be discussed on May 26, 2009)
7. list of exercises (to be discussed on June 8, 2009)
8. list of exercises (to be discussed on June 18, 2009)
9. list of exercises (to be discussed on June 22, 2009)
10. list of exercises (to be discussed on July 2, 2009)

Downloads

• Bibliography (ps file). This is only for your reference; it is not a list of recommended literature.
• Additions to the bibliography (ps file) from 2009-05-15.
• A Tree-to-Tree Alignment-based Model for Statistical Machine Translation
• Two Languages are Better than One (for Syntactic Parsing)
• Maximum Likelihood from Incomplete Data via the EM Algorithm (Dempster, Laird, Rubin 1977)
• A Tutorial on the Expectation-Maximization Algorithm [...] (Prescher 2005)
• Training Tree Transducers (Graehl, Knight, May 2008)

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

• 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

This course will cover some problems and formal models relevant in the area of syntax-based machine translation of natural languages, such as parsing, tree transformations, and rule extraction. It fits into the module “Syntax-directed Semantics”.