[46] A k-queue machine is similar to a k-tape Turing machine with one-way input except with the k work tapes replaced by k work queues. A queue is a first-in last-out (FIFO) device. Prove (with one-way input understood):

(a) Simulating a linear-time 1-queue machine by a 1-tape Turing machine requires Ω(n2) time.

(b) Simulating a linear-time 1-queue machine by a 1-tape nondeterministic Turing machine requires Ω(n4/3/ log2/3 n) time.

(c) Simulating a linear-time 1-pushdown store machine (which accepts precisely CFLs) by a 1-queue machine, deterministically or nondeterministically, requires Ω(n4/3/ log n) time.

Comments. Items

(a) and

(b) are from [M. Li and P.M.B. Vit´anyi, Inform. Comput., 78(1988), 56–85]; Item

(c) is from [M. Li, L. Longpr´e, and P.M.B. Vit´anyi, SIAM J. Comput., 21:4(1992), 697–712]. The bound in Item

(a) is tight. The bound in Item

(b) is not tight; the best upper bound is O(n3/2√log n), in [M. Li, J. Comput. System Sci., 7:1(1988), 101–116]. The bound in Item

(c) is not tight; the upper bound is known to be O(n2) (also to simulate a 2-pushdown store machine).