scientific article; zbMATH DE number 512810

zbMATH Open0797.68056MaRDI QIDQ4281503FDOQ4281503

Authors: Burchard von Braunmühl 

Publication date: 7 April 1994

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

collapsealternation hierarchysublogarithmic spacestructural complexity theorytwo-way Turing machines

Mathematics Subject Classification ID

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

Cited In (10)

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

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)