|
Reading Group Weighted Tree Automata in the winter term 2013/2014 (nur auf Englisch)This reading group serves the purpose of acquiring an understanding of the concept of weighted tree automata, weighted context-free tree grammar (CFTG), weighted tree transducers and related formalisms. Context-free tree grammars allow, i.a., the modelling of phenomena encountered when dealing with natural language. They are a generalization of context-free grammars to the realm of trees. In contrast to regular tree grammars, whose sentential forms are trees where further derivation may only take place at the frontier, context-free tree grammar also allow expansion of nonterminals within the tree. In our reading, we will consider algebraic as well as operational approaches to context-free tree languages. Weighted tree languages generalize the well-established notion of formal tree languages, i.e., sets of trees, to functions from the set of all trees into some weight structure, e.g., a semiring. Thus each tree is assigned a weight by the language. There are manifold ways to define such weighted tree languages, and we will get to know some approaches, as e.g. by automata, or by systems of equations. Finally, we will consider tree transducers, which allow the specification of tree transformations, i.e. mappings between trees, by means of a finite set of state-based rewrite rules. Our reading will comprise comparisons between different classes of such tree transformations, and we will get to know a number of generalizations, e.g., tree transducers with weights, or tree transducers which allow transformations that are, in a certain sense, context-free. During the course of the reading group, every participant is expected to read all the literature. After an introductory meeting, we will convene in fortnightly meetings to discuss the current article. Note: Due to the content and extent of the reading material, this is an advanced course! We require each participant to be literate (and interested) in automata theory and in (basic concepts from) abstract algebra. MeetingsNext meeting is in italics. Meetings take place, unless specified otherwise, in room INF/3027.
Literature
|
Kontakt
Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
Heiko Vogler Tel.: +49 (0) 351 463-38232 Fax: +49 (0) 351 463-37959 ![]() Bitte entschuldigen Sie – beim Einbinden der Informationen ist ein Fehler aufgetreten |