Document Open Access Logo

Automata Minimization: a Functorial Approach

Authors Thomas Colcombet, Daniela Petrisan

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2017.8.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Thomas Colcombet
Daniela Petrisan

Cite As Get BibTex

Thomas Colcombet and Daniela Petrisan. Automata Minimization: a Functorial Approach. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CALCO.2017.8

Abstract

In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as
functors from input categories that specify the type of the
languages and of the machines to categories that specify the type of
outputs.

Our results are as follows: a) We provide sufficient conditions on the output category so that minimization of the corresponding automata is guaranteed. b) We show how to lift adjunctions between the categories for output values to adjunctions between categories of automata. c) We show how this framework can be applied to several phenomena in automata theory, starting with determinization and
minimization (previously studied from a coalgebraic and duality theoretic perspective). We apply in particular these techniques to
Choffrut's minimization algorithm for subsequential transducers and revisit Brzozowski's minimization algorithm.

Subject Classification

Keywords
  • functor automata
  • minimization
  • Choffrut's minimization algorithm
  • subsequential transducers
  • Brzozowski's minimization algorithm

Metrics

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

References

  1. Jiří Adámek and Věra Trnková. Automata and Algebras in Categories. 37. Springer Netherlands, New York, 1989. URL: http://www.springer.com/fr/book/9780792300106.
  2. Jiří Adámek, Filippo Bonchi, Mathias Hülsbusch, Barbara König, Stefan Milius, and Alexandra Silva. A coalgebraic perspective on minimization and determinization. In Proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS'12, pages 58-73, Berlin, Heidelberg, 2012. Springer-Verlag. Google Scholar
  3. 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. URL: http://dx.doi.org/10.1016/0022-4049(75)90028-6.
  4. E. S. Bainbridge. Adressed machines and duality. In Category Theory Applied to Computation and Control, volume 25 of Lecture Notes in Computer Science, pages 93-98. Springer, 1974. Google Scholar
  5. Adolfo Ballester-Bolinches, Enric Cosme-Llópez, and Jan J. M. M. Rutten. The dual equivalence of equations and coequations for automata. Inf. Comput., 244:49-75, 2015. Google Scholar
  6. Nick Bezhanishvili, Clemens Kupke, and Prakash Panangaden. Minimization via Duality, pages 191-205. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32621-9_14.
  7. Filippo Bonchi, Marcello M. Bonsangue, Helle Hvid Hansen, Prakash Panangaden, Jan J. M. M. Rutten, and Alexandra Silva. Algebra-coalgebra duality in Brzozowski’s minimization algorithm. ACM Trans. Comput. Log., 15(1):3:1-3:29, 2014. Google Scholar
  8. Filippo Bonchi, Marcello M. Bonsangue, Jan J. M. M. Rutten, and Alexandra Silva. Brzozowski’s algorithm (co)algebraically. In Logic and Program Semantics, volume 7230 of Lecture Notes in Computer Science, pages 12-23. Springer, 2012. Google Scholar
  9. C. Cassidy, M. Hébert, and G. M. Kelly. Reflective subcategories, localizations and factorizationa systems. Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 38(3):287–329, 1985. URL: http://dx.doi.org/10.1017/S1446788700023624.
  10. Christian Choffrut. A generalization of Ginsburg and Rose’s characterization of G-S-M mappings. In ICALP, volume 71 of Lecture Notes in Computer Science, pages 88-103. Springer, 1979. Google Scholar
  11. Christian Choffrut. Minimizing subsequential transducers: a survey. Theoretical Computer Science, 292(1):131 - 143, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(01)00219-5.
  12. Thomas Colcombet and Daniela Petrişan. Automata in glued vector spaces. submitted, 2017. Google Scholar
  13. Mai Gehrke, Daniela Petrisan, and Luca Reggio. The Schützenberger product for syntactic spaces. In ICALP, volume 55 of LIPIcs, pages 112:1-112:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  14. J. A. Goguen. Minimal realization of machines in closed categories. Bull. Amer. Math. Soc., 78(5):777-783, 09 1972. URL: http://projecteuclid.org/euclid.bams/1183533991.
  15. Helle Hvid Hansen. Subsequential transducers: a coalgebraic perspective. Inf. Comput., 208(12):1368-1397, 2010. Google Scholar
  16. Bart Jacobs and Jan Rutten. A tutorial on (co)algebras and (co)induction. EATCS Bulletin, 62:62-222, 1997. Google Scholar
  17. Bart Jacobs, Alexandra Silva, and Ana Sokolova. Trace semantics via determinization. Journal of Computer and System Sciences, 81(5):859 - 879, 2015. 11th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2012 (Selected Papers). URL: http://dx.doi.org/10.1016/j.jcss.2014.12.005.
  18. Henning Kerstan, Barbara König, and Bram Westerbaan. Lifting adjunctions to coalgebras to (re)discover automata constructions. In CMCS, volume 8446 of Lecture Notes in Computer Science, pages 168-188. Springer, 2014. Google Scholar
  19. 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. Google Scholar
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 About DROPS Imprint Privacy Contact