Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

A Coalgebraic Perspective on Minimization and Determinization

Adámek J, Bonchi F, Hülsbusch M, König B, Milius S, Silva A (2012)

---

Publication Type: Conference contribution

Publication year: 2012

Journal

Publisher: Springer-verlag

Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series: Lecture Notes in Computer Science

City/Town: Berlin Heidelberg

Book Volume: 7213

Pages Range: 58-73

Conference Proceedings Title: Foundations of Software Science and Computational Structures

Event location: Tallin, Estonia

ISBN: 978-3-642-28728-2

URI: http://link.springer.com/chapter/10.1007%2F978-3-642-28729-9_4

DOI: 10.1007/978-3-642-28729-9_4

Abstract

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.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

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.

MLA:

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.

BibTeX: Download