The Sublogarithmic Alternating Space World

DOI10.1137/S0097539793252444MaRDI QIDQ4895832zbMATH OpenOpenAlexFDO

Authors Maciej Liśkiewicz, Rüdiger Reischuk

Publication date 3 March 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793252444

zbMATH Keywords

nonregular context-free languagesTuring machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• The alternation hierarchy for sublogarithmic space is infinite
• scientific article; zbMATH DE number 512811
• Sublogarithmic Bounds on Space and Reversals
• scientific article; zbMATH DE number 2172793
• The hyperspace of meager subcontinua
• scientific article; zbMATH DE number 1072535
• scientific article; zbMATH DE number 512809
• Choiceless Logarithmic Space
• Alternating space is closed under complement and other simulations for sublogarithmic space
• A class of substitution systems and the hyperspace systems

Cited in

(31)

• Alternating on-line Turing machines with only universal states and small space bounds
• Bridging across the (n) space frontier
• The alternation hierarchy for sublogarithmic space is infinite
• Turing machines with sublogarithmic space
• Space hierarchy theorem revised.
• A variant of inductive counting
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• For completeness, sublogarithmic space is no space.
• 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
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• scientific article; zbMATH DE number 512811 (Why is no real title available?)
• scientific article; zbMATH DE number 1072535 (Why is no real title available?)
• An alternating hierarchy for finite automata
• scientific article; zbMATH DE number 2172794 (Why is no real title available?)
• scientific article; zbMATH DE number 3999297 (Why is no real title available?)
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• 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
• Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\)
• A note on one-pebble two-dimensional Turing machines
• A note on one-pebble two-dimensional Turing machines
• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
• Alternation for sublogarithmic space-bounded alternating pushdown automata
• On log-time alternating Turing machines of alternation depth k
• A note on alternating one-pebble Turing machines with sublogarithmic space

This page was built for publication: The Sublogarithmic Alternating Space World

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