Turing machines with sublogarithmic space

zbMath0998.68062MaRDI QIDQ1338452

Andrzej Szepietowski

Publication date: 1 December 1994

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Related Items (39)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Weak and strong one-way space complexity classes ⋮ A note on alternating one-pebble Turing machines with sublogarithmic space ⋮ Some results concerning two-dimensional turing machines and finite automata ⋮ On space functions fully constructed by two-dimensional Turing machines ⋮ A remark on middle space bounded alternating Turing machines ⋮ Uncountable realtime probabilistic classes ⋮ A communication hierarchy of parallel computations ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Space hierarchy theorem revised. ⋮ Passively mobile communicating machines that use restricted space ⋮ Two-way automata making choices only at the endmarkers ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ A note on one-pebble two-dimensional Turing machines ⋮ A note on one-pebble two-dimensional Turing machines ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ 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 ⋮ Quantum computation with write-only memory ⋮ Two-way unary automata versus logarithmic space ⋮ Unbounded-error quantum computation with small space bounds ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata ⋮ Factoring and Testing Primes in Small Space ⋮ Complement for two-way alternating automata ⋮ On store languages of language acceptors ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ Uncountable classical and quantum complexity classes ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Lower Space Bounds for Accepting Shuffle Languages ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic Turing machines ⋮ A variant of inductive counting ⋮ Languages, Decidability, and Complexity ⋮ Some properties of one-pebble Turing machines with sublogarithmic space ⋮ Membership Problem for Two-Dimensional General Row Jumping Finite Automata ⋮ Non-closure property of space-bounded two-dimensional alternating Turing machines ⋮ Random Generation for Finitely Ambiguous Context-free Languages

This page was built for publication: Turing machines with sublogarithmic space