ABSTRACT:
Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices. In our main result, we derive the Chomsky-Schutzenberger Theorem for such quantitative context-free languages, showing that each arises as the image of a Dyck language and a recognizable language under a suitable morphism.

This is joint work with Manfred Droste (University of Leipzig)

BIOGRAPHY:
Prof. Dr.-Ing-habil. Heiko Vogler received the degree of Doktor in De Technische Wetenschappen at the Technische Hogeschool Twente, The Netherlands in 1986. He achieved the Habilitation in Computer Science at the RWTH Aachen in 1990, was associate professor at the University of Ulm from 1991-1994, and since 1994 he is full professor at the TU Dresden. He received the degree of Doktor honoris causa from the University of Szeged, Hungary in November 2013. His research interests are weighted tree automata and formal models for statistical machine translation of natural languages.