Automata Learning: An Algebraic Approach
Urbat H, Schröder L (2020)
Publication Language: English
Publication Type: Conference contribution, Original article
Publication year: 2020
Publisher: Association for Computing Machinery
City/Town: New York, NY
Pages Range: 900-914
Conference Proceedings Title: ACM International Conference Proceeding Series
Event location: Saarbrücken
ISBN: 9781450371049
URI: https://arxiv.org/abs/1911.00874
Abstract
We propose a generic categorical framework for learning unknown formal languages of various types (e.g. finite or infinite words, weighted and nominal languages). Our approach is parametric in a monad T that represents the given type of languages and their recognizing algebraic structures. Using the concept of an automata presentation of T-algebras, we demonstrate that the task of learning a T-recognizable language can be reduced to learning an abstract form of algebraic automaton whose transitions are modeled by a functor. For the important case of adjoint automata, we devise a learning algorithm generalizing Angluin's L∗. The algorithm is phrased in terms of categorically described extension steps; we provide for a termination and complexity analysis based on a dedicated notion of finiteness. Our framework applies to structures like ω-regular languages that were not within the scope of existing categorical accounts of automata learning. In addition, it yields new learning algorithms for several types of languages for which no such algorithms were previously known at all, including sorted languages, nominal languages with name binding, and cost functions.
Authors with CRIS profile
Henning Urbat
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Lutz Schröder
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Related research project(s)
How to cite
APA:
Urbat, H., & Schröder, L. (2020). Automata Learning: An Algebraic Approach. In ACM International Conference Proceeding Series (pp. 900-914). Saarbrücken, DE: New York, NY: Association for Computing Machinery.
MLA:
Urbat, Henning, and Lutz Schröder. "Automata Learning: An Algebraic Approach." Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020, Saarbrücken New York, NY: Association for Computing Machinery, 2020. 900-914.
BibTeX: Download