摘要: Queues are compared to stacks and tapes. Offline machines with a one-way input, deterministic and nondeterministic are considered. The techniques rely on algorithmic information theory (Kolmogorov complexity). The jamming lemma is used. It is shown that deterministically simulating a queue by a tape takes quadratic time (infinitely often). A lower bound for nondeterministically simulating a stack by a queue is obtained. Lower and upper bounds for simulating k queues by 2 queues or 2 queues by 1 queue are obtained. (ESA)