Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)

DOI10.1007/978-3-319-58747-9_14zbMath1423.68252OpenAlexW2610321650MaRDI QIDQ5920059

Viliam Geffert

Publication date: 22 August 2017

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-58747-9_14

zbMATH Keywords

computational complexityalternationsublogarithmic space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space bounded computations: Review and new separation results
• Bridging across the \(\log(n)\) space frontier
• Bits and relative order from residues, space efficiently
• Turing machines with sublogarithmic space
• Relationships between nondeterministic and deterministic tape complexities
• Division in logspace-uniformNC¹
• Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space
• Alternating Pushdown and Stack Automata
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Alternation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)

This page was built for publication: Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)