Portal de Periódicos da CAPES

Identification in the Limit of Substitutable Context-Free Languages

2005; Springer Science+Business Media; Linguagem: Inglês

10.1007/11564089_23

1611-3349

Alexander Clark, R. Eyraud,

Algorithms and Data Compression

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.