A Coalgebraic Perspective on Minimization and Determinization

Conference contribution

Publication Details

Author(s): Adámek J, Bonchi F, Hülsbusch M, König B, Milius S, Silva A
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher: Springer-verlag
Publishing place: Berlin Heidelberg
Publication year: 2012
Title of series: Lecture Notes in Computer Science
Volume: 7213
Conference Proceedings Title: Foundations of Software Science and Computational Structures
Pages range: 58-73
ISBN: 978-3-642-28728-2
ISSN: 0302-9743


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. © 2012 Springer-Verlag Berlin Heidelberg.

FAU Authors / FAU Editors

Milius, Stefan apl. Prof. Dr.
Lehrstuhl für Informatik 8 (Theoretische Informatik)

External institutions with authors

École normale supérieure de Lyon (ENS)
Technische Universität Braunschweig
Universität Duisburg-Essen
University College London (UCL)

How to cite

Adámek, J., Bonchi, F., Hülsbusch, M., König, B., Milius, S., & Silva, A. (2012). A Coalgebraic Perspective on Minimization and Determinization. In Foundations of Software Science and Computational Structures (pp. 58-73). Tallin, Estonia, EE: Berlin Heidelberg: Springer-verlag.

Adámek, Jiří, et al. "A Coalgebraic Perspective on Minimization and Determinization." Proceedings of the 15th International Conference, FOSSACS 2012, Tallin, Estonia Berlin Heidelberg: Springer-verlag, 2012. 58-73.


Last updated on 2018-09-08 at 23:09