Abstract
Subsequential transducers generalise both classic deterministic automata and Mealy/Moore type state machines by combining (input) language recognition with transduction. In this paper we show that normalisation and taking differentials of subsequential transducers and their underlying structures can be seen as coalgebraisation. More precisely, we show that the subclass of normalised subsequential structures is a category of coalgebras which is reflective in the category of coaccessible subsequential structures, and which has a final object. This object is then also final for coaccessible structures. The existence and properties of the minimal subsequential transducer realising a partial word function f can be derived from this result. We also show that subsequential structures in which all states are accepting, can be seen as coalgebras by taking differentials. The coalgebraic representation obtained in this way gives rise to an alternative method of deciding transducer equivalence. © 2008 Elsevier B.V. All rights reserved.
Original language | English |
---|---|
Pages (from-to) | 109-129 |
Journal | Electronic Notes in Theoretical Computer Science |
Volume | 203 |
DOIs | |
Publication status | Published - 2008 |
Bibliographical note
Hansen:Subseq-CMCS08Proceedings title: Proceedings of the 9th Workshop on Coalgebraic Methods in Computer Science (CMCS 2008)
Publisher: Elsevier
Editors: J. Adámek, C. Kupke