Document Open Access Logo

Tree Automata as Algebras: Minimisation and Determinisation

Authors Gerco van Heerdt , Tobias Kappé , Jurriaan Rot, Matteo Sammartino , Alexandra Silva

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2019.6.pdf
  • Filesize: 0.56 MB
  • 22 pages

Document Identifiers

Author Details

Gerco van Heerdt
  • University College London, United Kingdom
Tobias Kappé
  • University College London, United Kingdom
Jurriaan Rot
  • University College London, United Kingdom
  • Radboud University, Nijmegen, The Netherlands
Matteo Sammartino
  • University College London, United Kingdom
Alexandra Silva
  • University College London, United Kingdom

Funding

This work was partially supported by the ERC Starting Grant ProFoundNet (grant code 679127), a Leverhulme Prize (PLP-2016-129) and a Marie Curie Fellowship (grant code 795119).

Cite AsGet BibTex

Gerco van Heerdt, Tobias Kappé, Jurriaan Rot, Matteo Sammartino, and Alexandra Silva. Tree Automata as Algebras: Minimisation and Determinisation. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CALCO.2019.6

Abstract

We study a categorical generalisation of tree automata, as algebras for a fixed endofunctor endowed with initial and final states. Under mild assumptions about the base category, we present a general minimisation algorithm for these automata. We then build upon and extend an existing generalisation of the Nerode equivalence to a categorical setting and relate it to the existence of minimal automata. Finally, we show that generalised types of side-effects, such as non-determinism, can be captured by this categorical framework, leading to a general determinisation procedure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • tree automata
  • algebras
  • minimisation
  • determinisation
  • Nerode equivalence

Metrics

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

