×

A coalgebraic perspective on minimization and determinization. (English) Zbl 1352.68171

Birkedal, Lars (ed.), Foundations of software science and computational structures. 15th international conference, FOSSACS 2012, held as part of the European joint conferences on theory and practice of software, ETAPS 2012, Tallinn, Estonia, March 24 – April 1, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-28728-2/pbk). Lecture Notes in Computer Science 7213, 58-73 (2012).
Summary: Coalgebra offers a unified theory of state based systems, including infinite streams, labelled transition systems and deterministic automata. In this paper, we use the coalgebraic view on systems to derive, in a uniform way, abstract procedures for checking behavioural equivalence in coalgebras, which perform (a combination of) minimization and determinization. First, we show that for coalgebras in categories equipped with factorization structures, there exists an abstract procedure for equivalence checking. Then, we consider coalgebras in categories without suitable factorization structures: under certain conditions, it is possible to apply the above procedure after transforming coalgebras with reflections. This transformation can be thought of as some kind of determinization. We will apply our theory to the following examples: conditional transition systems and (non-deterministic) automata.
For the entire collection see [Zbl 1238.68011].

MSC:

68Q70 Algebraic theory of languages and automata
18B20 Categories of machines, automata
68Q65 Abstract data types; algebraic specification
PDFBibTeX XMLCite
Full Text: DOI