HomeHome

Two Nonlinear Bounds for On-Line Computations

Pavol Duris; Zvi Galil; Wolfgang Paul; Ruediger Reischuk

Title:
Two Nonlinear Bounds for On-Line Computations
Author(s):
Duris, Pavol
Galil, Zvi
Paul, Wolfgang
Reischuk, Ruediger
Date:
Type:
Reports
Department(s):
Computer Science
Persistent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-060-83
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
We prove the following lower bounds for on-line computation. 1) Simulating two tape nondeterministic machines by one tape machine requires n(n log n) time. 2) Simulating k tape (deterministic) machines by machines with k pushdown stores requires n(n log 1/(k+l) n) time.
Subject(s):
Computer science
Item views
139
Metadata:
text | xml
Suggested Citation:
Pavol Duris, Zvi Galil, Wolfgang Paul, Ruediger Reischuk, , Two Nonlinear Bounds for On-Line Computations, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