Abstract

For powerful computational models, such as Turing machines, or polynomial time Turing machines, it does not make much of a difference if one considers string-to-Boolean functions (i.e. languages) or string-to-string functions. For finite-state models, such as finite automata, there is a difference, and hence the study of string-to-string functions computed by automata, also known as transducers, is its own field.

Early models of transducers where minor variations on automata. An example of such a model is a Mealy machine, which is a deterministic finite automaton that produces one output letter in each transition. In time, transducer models have grown in sophistication, and now they are powerful enough to resemble programming languages, with features such as loops or higher-order functions. At the same time, because they are “finite-state”, the halting problem remains decidable. An appealing part of transducer theory is that, similarly to the language case, the important transducer models have many equivalent characterisations, using automata, logics, algebra, etc.

In this talk, I would like to discuss such transducer models, with an emphasis on those which compute string-to-string functions of polynomial growth.