一句话：提出泛范畴框架，将多种语言的学习归约为代数自动机学习，并推广 Angluin 的 L* 算法。
论文提出一个通用的范畴论框架，用于学习各类未知形式语言，包括有限或无限词语言、加权语言与名义语言。框架以 monad T 为参数，刻画语言类型及其识别代数结构。作者引入 T-代数的自动机表示，把学习 T-可识别语言归约为学习一类抽象代数自动机，其迁移由函子建模。针对重要的伴随自动机情形，设计了推广 Angluin L* 的学习算法，并用范畴扩展步描述算法；在专门的有限性概念下分析终止性与复杂度。该框架覆盖已有范畴化自动机学习未涉及的 ω-正则语言，并给出有序语言、带名字绑定的名义语言与代价函数等此前无已知学习算法的新结果。
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.
DOI 原文 ·
@inproceedings{paperbot5483,
title = {Automata Learning},
author = {Henning Urbat and Lutz Schröder},
booktitle = {LICS},
year = {2020},
doi = {10.1145/3373718.3394775}
}