Parallel learning of automatic classes of languages (Q329605)

This article explores a new model of learning regular languages (and subclasses) from text. In the new model, called parallel learning, the learner is provided with text streams from several pairwise different languages from a class and is supposed to identify at least a certain number of them exactly. The text streams are simply sequences of words from the respective languages, so the learner is only provided with positive data (i.e., elements of the languages), the class under investigation, and the guarantee that the languages to be learnt are all different. A minor variation, in which the learner additionally has to indicate which languages it believes to have learnt correctly, is also studied. In the ``finite learning'' setup the learner can indicate uncertainty, but eventually needs to output hypotheses for the languages in question, which it can then no longer revise. In this sense, its first guess is also final. In the ``learning in the limit'' setup, the learner can output and revise hypotheses, but the hypotheses need to stabilize and converge to the actual language in question in the limit. Finally, also the computational capacity of the learner is restricted to a finite automaton. In most cases, the authors obtain exact characterizations of the learnable classes. The characterizations rely on the classical notions (tell-tale sets, characteristic subsets, etc.) and the difference of the number of languages presented to the number of languages to be successfully learnt. The classical notions are typically sufficient to identify a language. For example, a finite subset~\(S\) of a language~\(L\) is characteristic (for~\(L\)) if within the considered class of languages no language but~\(L\) is a superset of~\(S\). Given that all languages have characteristic sets, the learner can wait and read the input streams until it has identified a superset of a characteristic set. At this point, by the definition of a characteristic set, it has identified the language to be learnt. Theorem~9 states that if the learner needs to identify at least \(m\)~out of~\(n\) languages, then at most \(m-n\)~languages of the class may not have a characteristic sample (subject to some size constraint on the class). Characterizations in the same spirit are provided for the considered learning setups. The paper is well written and easily understandable. No additional literature is necessary to appreciate the details of the article.