Bridging across the \(\log(n)\) space frontier

DOI10.1006/inco.1997.2682zbMath0917.68077OpenAlexW2059646261MaRDI QIDQ1271619

Viliam Geffert

Publication date: 10 November 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1997.2682

zbMATH Keywords

space bounded computations

Mathematics Subject Classification ID

Related Items (9)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Space hierarchy theorem revised. ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ A variant of inductive counting

Cites Work

• Inductive counting for width-restricted branching programs
• New developments in structural complexity theory
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
• The method of forced enumeration for nondeterministic automata
• Halting space-bounded computations
• Space bounded computations: Review and new separation results
• A lower bound for the nondeterministic space complexity of context-free recognition
• Space bounds for processing contentless inputs
• The alternation hierarchy for sublogarithmic space is infinite
• An optimal lower bound for nonregular languages
• Turing machines with sublogarithmic space
• Some notes on strong and weak log log n space complexity
• Relationships between nondeterministic and deterministic tape complexities
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Nondeterministic Space is Closed under Complementation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• A hierarchy that does not collapse : alternations in low level space
• The Sublogarithmic Alternating Space World
• Some Results on Tape-Bounded Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bridging across the \(\log(n)\) space frontier