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? We propose to address that question in a first step, 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, we focus on transducers, i.e., automata with letter output. We study the problem of deciding whether a given transducer realizes a V-continuous function, for some classical classes V (e.g., aperiodic languages, group languages, piecewise-testable, …).

If time allows, we will also see when there exists a correlation between the transducer structure (i.e., its transition monoid), and its computing a continuous function.

Joint work with Olivier Carton, Andreas Krebs, Michael Ludwig, Charles Paperman.