Reversal complexity revisited

DOI10.1016/j.tcs.2008.04.026zbMath1147.68022OpenAlexW2170954902MaRDI QIDQ935164

Nicole Schweikardt, André Hernich

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)

Related Items (3)

Tight lower bounds for query processing on streaming and external memory data ⋮ Tradeoff lower lounds for stack machines ⋮ On the Value of Multiple Read/Write Streams for Data Compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded-depth, polynomial-size circuits for symmetric functions
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
• On the relationship between deterministic time and deterministic reversal
• Algorithms for memory hierarchies. Advanced lectures
• Tight lower bounds for query processing on streaming and external memory data
• Relationships between nondeterministic and deterministic tape complexities
• Lower bounds for randomized read/write stream algorithms
• Reversal Complexity
• Rounds in Communication Complexity Revisited
• Expressibility and Parallel Complexity
• A note on nondeterminism in small, fast parallel computers
• Fundamentals of Computation Theory

This page was built for publication: Reversal complexity revisited