Document Open Access Logo

Learning Automata and Transducers: A Categorical Approach

Authors Thomas Colcombet , Daniela Petrişan , Riccardo Stabile

PDF
Thumbnail PDF

File

LIPIcs.CSL.2021.15.pdf
  • Filesize: 0.63 MB
  • 17 pages

Document Identifiers

Author Details

Thomas Colcombet
  • IRIF, CNRS, Paris, France
Daniela Petrişan
  • IRIF, Université de Paris, France
Riccardo Stabile
  • Università degli Studi di Milano, Dipartimento di Matematica, Italy

Funding

  • Colcombet, Thomas: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No.670624) and the DeLTA ANR project (ANR-16-CE40-0007).
  • Petrişan, Daniela: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No.670624) and the DeLTA ANR project (ANR-16-CE40-0007).
  • Stabile, Riccardo: Supported by the European Commission under the Erasmus+ programme for a five-month study period at Université de Paris.

Cite As Get BibTex

Thomas Colcombet, Daniela Petrişan, and Riccardo Stabile. Learning Automata and Transducers: A Categorical Approach. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CSL.2021.15

Abstract

In this paper, we present a categorical approach to learning automata over words, in the sense of the L*-algorithm of Angluin. This yields a new generic L*-like algorithm which can be instantiated for learning deterministic automata, automata weighted over fields, as well as subsequential transducers. The generic nature of our algorithm is obtained by adopting an approach in which automata are simply functors from a particular category representing words to a "computation category". We establish that the sufficient properties for yielding the existence of minimal automata (that were disclosed in a previous paper), in combination with some additional hypotheses relative to termination, ensure the correctness of our generic algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic language theory
  • Theory of computation → Transducers
Keywords
  • Automata
  • transducer
  • learning
  • category

Metrics

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

Related Versions

References

  1. Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75, 87-106, 1987. Google Scholar
  2. Dana Angluin, Sarah Eisenstat, and Dana Fisman. Learning regular languages via alternating automata. In IJCAI, pages 3308-3314. AAAI Press, 2015. Google Scholar
  3. Dana Angluin and Dana Fisman. Learning regular omega languages. Theor. Comput. Sci., 650:57-72, 2016. URL: https://doi.org/10.1016/j.tcs.2016.07.031.
  4. Simone Barlocco, Clemens Kupke, and Jurriaan Rot. Coalgebra learning via duality. In FoSSaCS, volume 11425 of Lecture Notes in Computer Science, pages 62-79. Springer, 2019. Google Scholar
  5. Francesco Bergadano and Stefano Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. In CIAC, volume 778 of Lecture Notes in Computer Science, pages 54-62. Springer, 1994. Google Scholar
  6. Francesco Bergadano and Stefano Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput., 25(6):1268-1280, 1996. Google Scholar
  7. Adrien Boiret, Aurélien Lemay, and Joachim Niehren. Learning rational functions. In Developments in Language Theory, volume 7410 of Lecture Notes in Computer Science, pages 273-283. Springer, 2012. Google Scholar
  8. Adrien Boiret, Aurélien Lemay, and Joachim Niehren. Learning top-down tree transducers with regular domain inspection. In ICGI, volume 57 of JMLR Workshop and Conference Proceedings, pages 54-65. JMLR.org, 2016. Google Scholar
  9. Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In IJCAI, pages 1004-1009, 2009. URL: http://ijcai.org/Proceedings/09/Papers/170.pdf.
  10. Benedikt Bollig, Joost-Pieter Katoen, Carsten Kern, Martin Leucker, Daniel Neider, and David R. Piegdon. libalf: The automata learning framework. In Tayssir Touili, Byron Cook, and Paul Jackson, editors, Computer Aided Verification, pages 360-364, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  11. 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
  12. Thomas Colcombet and Daniela Petrişan. Automata minimization: a functorial approach. In 7th Conference on Algebra and Coalgebra in Computer Science, CALCO 2017, June 12-16, 2017, Ljubljana, Slovenia, pages 8:1-8:16, 2017. URL: https://doi.org/10.4230/LIPIcs.CALCO.2017.8.
  13. Thomas Colcombet and Daniela Petrişan. Automata minimization: a functorial approach. Logical Methods in Computer Science, Volume 16, Issue 1, 2020. URL: https://lmcs.episciences.org/6213.
  14. Thomas Colcombet, Daniela Petrişan, and Riccardo Stabile. Learning automata and transducers: a categorical approach. CoRR, 2020. URL: http://arxiv.org/abs/2010.13675.
  15. Samuel Drews and Loris D'Antoni. Learning symbolic automata. In TACAS (1), volume 10205 of Lecture Notes in Computer Science, pages 173-189, 2017. Google Scholar
  16. Helle Hvid Hansen. Subsequential transducers: a coalgebraic perspective. Inf. Comput., 208(12):1368-1397, 2010. Google Scholar
  17. Bart Jacobs and Alexandra Silva. Automata learning: A categorical perspective. In Horizons of the Mind, volume 8464 of Lecture Notes in Computer Science, pages 384-406. Springer, 2014. Google Scholar
  18. Martin Leucker. Learning meets verification. In Frank S. de Boer, Marcello M. Bonsangue, Susanne Graf, and Willem-Paul de Roever, editors, Formal Methods for Components and Objects, pages 127-151, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  19. Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michal Szynwelski. Learning nominal automata. In POPL, pages 613-625. ACM, 2017. URL: http://dl.acm.org/citation.cfm?id=3009879.
  20. M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4(2):245-270, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80020-X.
  21. Henning Urbat and Lutz Schröder. Automata learning: An algebraic approach. In LICS, pages 900-914. ACM, 2020. Google Scholar
  22. Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. CALF: categorical automata learning framework. In CSL, volume 82 of LIPIcs, pages 29:1-29:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  23. Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. Learning automata with side-effects. In CMCS, 2020. Google Scholar
  24. Juan Miguel Vilar. Query learning of subsequential transducers. In Grammatical Inference: Learning Syntax from Sentences, 3rd International Colloquium, ICGI-96, Montpellier, France, September 25-27, 1996, Proceedings, pages 72-83, 1996. URL: https://doi.org/10.1007/BFb0033343.
  25. Juan Miguel Vilar. Improve the learning of subsequential transducers by using alignments and dictionaries. In Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI 2000, Lisbon, Portugal, September 11-13, 2000, Proceedings, pages 298-311, 2000. URL: https://doi.org/10.1007/978-3-540-45257-7_24.
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