L Auslander, E Feig, et al.
Advances in Applied Mathematics
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.
L Auslander, E Feig, et al.
Advances in Applied Mathematics
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
Chai Wah Wu
Linear Algebra and Its Applications
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992