Document Open Access Logo

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

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.CALCO.2023.20.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata extensions
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Formalisms
Keywords
  • Deterministic automata
  • Moore machines
  • Mealy machines
  • coalgebras
  • cocomplete category

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.CALCO.2023.20

Author Details

Guido Boccali
  • University of Torino, Italy
Andrea Laretto
  • Tallinn University of Technology, Estonia
Fosco Loregian
  • Tallinn University of Technology, Estonia
Stefano Luneia
  • University of Bologna, Italy

Funding

  • Loregian, Fosco: The author was supported by the ESF funded Estonian IT Academy research measure (project 2014-2020.4.05.19-0001).

Acknowledgements

À René, parce qu'il faut ruser pour te lire.

Supplementary Materials

References

  1. J. Adámek and V. Trnková. Automata and Algebras in Categories. Kluwer, 1990. Google Scholar
  2. G. Boccali, A. Laretto, F. Loregian, and S. Luneia. Bicategories of automata, automata in bicategories, 2023. URL: https://arxiv.org/abs/2303.03865.
  3. F. Borceux. Handbook of categorical algebra. 2, volume 51 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1994. Categories and structures. Google Scholar
  4. M. Droste, W. Kuich, and H. Vogler, editors. Handbook of Weighted Automata. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-01492-5.
  5. H. Ehrig, K.-D. Kiermeier, H.-J. Kreowski, and W. Kühnel. Universal theory of automata. A categorical approach. XTeubner Studienbücher Informatik. Vieweg+Teubner Verlag Wiesbaden, 1974. URL: https://doi.org/10.1007/978-3-322-96644-5.
  6. J. W. Gray. Formal Category Theory: Adjointness for 2-Categories. Springer Berlin Heidelberg, 1974. URL: https://doi.org/10.1007/bfb0061280.
  7. R. Guitart. Tenseurs et machines. Cahiers de topologie et géométrie différentielle, 21(1):5-62, 1980. URL: http://www.numdam.org/item/CTGDC_1980__21_1_5_0/.
  8. B. Jacobs. A bialgebraic review of deterministic automata, regular expressions and languages. In Algebra, Meaning, and Computation, pages 375-404. Springer Berlin Heidelberg, 2006. Google Scholar
  9. B. Jacobs. Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2016. Google Scholar
  10. P. T. Johnstone. Topos theory., 1977. Google Scholar
  11. P. Katis, N. Sabadini, and R.F.C. Walters. Bicategories of processes. Journal of Pure and Applied Algebra, 115(2):141-178, February 1997. URL: https://doi.org/10.1016/s0022-4049(96)00012-6.
  12. Kenneth Krohn and John Rhodes. Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, 116(0):450-464, 1965. URL: https://doi.org/10.1090/s0002-9947-1965-0188316-1.
  13. F. W. Lawvere. Categories of spaces may not be generalized spaces as exemplified by directed graphs. Revista colombiana de matemáticas, 20(3-4):179-186, 1986. Google Scholar
  14. F. W. Lawvere. Axiomatic cohesion. Theory and Applications of Categories, 19:41-49, 2007. Google Scholar
  15. A. H. Louie. Categorical system theory. Bulletin of Mathematical Biology, 45(6):1047-1072, November 1983. URL: https://doi.org/10.1007/bf02458830.
  16. S. Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1998. URL: https://doi.org/10.1007/978-1-4757-4721-8.
  17. D. J. Myers. Double categories of open dynamical systems (extended abstract). Electronic Proceedings in Theoretical Computer Science, 333:154-167, February 2021. Google Scholar
  18. G. Naudé. On the adjoint situations between behaviour and realization. Quaestiones Mathematicae, 2:245-267, 1977. URL: https://doi.org/10.1080/16073606.1977.9632546.
  19. G. Naudé. Universal realization. Journal of Computer and System Sciences, 19(3):277-289, 1979. URL: https://doi.org/10.1016/0022-0000(79)90005-9.
  20. P. Schultz, D. I. Spivak, and C. Vasilakopoulou. Dynamical systems and sheaves. Applied Categorical Structures, 28(1):1-57, April 2019. URL: https://doi.org/10.1007/s10485-019-09565-x.
  21. David I. Spivak. Category Theory for the Sciences. The MIT Press, 2014. Google Scholar
  22. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser Boston, 1994. URL: https://doi.org/10.1007/978-1-4612-0289-9.
  23. Charles Wells. A krohn-rhodes theorem for categories. Journal of Algebra, 64(1):37-45, May 1980. URL: https://doi.org/10.1016/0021-8693(80)90130-1.
  24. R. J. Wood. Abstract pro arrows I. Cahiers de topologie et géométrie différentielle, 23(3):279-290, 1982. URL: http://www.numdam.org/item/CTGDC_1982__23_3_279_0/.
  25. R. J. Wood. Proarrows II. Cahiers de Topologie et Géométrie Différentielle Catégoriques, 26(2):135-168, 1985. URL: http://www.numdam.org/item/CTGDC_1985__26_2_135_0/.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact