ECCC-Report TR08-053https://eccc.weizmann.ac.il/report/2008/053Comments and Revisions published for TR08-053en-usMon, 19 May 2008 05:04:47 +0300
Paper TR08-053
| The complexity of learning SUBSEQ(A) |
Stephen A. Fenner,
William Gasarch,
Brian Postow
https://eccc.weizmann.ac.il/report/2008/053 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.
Mon, 19 May 2008 05:04:47 +0300https://eccc.weizmann.ac.il/report/2008/053