2017/04/19 by Gerco van Heerdt, van Heerdt, Gerco, Matteo Sammartino +3
Computer Science · #F.1.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #Network Packet Processing and Optimization #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1704.05676
openalex publication_date 2017/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Automata learning is a technique that has successfully been applied in verification, with the automaton type varying depending on the application domain. Adaptations of automata learning algorithms for increasingly complex types of automata have to be developed from scratch because there was no abstract theory offering guidelines. This makes it hard to devise such algorithms, and it obscures their correctness proofs. We introduce a simple category-theoretic formalism that provides an appropriately abstract foundation for studying automata learning. Furthermore, our framework establishes formal relations between algorithms for learning, testing, and minimization. We illustrate its generality with two examples: deterministic and weighted automata.