Reversal Complexity

DOI10.1137/0220039zbMath0736.68028OpenAlexW2911693923MaRDI QIDQ3978172

Chee-Keng Yap, Jian'er Chen

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/0220039

zbMATH Keywords

parallel time complexitycomplete languagesreversal hierarchiestape reduction theorem

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Tight lower bounds for query processing on streaming and external memory data ⋮ Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines ⋮ Reversal complexity revisited ⋮ On the relationship between deterministic time and deterministic reversal ⋮ Tradeoff lower lounds for stack machines ⋮ On the Value of Multiple Read/Write Streams for Data Compression