Automatic learning from positive data and negative counterexamples (Q2013555)

The contribution discusses learnability in the limit of language classes from positive data and limited counterexamples. In their learning scenario the learner is presented with a stream of positive examples from the language that eventually presents every member of the language. At each step, the learner can return a hypothesis, which triggers a counterexample reply provided that the hypothesis contains an element that does not belong to the language to be learned. In this case the counterexample reply returns a member of the hypothesis language that is not a member of the language to be learned according to certain criteria (any, the least according to some total order, or some particularly small counterexample according to some size). In earlier work [the first author et al., J. Comput. Syst. Sci. 78, No. 6, 1910--1927 (2012; Zbl 1250.68137)] an automatic variant of this learning scenario without the counterexamples was introduced. In the automatic learnability the learner is restricted to be automatic, which means that its computed function is a regular relation (i.e., recognized by a finite automaton). Additionally, the authors also place memory restrictions on the learner. In the earlier work it was demonstrated that automatic learners are rather weak based on positive data alone. In the present work, this investigation is extended to the scenario that includes counterexamples. It is demonstrated that typically all automatic classes can be learned in this manner. The memory of the learner can even be restricted to the length of the longest datum seen so far without effect on the learnability. Only in the scenario in which the counterexample returned is bounded in size by the length of the longest datum seen so far a restricted learnability is observed. The authors present a characterization of the languages that can be successfully learned despite these severe restrictions. In conjunction with memory restrictions on the learner the situation becomes more involved and the authors also present results for these setups, which are still reasonably powerful. The paper is well written and should be generally understandable by anyone with a graduate level understanding of basic automata theory. The text is generally focussed on definitions and results, but motivation is provided in the text. Since most proofs are rather constructive in nature, additional examples are not much missed.