License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2021.24
URN: urn:nbn:de:0030-drops-153791
Go to the corresponding LIPIcs Volume Portal

Wißmann, Thorsten

Minimality Notions via Factorization Systems ((Co)algebraic pearls)

LIPIcs-CALCO-2021-24.pdf (0.8 MB)


For the minimization of state-based systems (i.e. the reduction of the number of states while retaining the system’s semantics), there are two obvious aspects: removing unnecessary states of the system and merging redundant states in the system. In the present article, we relate the two aspects on coalgebras by defining an abstract notion of minimality.
The abstract notion minimality and minimization live in a general category with a factorization system. We will find criteria on the category that ensure uniqueness, existence, and functoriality of the minimization aspects. The proofs of these results instantiate to those for reachability and observability minimization in the standard coalgebra literature. Finally, we will see how the two aspects of minimization interact and under which criteria they can be sequenced in any order, like in automata minimization.

BibTeX - Entry

  author =	{Wi{\ss}mann, Thorsten},
  title =	{{Minimality Notions via Factorization Systems}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{24:1--24:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-153791},
  doi =		{10.4230/LIPIcs.CALCO.2021.24},
  annote =	{Keywords: Coalgebra, Reachability, Observability, Minimization, Factorization System}

Keywords: Coalgebra, Reachability, Observability, Minimization, Factorization System
Collection: 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)
Issue Date: 2021
Date of publication: 08.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI