论文标题
从积极和负面的示例中学习：二进制字母的新证明
Learning from Positive and Negative Examples: New Proof for Binary Alphabets
论文作者
论文摘要
计算学习理论中最根本的问题之一是学习有限的自动机$ a $与有限的积极示例$ p $一致的问题，并带有有限的负面示例$ n $。凭借一致性，我们的意思是$ a $接受$ p $的所有字符串，并拒绝$ n $中的所有字符串。众所周知，这个问题是NP完整的。在文献中，据说即使在二进制字母的情况下，这种NP硬度也能保持。作为该定理的标准参考，1978年的黄金工作要么被引用或改编。但是，作为一个至关重要的细节，黄金的工作实际上被视为Mealy机器，而不是如今被认为是确定性的有限状态自动机（DFA）。由于Mealy Automata配备了输出功能，因此它们可能比接受相同语言的DFA更紧凑。我们表明，文献中所述的Gold构造对Mealy机器的改编存在一些问题，并为DFA提供了新的二进制字母的新结构。
One of the most fundamental problems in computational learning theory is the the problem of learning a finite automaton $A$ consistent with a finite set $P$ of positive examples and with a finite set $N$ of negative examples. By consistency, we mean that $A$ accepts all strings in $P$ and rejects all strings in $N$. It is well known that this problem is NP-complete. In the literature, it is stated that this NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. But as a crucial detail, the work of Gold actually considered Mealy machines and not deterministic finite state automata (DFAs) as they are considered nowadays. As Mealy automata are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptions of Gold's construction for Mealy machines stated in the literature have some issues and give a new construction for DFAs with a binary alphabet ourselves.
