Coalgebra encoding for efficient minimization

Deifel HP, Milius S, Wißmann T (2021)


Publication Type: Conference contribution

Publication year: 2021

Journal

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Book Volume: 195

Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs

Event location: Virtual AR

ISBN: 9783959771917

DOI: 10.4230/LIPIcs.FSCD.2021.28

Abstract

Recently, we have developed an efficient generic partition refinement algorithm, which computes behavioural equivalence on a state-based system given as an encoded coalgebra, and implemented it in the tool CoPaR. Here we extend this to a fully fledged minimization algorithm and tool by integrating two new aspects: (1) the computation of the transition structure on the minimized state set, and (2) the computation of the reachable part of the given system. In our generic coalgebraic setting these two aspects turn out to be surprisingly non-trivial requiring us to extend the previous theory. In particular, we identify a sufficient condition on encodings of coalgebras, and we show how to augment the existing interface, which encapsulates computations that are specific for the coalgebraic type functor, to make the above extensions possible. Both extensions have linear run time.

Authors with CRIS profile

Related research project(s)

Involved external institutions

How to cite

APA:

Deifel, H.-P., Milius, S., & Wißmann, T. (2021). Coalgebra encoding for efficient minimization. In Naoki Kobayashi (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Virtual, AR: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Deifel, Hans-Peter, Stefan Milius, and Thorsten Wißmann. "Coalgebra encoding for efficient minimization." Proceedings of the 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021, Virtual Ed. Naoki Kobayashi, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.

BibTeX: Download