Tree Automata in the summer term 2010
Examinations are possible on September 20. Please fix a time with Mrs Achtruth.
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.
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).
Books on other topics will be added to this list on demand.
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.