Turing machines with sublogarithmic space
From MaRDI portal
Recommendations
Cited in
(42)- Some results concerning two-dimensional turing machines and finite automata
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Some properties of one-pebble Turing machines with sublogarithmic space
- Computational power of one-way Turing machines with sublogarithmic memory restrictions
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- Minimal Size of Counters for (Real-Time) Multicounter Automata
- Translation from classical two-way automata to pebble two-way automata
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
- Languages, Decidability, and Complexity
- Non-closure property of space-bounded two-dimensional alternating Turing machines
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- A variant of inductive counting
- A note on one-pebble two-dimensional Turing machines
- A communication hierarchy of parallel computations
- Two-way unary automata versus logarithmic space
- A remark on middle space bounded alternating Turing machines
- Random Generation for Finitely Ambiguous Context-free Languages
- A note on one-pebble two-dimensional Turing machines
- Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines
- A note on two-dimensional probabilistic Turing machines
- On space functions fully constructed by two-dimensional Turing machines
- Bridging across the \(\log(n)\) space frontier
- Alternating space is closed under complement and other simulations for sublogarithmic space
- A note on alternating one-pebble Turing machines with sublogarithmic space
- Lower Space Bounds for Accepting Shuffle Languages
- Membership problem for two-dimensional general row jumping finite automata
- On store languages of language acceptors
- A computation model with automatic functions and relations as primitive operations
- Closure property of probabilistic Turing machines and alternating Turing machines with sublogarithmic spaces
- Uncountable classical and quantum complexity classes
- Factoring and Testing Primes in Small Space
- Unbounded-error quantum computation with small space bounds
- Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal
- Weak and strong one-way space complexity classes
- Space hierarchy theorem revised.
- Alternating demon space is closed under complement and other simulations for sublogarithmic space
- Passively mobile communicating machines that use restricted space
- Complement for two-way alternating automata
- Alternation for sublogarithmic space-bounded alternating pushdown automata
- scientific article; zbMATH DE number 1848283 (Why is no real title available?)
This page was built for publication: Turing machines with sublogarithmic space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338452)
