dc.contributor.author Li, Ming en_US dc.date.accessioned 2007-04-23T17:08:38Z dc.date.available 2007-04-23T17:08:38Z dc.date.issued 1985-03 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-667 en_US dc.identifier.uri https://hdl.handle.net/1813/6507 dc.description.abstract Based on two graph separator theorems, one old (the Lipton-Tarjan planar separator theorem) and one new, we present two unexpected upper bounds and resolve several open problems for on-line computations: (1) 1 tape nondeterministic machines can simulate 2 pushdown stores in time $O(n^{1.5} \sqrt{logn})$ (true for both on-line and off-line machines). Together with the $\Omega (n^{1.5} \sqrt{logn})$ lower bound by the author [L1], this solved the open problem 1 in [DGPR] for the 1 tape vs. 2 pushdown case. It also disproves the commonly conjectured $\Omega (n^{2})$ lower bound. (Note, the $\Omega (n^{2})$ lower bound has been proved for the deterministic case [M, L, V].) (2) the languages defined by [M] and [F], aimed to obtain optimal lower bound for 1 tape nondeterministic machines, can be accepted in $O(n^{2}loglogn / \sqrt{logn})$ and $O(n^{1.5}\sqrt{logn})$ time by a 1 tape TM, respectively. (3) 3 pushdown stores are better than 2 pushdown stores. This answers open problem 3 of [DG]. (An $\Omega(n^{4/3} / log^{e} n)$ lower bound is also obtained.) (4) 1 tape can nondeterministically simulate 1 queue in $O(n^{1.5} \sqrt{logn})$ time. (The lower bounds were: $\Omega(n^{2})$ for deterministic case [V] and $\Omega(n^{4/3} / logn)$ [L1] for nondeterministic case.) en_US dc.format.extent 1333056 bytes dc.format.extent 310846 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Simulating Two Pushdown Stores by One Tape in $O(n^{1.5}\sqrt{logn}$) Time. (Preliminary Version) en_US dc.type technical report en_US
﻿