The Complexity of Learning SUBSEQ(A) Authors: Stephen Fenner and William Gasarch Source: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, October 2006, Proceedings, (José L. Balcázar, Phil Long and Frank Stephan, Eds.), Lecture Notes in Artificial Intelligence 4264, pp. 109 - 123, Springer 2006. Abstract. Higman showed¹ that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. We consider the following inductive inference problem: given A(ε), A(0), A(1), A(00),… learn, in the limit, a DFA for SUBSEQ(A). We consider this model of learning and the variants of it that are usually studied in inductive inference: anomalies, mindchanges, and teams. ¹ The result we attribute to Higman is actually an easy consequence of his work. We explain in the journal version. ©Copyright 2006, Springer