A Negative Result on Inductive Inference of Extended Pattern Languages
A Negative Result on Inductive Inference of Extended Pattern Languages
复制标题
扩展模式语言归纳推理的一个否定结果
DOI：
10.1007/3-540-36169-3_25
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Daniel A. Reidenbach
中科院分区：
文献类型：
--
作者：
Daniel A. Reidenbach
扩展模式语言类的可学习性问题被认为是形式语言归纳推理中最古老和最突出的公开问题之一。本文提供了一个适当的答案，提出了一个子类-终端自由扩展模式语言-这是不学习的限制。为了实现这个结果，我们将不得不限制终端符号的相应字母表正好是两个字母。此外，我们将重点关注模式语言的歧义对无终端扩展模式语言的归纳推理的影响。受形式语言理论启发的关于模式中的非确定性的传统观点被转化为满足归纳推理要求的方法。这些研究将导致一些有用的可学习性标准类终端自由扩展模式语言。
The question of learnability of the class of extended pattern languages is considered to be one of the eldest and outstanding open problems in inductive inference of formal languages. This paper provides an appropriate answer presenting a subclass - the terminal-free extended pattern languages - that is not learnable in the limit. In order to achieve this result we will have to limit the respective alphabet of terminal symbols to exactly two letters. In addition we will focus on the impact of ambiguity of pattern languages on inductive inference of terminal-free extended pattern languages. The conventional view on nondeterminism in patterns inspired by formal language theory is transformed into an approach that meets the requirements of inductive inference. These studies will lead to some useful learnability criteria for classes of terminal-free extended pattern languages.