scientific article; zbMATH DE number 512810

MaRDI QIDQ4281503zbMATH OpenFDO

Authors Burchard von Braunmühl

Publication date 7 April 1994

zbMATH Keywords

alternation hierarchycollapsestructural complexity theorysublogarithmic spacetwo-way Turing machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The alternation hierarchy for sublogarithmic space is infinite
• A hierarchy that does not collapse : alternations in low level space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

Cited in

(11)

• A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
• A note on multi-inkdot nondeterministic Turing machines with small space
• For completeness, sublogarithmic space is no space.
• Two-way automata versus logarithmic space
• A space lower bound for acceptance by one-way _2-alternating machines
• Two-Way Automata versus Logarithmic Space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• scientific article; zbMATH DE number 4049051 (Why is no real title available?)
• scientific article; zbMATH DE number 45125 (Why is no real title available?)
• A hierarchy that does not collapse : alternations in low level space
• scientific article; zbMATH DE number 2172793 (Why is no real title available?)

This page was built for publication:

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