Transducers, i.e., automata that output values other than just “yes” or “no”, are one of the oldest computational models in theoretical computer science. They even predate the usual automata, with Rabin and Scott arguing in their 1959 paper that they are better off by “doing away with a complicat-ed output function and having our machines simply give ‘yes’ or ‘no’ answers.” Despite this impres-sive pedigree, transducers have remained an active research topic ever since. Also, connections to practical applications in efficient processing of streaming data have been established recently. The purpose of this Dagstuhl Seminar is to gather researchers working on these topics to discuss recent developments.

We plan to discuss and advance on the following non-exhaustive list of topics during the seminar:

• regular and polyregular functions: the class of regular string-to-string functions has now gained a central position in the theory of transducers, as witnessed by many recent developments. The semi-nar will discuss those developments as well as classes of functions beyond regular functions, and in particular models of functions of polynomial growth, which have received a lot of attention in the last years.
• equivalence problems: transducer equivalence is one of the most central algorithmic problems in transducer theory. Algebraic techniques have been used recently to tackle this problem but important questions remain, such as whether or not the equivalence problem is decidable for polyregular functions.
• with finite model theory: the last decade has seen an explosion of new work on the theory of graph classes where first-order model checking is tractable (first-order model checking is not tractable on the class of all graphs). A recent trend in this work has been to use transducers, by considering images of simple graphs under certain transducers, or by considering classes that cannot yield all graphs by applying certain transducers.
• semantics: origin semantics means tagging the output by the positions of the input that generated that output. Origin semantics has shed new lights on algebraic characterizations of regu-lar functions and equivalence problems for transducers.
• membership problems: unlike deterministic finite automata, transducers are not robust under natural extensions such as non-determinism, bidirectionality, pebbles, … This induces classes of functions of various expressive power. Class membership problems, which ask to decide whether a function given as a transducer in some class belongs to some other class, have seen important de-velopments in the last few years.

Creative Commons BY 4.0

Rajeev Alur, Mikolaj Bojanczyk, Emmanuel Filiot, and Anca Muscholl