Learning DFAs from Positive Examples Only via Word Counting
Benjamin Bordais, Daniel Neider
从积极的例子中学习有限自动机最近获得了关注,作为理解,解释,分析和验证黑盒系统的强大方法。 仅仅关注积极的例子的动机源于实际的限制,即我们只能观察一个系统能够做什么(积极的例子),而不是它不能做什么(消极的例子)。 与自20世纪70年代以来已知是NP完全的被动DFA学习的被动和消极例子的经典问题不同,仅从积极的例子中学习DFA的主题仍然知之甚少。 本文通过利用计算接受单词数的概念来介绍这个问题的新视角,以仔细确定的长度。 我们的贡献是双重的。 首先,我们证明计算接受所有正面示例的给定大小的DFA所接受的最小单词数是NP-complete,因此仅从正面示例中学习是计算要求很高的。 其次,我们提出了一种新的学习算法,具有更好的渐近运行时,这是现有算法中最著名的绑定。 虽然我们的实验评估表明,这种算法表现不佳,但它显示出作为增强现有方法的预处理步骤的巨大潜力。
Learning finite automata from positive examples has recently gained attention as a powerful approach for understanding, explaining, analyzing, and verifying black-box systems. The motivation for focusing solely on positive examples arises from the practical limitation that we can only observe what a system is capable of (positive examples) but not what it cannot do (negative examples). Unlike the classical problem of passive DFA learning with both positive and negative examples, which has been k...