The complexity of learning SUBSEQ(A)

Journal of Symbolic Logic 74 (3):939-975 (2009)


Higman essentially 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. Let s1, s2, s3, . . . be the standard lexicographic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: given A(s1), A(s2), A(s3), . . . . learn, in the limit, a DFA for SUBSEQU). 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 [10]

Download options


    Upload a copy of this work     Papers currently archived: 72,660

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

11 (#858,955)

6 months
1 (#388,784)

Historical graph of downloads
How can I increase my downloads?

Similar books and articles

Complexity in Language Acquisition.Alexander Clark & Shalom Lappin - 2013 - Topics in Cognitive Science 5 (1):89-110.
Reducing Problem Complexity by Analogical Transfer.Peter F. Dominey - 1997 - Behavioral and Brain Sciences 20 (1):71-72.