Formal models for the computation of problems, say circuits, automata, Turing machines, can be naturally extended to compute word-to-word functions. But abstracting from the computation model, what does it mean to “lift” a language class to functions? In this talk, that question is addressed in a first step by developing a robust theory that incidentally revolves around the (topological) notion of continuity. In language-theoretic terms, a word-to-word function is V-continuous, for a class of languages V, if it preserves membership in V by inverse image. In a second step, the focus is put on transducers, i.e. automata with letter output. The natural problem at hand is then that of deciding whether a given transducer realizes a V-continuous function; this is shown decidable for some classical classes V (e.g. a periodic languages, group languages, piecewise-testable …).
If time allows, the correlation between the transducer structure (i.e. its transition monoid), and its computing a continuous function will be explored.
Joint work with Olivier Carton, Andreas Krebs, Michael Ludwig, Charles Paperman.
Level of technicality: Medium; basic knowledge of automata theory required.
Bio
After earning an engineering degree from Épita, Paris, and a M.Sc. in mathematical logic from Université Paris Diderot, Michaël went on to do his Ph.D. in Université de Montréal under the supervision of Pierre McKenzie and Alain Finkel. He then spent some years in Universität Tübingen, Germany, as a postdoctoral researcher under the supervision of Andreas Krebs. He is now a postdoctoral researcher in the verification lab at the University of Oxford.
Add comment