Simulating Two Pushdown Stores by One Tape in $O(n^{1.5}\sqrt{logn}$) Time. (Preliminary Version)
| 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.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.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.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 |