Compression for data archiving and backup revisited
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
It is proved that for infinitely many n there is a directed acyclic graph with vertex indegrees bounded by 2 that has a strategy of the black-white pebble game using n pebbles and for which any strategy of the black pebble game requires Ω(n log n/log log n) pebbles. This shows that there is a family of straight-line programs for which nondeterminism reduces the space required to evaluate the programs by more than any constant factor. © 1988.
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998