The complexity of finding SUBSEQ\((A)\)
DOI10.1007/s00224-008-9111-4zbMath1187.68295OpenAlexW2054632127MaRDI QIDQ839630
William I. Gasarch, Brian Postow, Stephen A. Fenner
Publication date: 2 September 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-008-9111-4
computational complexityautomata theorycontext-free languagereverse mathematicsunbounded searchcomputabilitycontext-free grammarautomatonsubsequenceHigman's lemmabounded queriesrecursive mathematicsturing degree
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Comparison of identification criteria for machine inductive inference
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
- Deterministic one-counter automata
- An almost optimal algorithm for unbounded searching
- Effective constructions in well-partially-ordered free monoids
- Binary search and recursive graph problems
- Terse, superterse, and verbose sets
- Bounded queries in recursion theory
- Unbounded Searching Algorithms
- The Complexity of Learning SUBSEQ (A)
- On the Succinctness of Different Representations of Languages
- Effective content of field theory
- Toward a mathematical theory of inductive inference
- On the recursion-theoretic complexity of relative succinctness of representations of languages
- Turing machines with restricted memory access
- Counter machines and counter languages
- Language identification in the limit
- Computability and Recursion
- Ordering by Divisibility in Abstract Algebras
This page was built for publication: The complexity of finding SUBSEQ\((A)\)
