Reversal complexity revisited

DOI10.1016/J.TCS.2008.04.026MaRDI QIDQ935164zbMATH OpenOpenAlexFDO

Authors André Hernich, Nicole Schweikardt

Publication date 31 July 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.04.026

zbMATH Keywords

hierarchies of complexity classesreversal-bounded and space-bounded Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• On reversal bounded alternating Turing machines
• The difference between one tape and two tapes: With respect to reversal complexity
• scientific article; zbMATH DE number 3885308

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• A note on nondeterminism in small, fast parallel computers
• Algorithms for memory hierarchies. Advanced lectures
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
• Bounded-depth, polynomial-size circuits for symmetric functions
• Descriptive complexity: a logician's approach to computation.
• Expressibility and Parallel Complexity
• Fundamentals of Computation Theory
• Lower bounds for randomized read/write stream algorithms
• On the relationship between deterministic time and deterministic reversal
• Relationships between nondeterministic and deterministic tape complexities
• Reversal Complexity
• Rounds in Communication Complexity Revisited
• Tight lower bounds for query processing on streaming and external memory data

Cited in

(11)

• Reversal Hierarchies for Small 2DFAs
• Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
• The Complexity of Satisfaction Problems in Reverse Mathematics
• Reverse complexity
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• Tradeoff lower lounds for stack machines
• Time and space complexity of reversible pebbling
• Reversibility in space-bounded computation
• Tight lower bounds for query processing on streaming and external memory data
• A tight amortized bound for path reversal
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines

This page was built for publication: Reversal complexity revisited

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