Automata in the Category of Glued Vector Spaces

Authors Thomas Colcombet, Daniela Petrisan



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.52.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Colcombet
Daniela Petrisan

Cite AsGet BibTex

Thomas Colcombet and Daniela Petrisan. Automata in the Category of Glued Vector Spaces. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.52

Abstract

In this paper we adopt a category-theoretic approach to the conception of automata classes enjoying minimization by design. The main instantiation of our construction is a new class of automata that are hybrid between deterministic automata and automata weighted over a field.
Keywords
  • hybrid set-vector automata
  • automata minimization in a category

Metrics

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

References

  1. Jirí Adámek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Well-pointed coalgebras. Logical Methods in Computer Science, 9(3), 2013. Google Scholar
  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. URL: http://dx.doi.org/10.1007/978-3-642-28729-9_4.
  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. 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.
  5. Filippo Bonchi, Marcello Bonsangue, Michele Boreale, Jan Rutten, and Alexandra Silva. A coalgebraic perspective on linear weighted automata. Inf. Comput., 211:77-105, February 2012. URL: http://dx.doi.org/10.1016/j.ic.2011.12.002.
  6. 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
  7. 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
  8. Thomas Colcombet and Daniela Petrişan. Automata minimization: a functorial approach. CALCO, 72:8:1-8:15, 2017. Google Scholar
  9. Brian J. Day and Stephen Lack. Limits of small functors. Journal of Pure and Applied Algebra, 210(3):651 - 663, 2007. URL: http://dx.doi.org/10.1016/j.jpaa.2006.10.019.
  10. 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.
  11. Helle Hvid Hansen. Subsequential transducers: a coalgebraic perspective. Inf. Comput., 208(12):1368-1397, 2010. Google Scholar
  12. Sylvain Lombardy and Jacques Sakarovitch. Sequential? Theor. Comput. Sci., 356(1-2):224-244, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.01.028.
  13. M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4(2):245 - 270, 1961. URL: http://dx.doi.org/10.1016/S0019-9958(61)80020-X.
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