Technical reports:
Two Nonlinear Bounds for On-Line Computations
Pavol Duris; Zvi Galil; Wolfgang Paul; Ruediger Reischuk
Downloads:
- Title:
- Two Nonlinear Bounds for On-Line Computations
- Author(s):
-
Duris, Pavol
Galil, Zvi
Paul, Wolfgang
Reischuk, Ruediger - Date:
- 1983
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:11548
- 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:
- 74