2026-08-10T22:02:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13449 2024-03-06T10:52:06Z ddc:004 open_access

Learning Automata and Transducers: A Categorical Approach Colcombet, Thomas Petrişan, Daniela Stabile, Riccardo Automata transducer learning category 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet and Daniela Petrişan and Riccardo Stabile 2021 Is Part Of LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2021.15 urn:nbn:de:0030-drops-134498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.15 eng https://creativecommons.org/licenses/by/3.0/legalcode