Lecture Notes in Computer Science, 2005, Volume 3734/2005, 283-296, DOI: 10.1007/11564089_23

Identification in the Limit of Substitutable Context-Free Languages

Alexander Clark and Rémi Eyraud

View Related Documents

Abstract

This paper formalisms the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free grammars. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin’s notion of reversibility for regular languages.

Fulltext Preview

Image of the first page of the fulltext document