Nondeterministic Computations in Sublogarithmic Space and Space Constructibility

DOI10.1137/0220031zbMath0762.68022MaRDI QIDQ3978779

Viliam Geffert

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

zbMATH Keywords

sublogarithmic space; nondeterministic Turing machine; space-bounded computation; nondeterministic space; space constructibility; reversing automaton

Mathematics Subject Classification ID

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, On languages accepted with simultaneous complexity bounds and their ranking problem, 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 Π₂-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