Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time (Q1113670)

Two important results are proved in the paper: Theorem 1'. A one-tape nondeterministic Turing machine can simulate a two-pushdown store Turing machine in \(O(n^{1.5} \sqrt{\log n})\) time. Theorem 2. The languages used by \textit{W. Maass} [Trans. Am. Math. Soc. 292, 675-693 (1985; Zbl 0608.03013)] and \textit{R. Freivalds} [Inf. Process. 77, Proc. IFIP Congr., Toronto 1977, 839-842 (1977; Zbl 0367.94079)] can be accepted in \(O(n^ 2 \log \log n/\sqrt{\log n})\) time by a one-tape nondeterministic on-line machine. Theorem 1' disproves the conjectured \(O(n^ 2)\) lower bound which holds for the deterministic case. The proof is based on the separator theorem for planar graphs [\textit{R. J. Lipton} and \textit{R. E. Tarjan}, SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)]. Theorem 2 shows that the \(O(n^ 2)\) lower bound cannot be obtained for one-tape nondeterministically simulating two tapes. The proof is based on the separator theorem for doubling transformation graphs (a proof of this theorem is given in the paper). As applications the following results are obtained: three pushdown stores are better than two pushdown stores for nondeterministic machines and one tape can nondeterministically simulate one nondeterministic queue in \(O(n^{1.5} \sqrt{\log n})\) time. A list of three open questions ends the paper.