Academic Commons

Reports

Two Nonlinear Bounds for On-Line Computations

Duris, Pavol; Galil, Zvi; Paul, Wolfgang; Reischuk, Ruediger

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-060-83
Published Here
October 25, 2011