Two Nonlinear Bounds for On-Line Computations
- Two Nonlinear Bounds for On-Line Computations
- Duris, Pavol
- Computer Science
- Persistent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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.
- Computer science
- Item views
text | xml
- Suggested Citation:
- Pavol Duris, Zvi Galil, Wolfgang Paul, Ruediger Reischuk, 1983, Two Nonlinear Bounds for On-Line Computations, Columbia University Academic Commons, https://doi.org/10.7916/D87S7WRD.