Subsequential transducers: a coalgebraic perspective
Information and Computation , Volume 208 - Issue 12 p. 1368- 1397
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.
|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)|
|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|
Hansen, H.H. (2010). Subsequential transducers: a coalgebraic perspective. Information and Computation, 208(12), 1368–1397.