Informatik-Oberseminar: Synthesis of Transducers from Relations on Finite Words and Trees

Mittwoch, 19.12.2018, 10.00 Uhr

Ort: Gebäude E3, Seminarraum 9222, Ahornstr. 55

Referentin: Sarah Winter, M.Sc. (Informatik 7)


The synthesis problem asks, given a specification that relates possible inputs to allowed outputs, whether there is a program realizing the specification, and if so, construct one. Such a program is referred to as an implementation of the specification.

The field of automata theory offers a rich landscape of models for defining specifications and implementations over both words and trees. We consider synthesis of sequential transducers from automaton-definable specifications on finite words and trees.

In this talk, concerning specifications over words, we discuss synthesis of sequential word transducers from rational relations in which the allowed input/output behavior is specified by a given set of synchronizations. Concerning specifications over trees, we focus on synthesis of deterministic top-down tree transducers from tree-automatic specifications.


Es laden ein: die Dozentinnen und Dozenten der Informatik