TR08-053 Authors: Stephen A. Fenner, William Gasarch, Brian Postow

Publication: 19th May 2008 05:04

Downloads: 1486

Keywords:

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.