Space-efficient recognition of sparse self-reducible languages

DOI10.1007/BF01206639MaRDI QIDQ1337147zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

time-space-efficient algorithms

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

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

Cites work

• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• scientific article; zbMATH DE number 512798 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A Note on Sparse Complete Sets
• A comparison of polynomial time reducibilities
• A low and a high hierarchy within NP
• A taxonomy of problems with fast parallel algorithms
• Hard promise problems and nonuniform complexity
• Limitations of the upward separation technique
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Relating Time and Space to Size and Depth
• On log-tape isomorphisms of complete sets
• On polynomial time one-truth-table reducibility to a sparse set
• On the Tape Complexity of Deterministic Context-Free Languages
• On time-space classes and their relation to the theory of real addition
• On uniform circuit complexity
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Relationships between nondeterministic and deterministic tape complexities
• Relativization of questions about log space computability
• Self-reducibility
• Self-reducible sets of small density
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• The recognition of deterministic CFLs in small time and space
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

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
• A lower bound for the nondeterministic space complexity of context-free recognition
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• 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)