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