LIPIcs.MFCS.2017.52.pdf
- Filesize: 0.58 MB
- 14 pages
Document
Automata in the Category of Glued Vector Spaces
Authors
-
Part of:
Volume:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-01
Cite As Get 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.
Subject Classification
Keywords
- hybrid set-vector automata
- automata minimization in a category
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jirí Adámek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Well-pointed coalgebras. Logical Methods in Computer Science, 9(3), 2013.
- 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.
- 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.
- 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.
- 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.
-
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.
-
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.
-
Thomas Colcombet and Daniela Petrişan. Automata minimization: a functorial approach. CALCO, 72:8:1-8:15, 2017.
- 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.
- 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.
-
Helle Hvid Hansen. Subsequential transducers: a coalgebraic perspective. Inf. Comput., 208(12):1368-1397, 2010.
- 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.
- 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.