References

  1. Parosh Aziz Abdulla, Johanna Högberg, and Lisa Kaati. Bisimulation Minimization of Tree Automata. Int. J. Found. Comput. Sci., 18(4):699-713, 2007. URL: https://doi.org/10.1142/S0129054107004929.
  2. Jiří Adámek. Free algebras and automata realizations in the language of categories. Commentationes Mathematicae Universitatis Carolinae, 15(4):589-602, 1974. URL: http://eudml.org/doc/16649.
  3. Jiří Adámek. Realization theory for automata in categories. J. Pure and Appl. Algebra, 9(2):281-296, 1977. URL: https://doi.org/10.1016/0022-4049(77)90071-8.
  4. Jiří Adámek, Filippo Bonchi, Mathias Hülsbusch, Barbara König, Stefan Milius, and Alexandra Silva. A Coalgebraic Perspective on Minimization and Determinization. In FoSSaCS, pages 58-73, 2012. URL: https://doi.org/10.1007/978-3-642-28729-9_4.
  5. Jiří Adámek, Horst Herrlich, and George Strecker. Abstract and concrete categories: The joy of cats, volume 17 of Reprints in Theory and Applications of Categories. TAC, 2006. Google Scholar
  6. Jiří Adámek and Vera Trnková. Automata and algebras in categories. Kluwer, 1989. Google Scholar
  7. Brian D.O. Anderson, Michael A. Arbib, and Ernest G. Manes. Foundations of system theory: finitary and infinitary conditions, volume 115 of Lecture Notes in Econ. and Math. Syst. Springer, 1976. Google Scholar
  8. Michael A. Arbib and Ernest G. Manes. Machines in a category: An expository introduction. SIAM review, 16(2):163-192, 1974. Google Scholar
  9. Michael A. Arbib and Ernest G. Manes. Adjoint machines, state-behavior machines, and duality. Journal of Pure and Applied Algebra, 6(3):313-344, 1975. Google Scholar
  10. Simone Barlocco, Clemens Kupke, and Jurriaan Rot. Coalgebra Learning via Duality. In FoSSaCS, pages 62-79, 2019. URL: https://doi.org/10.1007/978-3-030-17127-8_4.
  11. Alwin Blok. Interaction, observation and denotation. Master’s thesis, ILLC Amsterdam, 2012. Google Scholar
  12. Mikołaj Bojańczyk. Recognisable languages over monads. In DLT, pages 1-13. Springer, 2015. Google Scholar
  13. Mikolaj Bojańczyk, Bartek Klin, and Slawomir Lasota. Automata theory in nominal sets. Logical Methods in Computer Science, 10(3), 2014. URL: https://doi.org/10.2168/LMCS-10(3:4)2014.
  14. Filippo Bonchi, Daniela Petrisan, Damien Pous, and Jurriaan Rot. A general account of coinduction up-to. Acta Inf., 54(2):127-190, 2017. URL: https://doi.org/10.1007/s00236-016-0271-4.
  15. Filippo Bonchi and Damien Pous. Hacking nondeterminism with induction and coinduction. Commun. ACM, 58(2):87-95, 2015. URL: https://doi.org/10.1145/2713167.
  16. Francis Borceux. Handbook of Categorical Algebra, volume 1 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1994. URL: https://doi.org/10.1017/CBO9780511525858.
  17. Björn Borchardt and Heiko Vogler. Determinization of Finite State Weighted Tree Automata. Journal of Automata, Languages and Combinatorics, 8(3):417-463, 2003. Google Scholar
  18. Ulrich Dorsch, Stefan Milius, Lutz Schröder, and Thorsten Wißmann. Efficient Coalgebraic Partition Refinement. In CONCUR, pages 32:1-32:16, 2017. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2017.32.
  19. Frank Drewes and Johanna Högberg. Query learning of regular tree languages: How to avoid dead states. Theory of Computing Systems, 40(2):163-185, 2007. Google Scholar
  20. Marcelo P. Fiore. Discrete Generalised Polynomial Functors (Extended Abstract). In ICALP, pages 214-226, 2012. Google Scholar
  21. Murdoch James Gabbay and Aad Mathijssen. Nominal (Universal) Algebra: Equational Logic with Names and Binding. J. Log. Comput., 19(6):1455-1508, 2009. URL: https://doi.org/10.1093/logcom/exp033.
  22. Amaury Habrard and José Oncina. Learning Multiplicity Tree Automata. In ICGI, volume 4201 of Lecture Notes in Computer Science, pages 268-280. Springer, 2006. Google Scholar
  23. Ichiro Hasuo, Bart Jacobs, and Ana Sokolova. Generic Trace Semantics via Coinduction. Logical Methods in Computer Science, 3(4), 2007. URL: https://doi.org/10.2168/LMCS-3(4:11)2007.
  24. Claudio Hermida and Bart Jacobs. Structural Induction and Coinduction in a Fibrational Setting. Inf. Comput., 145(2):107-152, 1998. URL: https://doi.org/10.1006/inco.1998.2725.
  25. Johanna Högberg, Andreas Maletti, and Jonathan May. Backward and forward bisimulation minimization of tree automata. Theoretical Computer Science, 410(37):3539-3552, 2009. URL: https://doi.org/10.1016/j.tcs.2009.03.022.
  26. William M. Holcombe. Algebraic Automata Theory. Cambridge University Press, 1982. Google Scholar
  27. Tobias Kappé, Paul Brunet, Alexandra Silva, and Fabio Zanasi. Concurrent Kleene Algebra: Free Model and Completeness. In ESOP, pages 856-882, 2018. URL: https://doi.org/10.1007/978-3-319-89884-1_30.
  28. Gregory M. Kelly. A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. Bull. Austr. Math. Soc., 22(1):1–83, 1980. URL: https://doi.org/10.1017/S0004972700006353.
  29. Stefan Kiefer, Ines Marusic, and James Worrell. Minimisation of Multiplicity Tree Automata. Logical Methods in Computer Science, 13(1), 2017. Google Scholar
  30. Bartek Klin and Jurriaan Rot. Coalgebraic trace semantics via forgetful logics. Logical Methods in Computer Science, 12(4), 2016. URL: https://doi.org/10.2168/LMCS-12(4:10)2016.
  31. Anders Kock. Monads on symmetric monoidal closed categories. Arch. der Math., 21(1):1-10, 1970. URL: https://doi.org/10.1007/BF01220868.
  32. Barbara König and Sebastian Küpper. Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata. In Theory Comput. Syst., pages 311-325, 2014. URL: https://doi.org/10.1007/978-3-662-44602-7_24.
  33. Dexter Kozen. A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Inf. Comput., 110(2):366-390, 1994. URL: https://doi.org/10.1006/inco.1994.1037.
  34. Alexander Kurz and Daniela Petrisan. On universal algebra over nominal sets. Mathematical Structures in Computer Science, 20(2):285-318, 2010. URL: https://doi.org/10.1017/S0960129509990399.
  35. Stephen Lack and Jiří Rosickỳ. Notions of Lawvere theory. Appl. Categ. Struct., 19(1):363-391, 2011. Google Scholar
  36. Saunders Mac Lane. Categories for the working mathematician, volume 5. Springer, 2013. Google Scholar
  37. Michael R. Laurence and Georg Struth. Completeness Theorems for Bi-Kleene Algebras and Series-Parallel Rational Pomset Languages. In RAMiCS, pages 65-82, 2014. URL: https://doi.org/10.1007/978-3-319-06251-8_5.
  38. Kamal Lodaya and Pascal Weil. Series-parallel languages and the bounded-width property. Theoretical Computer Science, 237(1):347-380, 2000. URL: https://doi.org/10.1016/S0304-3975(00)00031-1.
  39. Philip S. Mulry. Lifting Theorems for Kleisli Categories. In MFPS, pages 304-319, 1993. URL: https://doi.org/10.1007/3-540-58027-1_15.
  40. Jean Éric Pin. Mathematical Foundations of Automata Theory. Version of March 13, 2019. Google Scholar
  41. Andrew M. Pitts. Nominal Sets: Names and Symmetry in Computer Science. Cambridge University Press, 2013. Google Scholar
  42. Damien Pous and Davide Sangiorgi. Advanced Topics in Bisimulation and Coinduction, chapter Enhancements of the coinductive proof method. Cambridge University Press, 2011. Google Scholar
  43. Jan J. M. M. Rutten. Automata and Coinduction (An Exercise in Coalgebra). In CONCUR, pages 194-218, 1998. URL: https://doi.org/10.1007/BFb0055624.
  44. Yasubumi Sakakibara. Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 76(2-3):223-242, 1990. Google Scholar
  45. Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. Generalizing determinization from automata to coalgebras. Logical Methods in Computer Science, 9(1), 2013. URL: https://doi.org/10.2168/LMCS-9(1:9)2013.
  46. Thorsten Wißmann, Stefan Milius, Shin-ya Katsumata, and Jérémy Dubut. A Coalgebraic View on Reachability. arXiv e-prints, January 2019. URL: http://arxiv.org/abs/1901.10717.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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