1. The Complexity of Finding SUBSEQ( A).
- Author
-
Fenner, Stephen, Gasarch, William, and Postow, Brian
- Subjects
- *
TURING machines , *INDEXES , *MACHINE theory , *INPUT-output analysis - Abstract
Higman showed that if A is any language then SUBSEQ( A) is regular. His proof was nonconstructive. We show that the result cannot be made constructive. In particular we show that if f takes as input an index e of a total Turing Machine M e, and outputs a DFA for SUBSEQ( L( M e)), then ∅″≤T f ( f is Σ2-hard). We also study the complexity of going from A to SUBSEQ( A) for several representations of A and SUBSEQ( A). [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF