Turing machines with sublogarithmic space
From MaRDI portal
Publication:1338452
zbMath0998.68062MaRDI QIDQ1338452
Publication date: 1 December 1994
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
03D15: Complexity of computation (including implicit computational complexity)
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D10: Turing machines and related notions
Related Items
Lower Space Bounds for Accepting Shuffle Languages, Some results concerning two-dimensional turing machines and finite automata, Minimal Size of Counters for (Real-Time) Multicounter Automata, Uncountable classical and quantum complexity classes, Languages, Decidability, and Complexity, A note on one-pebble two-dimensional Turing machines, A note on one-pebble two-dimensional Turing machines, Alternation for sublogarithmic space-bounded alternating pushdown automata, Complement for two-way alternating automata, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Membership Problem for Two-Dimensional General Row Jumping Finite Automata, Weak and strong one-way space complexity classes, Two-way automata making choices only at the endmarkers, Alternating space is closed under complement and other simulations for sublogarithmic space, Two-way unary automata versus logarithmic space, Unbounded-error quantum computation with small space bounds, Passively mobile communicating machines that use restricted space, A note on alternating one-pebble Turing machines with sublogarithmic space, Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal, A communication hierarchy of parallel computations, Bridging across the \(\log(n)\) space frontier, On space functions fully constructed by two-dimensional Turing machines, A remark on middle space bounded alternating Turing machines, Space hierarchy theorem revised., A variant of inductive counting, Quantum computation with write-only memory, On store languages of language acceptors, Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines, A note on two-dimensional probabilistic Turing machines, Non-closure property of space-bounded two-dimensional alternating Turing machines, Uniform constant-depth threshold circuits for division and iterated multiplication., Uncountable realtime probabilistic classes, Some properties of one-pebble Turing machines with sublogarithmic space, A computation model with automatic functions and relations as primitive operations, Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space, Translation from classical two-way automata to pebble two-way automata, Random Generation for Finitely Ambiguous Context-free Languages, Factoring and Testing Primes in Small Space
