Transducers, logic and algebra for functions of finite words
Emmanuel Filiot, Pierre-Alain Reynier · ACM SIGLOG News · 2016
The robust theory of regular languages is based on three important pillars: computation (automata), logic, and algebra. In this paper, we survey old and recent results on extensions of these pillars to functions from words to words. We consider two important classes of word functions, the rational and regular functions, respectively defined by one-way and two-way automata with output words, called transducers.