A non-learnable class of E-pattern languages
A non-learnable class of E-pattern languages
复制标题
一类不可学习的 E 模式语言
DOI：
10.1016/j.tcs.2005.10.017
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Daniel A. Reidenbach
中科院分区：
文献类型：
--
作者：
Daniel A. Reidenbach
在Gold的学习模型中，我们研究了E-模式语言(也称为扩展或擦除模式语言)从正数据中的不可测性。主要结果是，如果相应的终端字母恰好由两个不同的字母组成，我们的分析对于整个E模式语言类-甚至对于无词尾的E模式语言的子类-都会产生否定的结果。此外，我们还给出了无终结点的E-模式语言的一个显式子类的一个正结果。我们指出，所考虑的问题与E-模式语言的不确定性的基本问题密切相关。
We investigate the inferrability of E-pattern languages (also known as extended or erasing pattern languages) from positive data in Gold's learning model. As the main result, our analysis yields a negative outcome for the full class of E-pattern languages—and even for the subclass of terminal-free E-pattern languages—if the corresponding terminal alphabet consists of exactly two distinct letters. Furthermore, we present a positive result for a manifest subclass of terminal-free E-pattern languages. We point out that the considered problems are closely related to fundamental questions concerning the nondeterminism of E-pattern languages.