DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2021.15

Learning Automata and Transducers: A Categorical Approach

Authors: Thomas Colcombet, Daniela Petrişan, and Riccardo Stabile

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{colcombet_et_al:LIPIcs.CSL.2021.15,
  author =	{Colcombet, Thomas and Petri\c{s}an, Daniela and Stabile, Riccardo},
  title =	{{Learning Automata and Transducers: A Categorical Approach}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.15},
  URN =		{urn:nbn:de:0030-drops-134498},
  doi =		{10.4230/LIPIcs.CSL.2021.15},
  annote =	{Keywords: Automata, transducer, learning, category}
}

Search Results

Documents authored by Stabile, Riccardo

Learning Automata and Transducers: A Categorical Approach

Abstract

Cite as

Thanks for your feedback!

Could not send message