Space-efficient recognition of sparse self-reducible languages
From MaRDI portal
Publication:1337147
DOI10.1007/BF01206639zbMATH Open0812.68073OpenAlexW2015323017MaRDI QIDQ1337147FDOQ1337147
Authors: Lane A. Hemaspaandra, Ogihara, Mitsunori, Seinosuke Toda 
Publication date: 14 May 1995
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01206639
Recommendations
- Language recognition power and succinctness of affine automata
- Language Recognition Power and Succinctness of Affine Automata
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
- A lower bound for the nondeterministic space complexity of context-free recognition
- A space-optimal grammar compression
- EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
- scientific article; zbMATH DE number 1962778
- scientific article; zbMATH DE number 3978426
- scientific article; zbMATH DE number 3907802
- scientific article; zbMATH DE number 3958761
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- On uniform circuit complexity
- Relationships between nondeterministic and deterministic tape complexities
- A taxonomy of problems with fast parallel algorithms
- Relativization of questions about log space computability
- Title not available (Why is that?)
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Self-reducibility
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- Title not available (Why is that?)
- A low and a high hierarchy within NP
- On Relating Time and Space to Size and Depth
- A comparison of polynomial time reducibilities
- On the Tape Complexity of Deterministic Context-Free Languages
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- The recognition of deterministic CFLs in small time and space
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Title not available (Why is that?)
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Title not available (Why is that?)
- On log-tape isomorphisms of complete sets
- On polynomial time one-truth-table reducibility to a sparse set
- Self-reducible sets of small density
- Hard promise problems and nonuniform complexity
- Limitations of the upward separation technique
- On time-space classes and their relation to the theory of real addition
Cited In (7)
- Self-reducible sets of small density
- The parameterized space complexity of model-checking bounded variable first-order logic
- Dense completeness
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
- A lower bound for the nondeterministic space complexity of context-free recognition
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis
This page was built for publication: Space-efficient recognition of sparse self-reducible languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337147)
