Home

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:
Technical reports
Department:
Computer Science
Permanent 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:
109
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use