The Sublogarithmic Alternating Space World

DOI10.1137/S0097539793252444zbMath0857.68039OpenAlexW2089947021MaRDI QIDQ4895832

Maciej Liśkiewicz, K. Ruediger 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

Turing machinesnonregular context-free languages

Mathematics Subject Classification ID

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

Related Items (15)

Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes ⋮ 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 note on one-pebble two-dimensional Turing machines ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ 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 ⋮ UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n) ⋮ CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES ⋮ For completeness, sublogarithmic space is no space.

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