DROPS

Document

(Co)algebraic pearls

DOI: 10.4230/LIPIcs.CALCO.2023.20

Completeness for Categories of Generalized Automata ((Co)algebraic pearls)

Authors: Guido Boccali, Andrea Laretto, Fosco Loregian, and Stefano Luneia

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract

We present a slick proof of completeness and cocompleteness for categories of F-automata, where the span of maps E ←d E⊗ I s→ O that usually defines a deterministic automaton of input I and output O in a monoidal category (K,⊗) is replaced by a span E ← FE → O for a generic endofunctor F : K → K of a generic category K: these automata exist in their "Mealy" and "Moore" version and form categories F-Mly and F-Mre; such categories can be presented as strict 2-pullbacks in Cat and whenever F is a left adjoint, both F-Mly and F-Mre admit all limits and colimits that K admits. We mechanize our main results using the proof assistant Agda and the library https://github.com/agda/agda-categories.

Cite as

Guido Boccali, Andrea Laretto, Fosco Loregian, and Stefano Luneia. Completeness for Categories of Generalized Automata ((Co)algebraic pearls). In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boccali_et_al:LIPIcs.CALCO.2023.20,
  author =	{Boccali, Guido and Laretto, Andrea and Loregian, Fosco and Luneia, Stefano},
  title =	{{Completeness for Categories of Generalized Automata}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{20:1--20:14},
  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/entities/document/10.4230/LIPIcs.CALCO.2023.20},
  URN =		{urn:nbn:de:0030-drops-188174},
  doi =		{10.4230/LIPIcs.CALCO.2023.20},
  annote =	{Keywords: Deterministic automata, Moore machines, Mealy machines, coalgebras, cocomplete category}
}

Search Results

Documents authored by Luneia, Stefano

Completeness for Categories of Generalized Automata ((Co)algebraic pearls)

Abstract

Cite as

Thanks for your feedback!

Could not send message