Characterizing language identification by standardizing operations

摘要

Notions from formal language learning theory are characterized in terms of standardizing operations on classes of recursively enumerable languages. Algorithmic identification in the limit of grammars from text presentation of recursively enumerable languages is a central paradigm of language learning. A mapping, F, from the set of all grammars into the set of all grammars is a standardizing operation on a class of recursively enumerable languages ℳ just in case F maps any grammar for any language L ∈ ℳ to a canonical grammar for L. Investigating connections between these two notions is the subject of this paper.