On the Inference of Finite State Automata from Positive and Negative Data
On the Inference of Finite State Automata from Positive and Negative Data
复制标题
论有限状态自动机从正负数据的推断
DOI：
10.1007/978-3-662-48395-4_4
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. García
中科院分区：
文献类型：
--
作者：
Damián López;P. García
Thrakhtenbrot-Barzdin和Gold的工作可以被认为是从给定数据识别有限自动机的第一个工作。他们结果的主要缺点是，他们可能得到的假设可能与提供的数据不一致。这一缺陷被RPNI和Lang算法解决了。除了这些工作外，其他工作也引入了关于训练数据的更有效的算法。这一改进的直接结果导致了错误率更低的算法。最近，一些工作已经取代了传统的DFA模型来解决NFA的识别问题。在这方面的研究中，剩余有限状态自动机(RFSA)的推理提供了一个典型的非确定性模型。其他的工作认为NFA组的推理是一种适合于解决有限自动机的语法推理的方法。我们回顾了利用目标语言中的正数据和负数据解决有限自动机推理的主要方法。在这篇综述中，我们将描述上述形式主义和归纳技术。
The works by Thrakhtenbrot–Barzdin and Gold can be considered to be the first works on the identification of Finite Automata from given data. The main drawback of their results is that they may obtain hypotheses that may be inconsistent with the provided data. This drawback was solved by theRPNIand Lang algorithms. Aside from these works, other works have introduced more efficient algorithms with respect to the training data. The direct consequence of this improvement has lead to algorithms that have lower error rates. Recently, some works have tackled the identification of NFAs instead of using the traditional DFA model. In this line of research, the inference of Residual Finite State Automata (RFSA) provides a canonical non-deterministic model. Other works consider the inference of teams of NFAs to be a method that is suitable to solve the grammatical inference of finite automata. We review the main approaches that solve the inference of finite automata by using positive and negative data from the target language. In this review, we will describe the above-mentioned formalisms and induction techniques.