Tree automata and their applications in computational linguistics

Hauptseminar for BSc and MSc students (Coli)
Seminar for BSc and MSc students (CS)
Sommersemester 2009
Alexander Koller

Fridays, 8:30 - 10:00; C7.2, room 2.11

Tree automata generalize the finite-state string automata, which are familiar to you from the Coli lecture "Mathematische Grundlagen II" or a similar introductory class on automata theory. Where string automata accept languages of strings by assigning states to string positions, tree automata accept languages of trees by assigning states to nodes of a tree. There are also tree transducers, which generalize string transducers in a similar way. All these automata have been studied thoroughly in theoretical computer science.

Recently, tree automata and transducers have popped up in various areas of computational linguistics. They have been used in parsing (parse charts are tree automata accepting the parse trees of a sentence), in the study of grammar formalisms, in efficient algorithms for dealing with semantic ambiguity, and in statistical machine translation. Some of these results are about improving our understanding of grammar formalisms; some are about new, clean models for machine translation or semantics; and some involve the development of new algorithms based on tree automata that make previously hard processing tasks much faster.

In this seminar, we will discuss the definition and formal properties of tree automata and transducers, and then talk about their recent applications to CL.