کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
423425 685222 2008 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Coalgebraising Subsequential Transducers
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Coalgebraising Subsequential Transducers
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 203, Issue 5, 12 June 2008, Pages 109-129