The alternation hierarchy for sublogarithmic space is infinite
type: Item
instance of: scholarly article
title: The alternation hierarchy for sublogarithmic space is infinite
zbMATH Open document ID: 0796.68099
DOI: 10.1007/BF01271368
author: Burchard von Braunmühl
author: Romain Gengler
author: Robert Rettinger
published in: Computational Complexity
publication date: 1994-01-23T00:00:00Z
review text: The alternation hierarchy for Turing machines with a space bound between loglog and log is infinite. That applies to all common concepts, especially a) to two-way machines with weak space-bounds, b) to two-way machines with strong space-bounds, and c) to one-way machines with weak space-bounds. In all of these cases the \(\Sigma_ k\)- and \(\Pi_ k\)- classes are not comparable for \(k\geq 2\). Furthermore, the \(\Sigma_ k\)- classes are not closed under intersection and the \(\Pi_ k\)-classes are not closed under union. Thus these classes are not closed under complementation. The hierarchy results also apply to classes determined by an alternation depth which is a function depending on the input rather than on a constant.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 488270
zbMATH Keywords: alternating Turing machines
zbMATH Keywords: space-complexity
zbMATH Keywords: language-hierarchies
MaRDI profile type: Publication
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Q4039803
cites work: Some observations concerning alternating Turing machines using small space
cites work: Q4385524
cites work: Q3912023
cites work: Q4198056
cites work: Q4038686
cites work: Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
cites work: Nondeterministic Space is Closed under Complementation
cites work: ${\text{ASPACE}}(o(\log \log n))$ is Regular
cites work: Reversal Complexity Classes for Alternating Turing Machines
cites work: Q5180413
cites work: Q4281504
cites work: On reversal bounded alternating Turing machines
cites work: Q3793733
cites work: Halting space-bounded computations
cites work: The method of forced enumeration for nondeterministic automata
cites work: Q4281502
Recommended article: Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
Recommended article: Q4281504
Recommended article: Q4281502
Recommended article: Alternating space is closed under complement and other simulations for sublogarithmic space
Recommended article: The Sublogarithmic Alternating Space World
Recommended article: The number of infinite substructures
Recommended article: Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space
Recommended article: Subshifts on an infinite alphabet
Recommended article: For completeness, sublogarithmic space is no space.
Recommended article: Q3695270
description: scientific article; zbMATH DE number 488270