Lecture Notes in Computer Science, 2002, Volume 2484/2002, 759-763, DOI: 10.1007/3-540-45790-9_11

On Sufficient Conditions to Identify in the Limit Classes of Grammars from Polynomial Time and Data

Colin de la Higuera and Jose Oncina

View Related Documents

Abstract

Linearity and determinism seem to be two essential conditions for polynomial learning of grammars to be possible. We propose a general condition valid for certain subclasses of the linear grammars given which these classes can be polynomially identified in the limit from given data. This enables us to give new proofs of the identification of well known classes of grammars, and to propose a new (and larger) class of linear grammars for which polynomial identification is thus possible.

Keywords  Polynomial identification in the limit - linear grammars

Fulltext Preview

Image of the first page of the fulltext document