A hierarchy that does not collapse : alternations in low level space

DOI10.1051/ita/1994280504651zbMath0884.68054OpenAlexW10622911MaRDI QIDQ4365021

Viliam Geffert

Publication date: 30 October 1997

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92491

zbMATH Keywords

alternation hierarchy

Mathematics Subject Classification ID

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

Related Items

Inductive counting below logspace ⋮ Space hierarchy theorem revised. ⋮ An alternating hierarchy for finite automata ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ Bridging across the \(\log(n)\) space frontier ⋮ A variant of inductive counting ⋮ For completeness, sublogarithmic space is no space.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some observations concerning alternating Turing machines using small space
• The method of forced enumeration for nondeterministic automata
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• \(\Sigma_ 2SPACE(n)\) is closed under complement
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• Space bounded computations: Review and new separation results
• Space bounds for processing contentless inputs
• The alternation hierarchy for sublogarithmic space is infinite
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Nondeterministic Space is Closed under Complementation
• Alternation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question