Space hierarchy theorem revised.
From MaRDI portal
Publication:1401238
DOI10.1016/S0304-3975(02)00402-4zbMath1038.68053MaRDI QIDQ1401238
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (7)
P-RAM vs. RP-RAM ⋮ Binary coded unary regular languages ⋮ Passively mobile communicating machines that use restricted space ⋮ Magic numbers in the state hierarchy of finite automata ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts ⋮ UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)
Cites Work
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- The method of forced enumeration for nondeterministic automata
- Halting space-bounded computations
- Space bounded computations: Review and new separation results
- Space bounds for processing contentless inputs
- On tape bounds for single letter alphabet language processing
- Bridging across the \(\log(n)\) space frontier
- The alternation hierarchy for sublogarithmic space is infinite
- Turing machines with sublogarithmic space
- Relationships between nondeterministic and deterministic tape complexities
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- 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
- Separating Nondeterministic Time Complexity Classes
- A hierarchy that does not collapse : alternations in low level space
- The Sublogarithmic Alternating Space World
- Some Results on Tape-Bounded Turing Machines
- A Note Concerning Nondeterministic Tape Complexities
This page was built for publication: Space hierarchy theorem revised.
