Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

DOI10.1016/0020-0190(89)90158-0zbMATH Open0684.68062OpenAlexW2061378925MaRDI QIDQ1825656FDOQ1825656

Authors: Andrzej Szepietowski 

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90158-0

Recommendations

• scientific article; zbMATH DE number 512811
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Turing machines with sublogarithmic space
• A hierarchy that does not collapse : alternations in low level space
• The Sublogarithmic Alternating Space World

zbMATH Keywords

complementnondeterminismTuring machinespace complexityalternating hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Nondeterministic Space is Closed under Complementation
• Alternation
• The method of forced enumeration for nondeterministic automata
• Halting space-bounded computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Erratum to: Some observations concerning alternating Turing machines using small space
• Space bounds for processing contentless inputs
• Remarks on languages acceptable in log log n space
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• On tape bounds for single letter alphabet language processing

Cited In (14)

• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• A hierarchy that does not collapse : alternations in low level space
• Inductive counting below LOGSPACE
• Closure property of probabilistic Turing machines and alternating Turing machines with sublogarithmic spaces
• Turing machines with sublogarithmic space
• The alternation hierarchy for sublogarithmic space is infinite
• Alternating demon space is closed under complement and other simulations for sublogarithmic space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• A survey of space complexity
• Alternating on-line Turing machines with only universal states and small space bounds
• Some notes on strong and weak log log n space complexity
• Nondeterministic Space is Closed under Complementation
• Alternating space is closed under complement and other simulations for sublogarithmic space
• Title not available (Why is that?)

This page was built for publication: Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

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