Elsevier

Information and Computation

Volume 208, Issue 12, December 2010, Pages 1368-1397
Information and Computation

Subsequential transducers: a coalgebraic perspective

https://doi.org/10.1016/j.ic.2009.10.008Get rights and content
Under an Elsevier user license
open archive

Abstract

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

Cited by (0)

This paper is the extended journal version of the work first published in the CMCS 2008 conference as: “H.H. Hansen, Coalgebraising subsequential transducers, Proceedings of the Ninth Workshop on Coalgebraic Methods in Computer Science (CMCS 2008), ENTCS 203 (5) 2008, Pp 109-129, doi:10.1016/j.entcs.2008.05.022.

1

Partially supported by NWO grant 612.000.316.