Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with subsequence:
TR08-053 | 27th March 2008
Stephen A. Fenner, William Gasarch, Brian Postow

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, ... more >>>

ISSN 1433-8092 | Imprint