Alternating space is closed under complement and other simulations for sublogarithmic space

DOI10.1016/J.IC.2017.02.001zbMATH Open1364.68215OpenAlexW2590387946MaRDI QIDQ515583FDOQ515583

Authors: Viliam Geffert 

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

Recommendations

• Alternating demon space is closed under complement and other simulations for sublogarithmic space
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• The Sublogarithmic Alternating Space World
• scientific article; zbMATH DE number 512811
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

zbMATH Keywords

computational complexityalternationsublogarithmic space

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the computational power of pushdown automata
• Nondeterministic Space is Closed under Complementation
• Alternation
• Title not available (Why is that?)
• The method of forced enumeration for nondeterministic automata
• Halting space-bounded computations
• Turing machines with sublogarithmic space
• Title not available (Why is that?)
• The alternation hierarchy for sublogarithmic space is infinite
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• A hierarchy that does not collapse : alternations in low level space
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• The Sublogarithmic Alternating Space World
• Nondeterminism is essential in small two-way finite automata with few reversals
• One-tape, off-line Turing machine 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
• Alternating Pushdown and Stack Automata
• Title not available (Why is that?)
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Sublogarithmic Bounds on Space and Reversals
• On languages accepted with simultaneous complexity bounds and their ranking problem
• UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)
• Inductive counting for width-restricted branching programs
• A speed-up theorem without tape compression
• A tradeoff theorem for space and reversal

Cited In (7)

• Alternation with restrictions on looping
• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
• For completeness, sublogarithmic space is no space.
• The Sublogarithmic Alternating Space World
• The alternation hierarchy for sublogarithmic space is infinite
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Alternating space is closed under complement and other simulations for sublogarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515583)