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

DOI10.1016/0020-0190(89)90158-0MaRDI QIDQ1825656zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3838107 (Why is no real title available?)
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• scientific article; zbMATH DE number 3723863 (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?)
• Alternation
• Erratum to: Some observations concerning alternating Turing machines using small space
• Halting space-bounded computations
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Nondeterministic Space is Closed under Complementation
• On tape bounds for single letter alphabet language processing
• Remarks on languages acceptable in log log n space
• Space bounds for processing contentless inputs
• The method of forced enumeration for nondeterministic automata

Cited in

(14)

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

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)