[38] A k-pushdown store machine is similar to a k-tape Turing machine with one-way input except that the k work tapes are replaced by k pushdown stores. Prove: simulating a linear-time 2-pushdown store deterministic machine with one-way input by a 1-tape nondeterministic Turing machine with one-way input requires Ω(n3/2/

√log n) time.

Comments. Source: [M. Li and P.M.B. Vit´anyi, Inform. Comput., 78(1988), 56–85]. This bound is optimal, since it is known that simulating a lineartime 2-pushdown store deterministic machine with one-way input by a 1-tape nondeterministic Turing machine with one-way input can be done in O(n3/2√log n) time [M. Li, J. Comput. System Sci., 7:1(1988), 101–

116].