Coalgebraising Subsequential Transducers

H.H. Hansen

Research output: Contribution to JournalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)109-129
JournalElectronic Notes in Theoretical Computer Science
Volume203
DOIs
Publication statusPublished - 2008

Bibliographical note

Hansen:Subseq-CMCS08
Proceedings title: Proceedings of the 9th Workshop on Coalgebraic Methods in Computer Science (CMCS 2008)
Publisher: Elsevier
Editors: J. Adámek, C. Kupke

Fingerprint

Dive into the research topics of 'Coalgebraising Subsequential Transducers'. Together they form a unique fingerprint.

Cite this