Characteristic sets for polynomial grammatical inference
Characteristic sets for polynomial grammatical inference
复制标题
DOI：
10.1023/a:1007353007695
复制
发表时间：
1997-05-01
期刊：
影响因子：
7.5
通讯作者：
DelaHiguera, C
中科院分区：
文献类型：
--
作者：
DelaHiguera, C
当关注有效的语法推理时，有两个问题是相关的：第一个是确定结果的质量，第二个是尝试使用多项式时间和空间。处理第一点的典型想法是，如果算法在极限内推断出正确的语言，则该算法表现良好。第二点引发了关于如何定义多项式时间的争论：多项式推理的主要定义是由 Pitt 和 Angluin 提出的。在本文中，我们回到 Gold 提出的定义，该定义要求每个语法都存在一组特征字符串，并且该集合是要学习的语法或自动机的大小的多项式，其中样本的大小是它包含的所有字符串的长度之和。一旦特征集包含在数据中，学习算法也必须正确推断。我们首先证明这个定义对应于戈德曼和马蒂亚斯定义的可教性概念。通过使他们的教师/学习者模型适应语法推理，我们证明了由上下文无关语法、简单确定性语法、线性语法和非确定性有限自动机给出的语言在多项式时间和数据的限制下是不可识别的。
When concerned about efficient grammatical inference two issues are relevant: the first one is to determine the quality of the result, and the second is to try to use polynomial time and space. A typical idea to deal with the first point is to say that an algorithm performs well if it infers in the limit the correct language. The second point has led to debate about how to define polynomial time: the main definitions of polynomial inference have been proposed by Pitt and Angluin. We return in this paper to a definition proposed by Gold that requires a characteristic set of strings to exist for each grammar, and this set to be polynomial in the size of the grammar or automaton that is to be learned, where the size of the sample is the sum of the lengths of all strings it includes. The learning algorithm must also infer correctly as soon as the characteristic set is included in the data. We first show that this definition corresponds to a notion of teachability as defined by Goldman and Mathias. By adapting their teacher/learner model to grammatical inference we prove that languages given by context-free grammars, simple deterministic grammars, linear grammars and nondeterministic finite automata are not identifiable in the limit from polynomial time and data.