Affordable Access

Access to the full text

Learning Automata and Transducers: A Categorical Approach

Authors
  • Colcombet, Thomas
  • Petri?an, Daniela
  • Stabile, Riccardo
Publication Date
Jan 01, 2021
Identifiers
DOI: 10.4230/LIPIcs.CSL.2021.15
OAI: oai:drops-oai.dagstuhl.de:13449
Source
Dagstuhl Research Online Publication Server
Keywords
Language
English
License
Green
External links

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.

Report this publication

Statistics

Seen <100 times