The Sublogarithmic Alternating Space World
From MaRDI portal
Publication:4895832
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
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
