We show in this paper (which appeared in a preliminary form as an extended abstract in [Proceedings of the 9th International ACM--SIAM Symposium on Discrete Algorithms, ACM, 1998]) that deterministic finite automata (DFAs) with n states and input alphabet $\Sigma$ can efficiently be learned from less than $|\Sigma|n^2$ smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required $|\Sigma|n^3$ smallest counterexamples. We present a general strategy which learns a finite concept class ${\cal F}$ from $\lfloor\log{\cal F}\rfloor$ smallest counterexamples (but not necessarily efficiently). An application to DFAs with at most n states shows that $(1+o(1))|\Sigma|n\log n$ smallest counterexamples are sufficient (if efficiency is not an issue). We show next that the special DFAs operating on input words of an arbitrary but fixed length (the so-called leveled DFAs) are efficiently learnable from $(1+o(1))|\Sigma|n\log n$ smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required $|\Sigma|n^2$ smallest counterexamples. Furthermore, we present a general lower bound on the number of smallest counterexamples (required by any learning algorithm). This bound can be stated in terms of a (new) combinatorial dimension associated with the target class. A computation of this dimension for leveled or arbitrary DFAs leads to a lower bound of the form $(\frac{1}{4}+o(1))|\Sigma|n\log n$. This bound matches the aforementioned upper bounds modulo a constant of approximately 4. Finally, we present a general conversion of algorithms learning from smallest counterexamples into algorithms performing self-directed learning. Forthe particular classes of leveled or arbitrary DFAs, this conversion leads to self-directed learners making the smallest possible number of mistakes (modulo a constant of approximately 4). A similar remark is valid for the class of multiplicity automata (MAs).

This paper deals with the UAV learning model of Goldman, Kwek and Scott [7]. ("UAV" is the acronym for "Unspecified Attribute Values".) As in [7], we consider exact learning within the UAV framework, where the learner has to exactly identify an unknown target concept by means of UAV membership (UAV-MQs) and/or UAV equivalence queries (UAV-EQs or UAV-ARB-EQs, respectively). A smooth transition between exact learning in the UAV setting and standard exact learning is obtained by putting a fixed bound r on the number of unspecified attribute values per instance. For r = 0, we obtain the standard model. For r = n (the total number of attributes), we obtain the (unrestricted) UAV model. Between these extremes, we find the hierarchies (UAV-MQ r ) 0rn , (UAV-EQ r ) 0rn , and (UAV-ARB-EQ r ) 0rn . Our main results are as follows. We present lower bounds on the number of ARB-EQs and UAV-MQs in terms of the Vapnik Chervonenkis dimension of the concept class. We show furthermore that a...

In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner.While the k-RFA model is a natural extension of the PAC model, there are also significant differences.For example, it was previously known that learnability in this model is not characterized by the VC dimension and that many PAC learning algorithms are not applicable in the k-RFA setting.In this paper we further explore the relationship between the PAC and k-RFA models, with several interesting results.First, we develop a characterization of k-RFA learnability upon which we build a general tool for proving hardness results.We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes, k-decision-lists (k-DL) and k-TOP, the class of thresholds of parity functions in which each parity function takes at most k inputs.Among other results, we prove a hardness result for k-RFA learnability of k-DL, k ~n -2.In sharp contrast, an (n -1)-RFA algorithm for learning (n -l)decision-lists is presented.Similarly, we prove that 1-DL is learnable if and only if at least half of the inputs are visible in each instance.In addition, we show that there is a uniform-distribution lc-RFA learning algorithm for the class of k-decision-lists