Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
From MaRDI portal
Publication:3978779
DOI10.1137/0220031zbMath0762.68022OpenAlexW2066080128MaRDI QIDQ3978779
Publication date: 25 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220031
sublogarithmic spacenondeterministic Turing machinespace-bounded computationnondeterministic spacespace constructibilityreversing automaton
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On 1-inkdot alternating Turing machines with small space ⋮ A note on multi-inkdot nondeterministic Turing machines with small space ⋮ Weak and strong one-way space complexity classes ⋮ A communication hierarchy of parallel computations ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Space hierarchy theorem revised. ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ An alternating hierarchy for finite automata ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ Magic numbers in the state hierarchy of finite automata ⋮ A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Factoring and Testing Primes in Small Space ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
