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.

Meetings

Next meeting is in italics. Meetings take place, unless specified otherwise, in room INF/3027.

No	Date	Topic
1	Oct 29, 08:00	IO & OI. I
2	Nov 19, 08:00	IO & OI. II
3	Dec 03, 08:00	Pushdown Tree Automata
4	Dec 19, 08:00	Pushdown Machines for the Macro Tree Transducer (pp. 251–302)

Literature

• Context Free Tree Grammars (CFTG)
  • J. Engelfriet and E. M. Schmidt. IO and OI. I. & II. Journal of Computer and System Sciences, 15(3):328 – 353, 1977; 16(1):67–99, 1978.
  • I. Guessarian. Pushdown tree automata. Mathematical systems theory, 16(1):237–263, 1983.
  • J. Engelfriet and H. Vogler. Pushdown machines for the macro tree transducer. Theoretical Computer Science, 42(0):251 – 368, 1986.
• Weighted Tree Automata/Grammars
  • A. Alexandrakis and S. Bozapalidis. Weighted grammars and Kleene’s theorem. Information Processing Letters, 24(1):1–4, 1987.
  • Z. Ésik and W. Kuich. Formal tree series. Journal of Automata, Languages and Combinatorics, 8(2):219–285, 2003.
  • S. Bozapalidis, Z. Fülöp and G. Rahonis. Equational weighted tree transformations. Acta Informatica, 49(1):29–52
• Weighted Tree Transducers
  • J. Engelfriet. Bottom-up and top-down tree transformations — a comparison. Mathematical systems theory, 9(2):198–231, 1975.
  • Z. Fülöp, A. Maletti, and H. Vogler. Weighted extended tree transducers. Fundamenta Informaticae, 111:163–202, 2011.
• Application in NLP: Tree Adjoining Grammars
  • S. Kepser and J. Rogers. The equivalence of tree adjoining grammars and monadic linear context-free tree grammars. Journal of Logic, Language and Information, 20(3):361–384, 2011.