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.2023.11
URN: urn:nbn:de:0030-drops-188084
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18808/
Go to the corresponding LIPIcs Volume Portal

Zetzsche, Stefan ; Silva, Alexandra ; Sammartino, Matteo

Generators and Bases for Monadic Closures

pdf-format:
LIPIcs-CALCO-2023-11.pdf (0.8 MB)

Abstract

It is well-known that every regular language admits a unique minimal deterministic acceptor. Establishing an analogous result for non-deterministic acceptors is significantly more difficult, but nonetheless of great practical importance. To tackle this issue, a number of sub-classes of non-deterministic automata have been identified, all admitting canonical minimal representatives. In previous work, we have shown that such representatives can be recovered categorically in two steps. First, one constructs the minimal bialgebra accepting a given regular language, by closing the minimal coalgebra with additional algebraic structure over a monad. Second, one identifies canonical generators for the algebraic part of the bialgebra, to derive an equivalent coalgebra with side effects in a monad. In this paper, we further develop the general theory underlying these two steps. On the one hand, we show that deriving a minimal bialgebra from a minimal coalgebra can be realized by applying a monad on an appropriate category of subobjects. On the other hand, we explore the abstract theory of generators and bases for algebras over a monad.

BibTeX - Entry

@InProceedings{zetzsche_et_al:LIPIcs.CALCO.2023.11,
  author =	{Zetzsche, Stefan and Silva, Alexandra and Sammartino, Matteo},
  title =	{{Generators and Bases for Monadic Closures}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18808},
  URN =		{urn:nbn:de:0030-drops-188084},
  doi =		{10.4230/LIPIcs.CALCO.2023.11},
  annote =	{Keywords: Monads, Category Theory, Generators, Automata, Coalgebras, Bialgebras}
}

Keywords: Monads, Category Theory, Generators, Automata, Coalgebras, Bialgebras
Collection: 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)
Issue Date: 2023
Date of publication: 02.09.2023

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