Polynomial-time identification of very simple grammars from positive data
Polynomial-time identification of very simple grammars from positive data
复制标题
从正数据中多项式时间识别非常简单的语法
DOI：
10.1016/s0304-3975(02)00423-1
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
T. Yokomori
中科院分区：
文献类型：
--
作者：
T. Yokomori
本文讨论了简单确定文法的一个子类--非常简单文法，并研究了从正数据中识别极限中的子类的问题。非常简单语言的类形成了简单确定性语言的一个适当子类，并且不能与正则语言的类相比。这类语言也被称为上下文无关文法的左Szilard语言。在提供了一些非常简单的语言的属性，我们表明，类非常简单的语法是多项式时间识别的限制，从以下意义上的正数据。也就是说，我们证明了有效地存在一个算法，给定一个目标非常简单的文法G在字母表上，从正数据中确定一个非常简单的文法G等价于G，满足更新猜想的时间由O（m）限定的性质，并且该算法的预测错误总数由O（n）限定，其中n是G的大小，m= Max {N| Σ| +1、|Σ| 3}，N是所提供的所有正数据的总长度。
This paper concerns a subclass of simple deterministic grammars, called very simple grammars, and studies the problem of identifying the subclass in the limit from positive data. The class of very simple languages forms a proper subclass of simple deterministic languages and is incomparable to the class of regular languages. This class of languages is also known as the class of left Szilard languages of context-free grammars. After providing some properties of very simple languages, we show that the class of very simple grammars is polynomial-time identifiable in the limit from positive data in the following sense. That is, we show that there effectively exists an algorithm that, given a target very simple grammar G∗over alphabet Σ, identifies a very simple grammar G equivalent to G∗in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by O(m), and the total number of prediction errors made by the algorithm is bounded by O(n), where n is the size of G∗, m= Max {N|Σ|+1,|Σ|3} and N is the total length of all positive data provided.