论文标题
加权自动机是紧凑的，可以积极学习
Weighted automata are compact and actively learnable
论文作者
论文摘要
我们表明，在两个元素的字段上加权自动机可以比非确定性有限状态自动机更紧凑。为了证明这一点，我们结合了自动机理论和沟通复杂性的想法。但是，加权自动机在Angluin的最小教师模型中也可以有效地学习，其中许多查询中的许多疑问，这些查询在最小的加权自动机的大小中是多项式的。我们包括基于Angluin-Schapire Algorithm的线性代数通用的任何领域的学习算法。总之，这产生了一个令人惊讶的结果：在字段上的加权自动机的结构足够，即使它们非常紧凑，它们仍然可以有效地学习。
We show that weighted automata over the field of two elements can be exponentially more compact than non-deterministic finite state automata. To show this, we combine ideas from automata theory and communication complexity. However, weighted automata are also efficiently learnable in Angluin's minimal adequate teacher model in a number of queries that is polynomial in the size of the minimal weighted automaton.. We include an algorithm for learning WAs over any field based on a linear algebraic generalization of the Angluin-Schapire algorithm. Together, this produces a surprising result: weighted automata over fields are structured enough that even though they can be very compact, they are still efficiently learnable.
