The alternation hierarchy for sublogarithmic space is infinite

DOI10.1007/BF01271368zbMath0796.68099MaRDI QIDQ1312177

Robert Rettinger, Romain Gengler, Burchard von Braunmühl

Publication date: 23 January 1994

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

alternating Turing machinesspace-complexitylanguage-hierarchies

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items

Inductive counting below logspace, Space hierarchy theorem revised., An alternating hierarchy for finite automata, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE, A note on one-pebble two-dimensional Turing machines, A hierarchy that does not collapse : alternations in low level space, A note on one-pebble two-dimensional Turing machines, 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, Some properties of one-pebble Turing machines with sublogarithmic space, CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES, For completeness, sublogarithmic space is no space.

Cites Work

• Some observations concerning alternating Turing machines using small space
• The method of forced enumeration for nondeterministic automata
• On reversal bounded alternating Turing machines
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Halting space-bounded computations
• Reversal Complexity Classes for Alternating Turing Machines
• Nondeterministic Space is Closed under Complementation
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item