Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
From MaRDI portal
Publication:3978779
DOI10.1137/0220031zbMath0762.68022MaRDI 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 space; nondeterministic Turing machine; space-bounded computation; nondeterministic space; space constructibility; reversing automaton
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A hierarchy that does not collapse : alternations in low level space, Investigations on Automata and Languages Over a Unary Alphabet, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Weak and strong one-way space complexity classes, An alternating hierarchy for finite automata, A communication hierarchy of parallel computations, A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space, Bridging across the \(\log(n)\) space frontier, On 1-inkdot alternating Turing machines with small space, A note on multi-inkdot nondeterministic Turing machines with small space, Space hierarchy theorem revised., Converting two-way nondeterministic unary automata into simpler automata., Oblivious two-way finite automata: decidability and complexity, Magic numbers in the state hierarchy of 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, Sublogarithmic $\sum _2$-space is not closed under complement and other separation results, On the State Complexity of Operations on Two-Way Finite Automata, Factoring and Testing Primes in Small Space
