Polynomial-time identification of very simple grammars from positive data

详细信息    查看全文

• 作者：Yokomori ; Takashi
• 关键词：Very simple grammars ; Identification in the limit from positive data ; Polynomial-time learning
• 刊名：Theoretical Computer Science
• 出版年：2003
• 出版时间：April 4, 2003
• 年：2003
• 卷：298
• 期：1
• 页码：179-206
• 全文大小：288 K

文摘

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.