Nondeterministic Computations in Sublogarithmic Space and Space Constructibility

DOI10.1137/0220031MaRDI QIDQ3978779zbMATH OpenOpenAlexFDO

Authors 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

nondeterministic spacenondeterministic Turing machinereversing automatonspace constructibilityspace-bounded computationsublogarithmic space

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 177808
• Bridging across the (n) space frontier
• Turing machines with sublogarithmic space

Cited in

(30)

• A communication hierarchy of parallel computations
• On space functions constructed by two-dimensional Turing machines
• A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space
• Bridging across the (n) space frontier
• On 1-inkdot alternating Turing machines with small space
• A note on multi-inkdot nondeterministic Turing machines with small space
• On space functions fully constructed by two-dimensional Turing machines
• 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
• Weak and strong one-way space complexity classes
• Translation from classical two-way automata to pebble two-way automata
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• scientific article; zbMATH DE number 3856412 (Why is no real title available?)
• On the State Complexity of Operations on Two-Way Finite Automata
• Factoring and Testing Primes in Small Space
• scientific article; zbMATH DE number 4045156 (Why is no real title available?)
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• scientific article; zbMATH DE number 177808 (Why is no real title available?)
• Sublogarithmic Bounds on Space and Reversals
• A hierarchy that does not collapse : alternations in low level space
• An alternating hierarchy for finite automata
• 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)\)
• Two-way automata and bounded languages
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n

This page was built for publication: Nondeterministic Computations in Sublogarithmic Space and Space Constructibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978779)