Tape versus Queue and Stacks: The Lower Bounds (Revised)

摘要

Optimal or nearly optimal lower bounds are derived on the time needed to simulate queue, stacks (stack = pushdown) and tapes by one off-line single-head tape-unit with one-way input, for the deterministic case and the nondeterministic case. The techniques rely on algorithmic information theory (Kolmogorov complexity).