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

DOI10.1016/J.IC.2017.02.001MaRDI QIDQ515583zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexityalternationsublogarithmic space

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3858415 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 793950 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• A hierarchy that does not collapse : alternations in low level space
• A speed-up theorem without tape compression
• A tradeoff theorem for space and reversal
• Alternating Pushdown and Stack Automata
• Alternation
• Bridging across the \(\log(n)\) space frontier
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Halting space-bounded computations
• Inductive counting for width-restricted branching programs
• Nondeterminism is essential in small two-way finite automata with few reversals
• Nondeterministic Space is Closed under Complementation
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
• On languages accepted with simultaneous complexity bounds and their ranking problem
• On the computational power of pushdown automata
• One-tape, off-line Turing machine computations
• Relationships between nondeterministic and deterministic tape complexities
• Space bounded computations: Review and new separation results
• Sublogarithmic Bounds on Space and Reversals
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• The Sublogarithmic Alternating Space World
• The alternation hierarchy for sublogarithmic space is infinite
• The method of forced enumeration for nondeterministic automata
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Turing machines with sublogarithmic space
• Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\)

Cited in

(8)

• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
• The alternation hierarchy for sublogarithmic space is infinite
• scientific article; zbMATH DE number 3868618 (Why is no real title available?)
• scientific article; zbMATH DE number 1332655 (Why is no real title available?)
• For completeness, sublogarithmic space is no space.
• Alternation with restrictions on looping
• The Sublogarithmic Alternating Space World
• Alternating demon space is closed under complement and other simulations for sublogarithmic space

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)