Alternating space is closed under complement and other simulations for sublogarithmic space
From MaRDI portal
Publication:515583
DOI10.1016/j.ic.2017.02.001zbMath1364.68215OpenAlexW2590387946MaRDI QIDQ515583
Publication date: 16 March 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2017.02.001
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- Inductive counting for width-restricted branching programs
- A speed-up theorem without tape compression
- A tradeoff theorem for space and reversal
- The method of forced enumeration for nondeterministic automata
- Halting space-bounded computations
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Space bounded computations: Review and new separation results
- Bridging across the \(\log(n)\) space frontier
- The alternation hierarchy for sublogarithmic space is infinite
- Turing machines with sublogarithmic space
- Nondeterminism is essential in small two-way finite automata with few reversals
- Relationships between nondeterministic and deterministic tape complexities
- On the computational power of pushdown automata
- Alternating Pushdown and Stack Automata
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Nondeterministic Space is Closed under Complementation
- Alternation
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- Sublogarithmic Bounds on Space and Reversals
- A hierarchy that does not collapse : alternations in low level space
- The Sublogarithmic Alternating Space World
- On languages accepted with simultaneous complexity bounds and their ranking problem
- UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)
- One-tape, off-line Turing machine computations
This page was built for publication: Alternating space is closed under complement and other simulations for sublogarithmic space
