Subsequential transducers combine (input) language recognition with transduction and thereby generalise classic deterministic automata as well as Mealy and Moore type state machines. These well known subclasses all have a natural coalgebraic characterisation, and the question arises whether their coalgebraic modelling can be extended to subsequential transducers and their underlying structures. In this paper, we show that although subsequential structures cannot generally be regarded as coalgebras, the subclass of normalised structures do form a subcategory of coalgebras. Moreover, normalised structures are reflective in the category of all subsequential structures, and a final normalised structure exists. The existence and properties of the minimal subsequential transducer can be derived from this result. We also show that for the class of subsequential structures in which all states are accepting, an alternative coalgebraic representation is obtained by taking differentials. This differential representation gives rise to a new method of deciding equivalence and computing minimal representations which does not involve normalisation. Both normalisation and taking differentials can be formalised as functors into reflective subcategories of coalgebras, and we can therefore see these constructions as coalgebraisation.
Additional Metadata
Keywords Subsequential transducer, word function, coalgebra, normalisation, differential
MSC Formal languages and automata (msc 68Q45), Algebraic theory of languages and automata (msc 68Q70)
THEME Software (theme 1)
Publisher Academic Press
Journal Information and Computation
Project Compositional Construction of Component Connectors
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/612.000.316 - Compositional Construction of Component Connectors
Citation
Hansen, H.H. (2010). Subsequential transducers: a coalgebraic perspective. Information and Computation, 208(12), 1368–1397.