Subsequential Transducers and Coalgebra

Subsequential transducers are deterministic finite state machines which compute partial word functions f: A^ --> B^. They have applications in coding theory and language processing, and they generalise both deterministic finite automata (DFAs) and Mealy machines. It is known that DFAs and Mealy machines can be viewed as coalgebras such that the coalgebraic semantics coincides with the traditional automaton semantics.

In this talk we will see that subsequential transducers, in general, cannot be considered as coalgebras. Only if we restrict to certain subclasses do we obtain an adequate coalgebraic modelling. However, we will also see that the existing constructions of normalisation and differentials can be seen as a form of coalgebraisation, meaning that these transformations produce a representation which is essentially coalgebraic. This observation suggests that the (computationally) right way of looking at subsequential transducers is indeed the coalgebraic way.  

hosted by