
Reading Group Weighted Tree Automata in the winter term 2013/2014This reading group serves the purpose of acquiring an understanding of the concept of weighted tree automata, weighted contextfree tree grammar (CFTG), weighted tree transducers and related formalisms. Contextfree tree grammars allow, i.a., the modelling of phenomena encountered when dealing with natural language. They are a generalization of contextfree 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, contextfree tree grammar also allow expansion of nonterminals within the tree. In our reading, we will consider algebraic as well as operational approaches to contextfree tree languages. Weighted tree languages generalize the wellestablished 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 statebased 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, contextfree. 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

Contact
Prof. Dr.Ing. habil. Dr. h.c./Univ. Szeged
Heiko Vogler Phone: +49 (0) 351 46338232 Fax: +49 (0) 351 46337959 email contact form Sorry — there was an error in gathering the desired information 