论文标题
学习通用树自动机的分类框架
A Categorical Framework for Learning Generalised Tree Automata
论文作者
论文摘要
自动机学习是一种流行技术，用于自动从查询中构建自动机模型。为不同类型的自动机制定了算法的临时适应。小牛项目旨在使用类别理论统一这些，以简化正确性证明并指导新算法的设计。在本文中，我们扩展了小牛，以涵盖可能没有结构性呈现的代数结构的学习。此外，我们还提供了流行的L*算法的抽象版本的详细算法，该算法是Calf中缺少的。我们将抽象理论实例化为一大类的集合函数，通过该理论，我们首次从抽象框架中恢复了实用的树自动机学习算法，同时又获得了新的算法来学习商定的多发函数的代数。
Automata learning is a popular technique used to automatically construct an automaton model from queries. Much research went into devising ad hoc adaptations of algorithms for different types of automata. The CALF project seeks to unify these using category theory in order to ease correctness proofs and guide the design of new algorithms. In this paper, we extend CALF to cover learning of algebraic structures that may not have a coalgebraic presentation. Furthermore, we provide a detailed algorithmic account of an abstract version of the popular L* algorithm, which was missing from CALF. We instantiate the abstract theory to a large class of Set functors, by which we recover for the first time practical tree automata learning algorithms from an abstract framework and at the same time obtain new algorithms to learn algebras of quotiented polynomial functors.
