A New Approach for Active Automata Learning Based on Apartness
A New Approach for Active Automata Learning Based on Apartness
复制标题
基于分离性的主动自动机学习新方法
DOI：
10.1007/978-3-030-99524-9_12
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Thorsten Wißmann
中科院分区：
文献类型：
--
作者：
F. Vaandrager;Bharat Garhewal;J. Rot;Thorsten Wißmann
我们提出了 $L^{\#}$，一种新的、简单的主动自动机学习方法。 $L^{\#}$ 不像 $L^{\ast}$ 算法及其后代那样关注观察的等价性，而是采取了不同的视角：它试图建立分离性，这是不平等的一种建设性形式。 $L^{\#}$不需要观察表或判别树等辅助概念，而是直接在树形自动机上运行。 $L^{\#}$ 具有与现有最佳学习算法相同的渐近查询和符号复杂性，但我们表明可以自然地集成自适应区分序列，以在实践中提高 $L^{\#}$ 的性能。用 Rust 编写的原型实现实验表明，$L^{\#}$ 与现有算法相比具有竞争力。
We present $L^{\#}$, a new and simple approach to active automata learning. Instead of focusing on equivalence of observations, like the $L^{\ast}$ algorithm and its descendants, $L^{\#}$ takes a different perspective: it tries to establish apartness, a constructive form of inequality. $L^{\#}$ does not require auxiliary notions such as observation tables or discrimination trees, but operates directly on tree-shaped automata. $L^{\#}$ has the same asymptotic query and symbol complexities as the best existing learning algorithms, but we show that adaptive distinguishing sequences can be naturally integrated to boost the performance of $L^{\#}$ in practice. Experiments with a prototype implementation, written in Rust, suggest that $L^{\#}$ is competitive with existing algorithms.