Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-053 | 27th March 2008 00:00

The complexity of learning SUBSEQ(A)



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. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... be the standard lexicographic
enumeration of all strings over some finite alphabet.
We consider the following inductive inference problem:
given A(s_1), A(s_2), A(s_3), ..., 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, mind-changes, teams, and combinations thereof.

This paper is a significant revision and expansion of an earlier
conference version that appeared in ALT 2006.

ISSN 1433-8092 | Imprint