Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Paper
White pebbles help
Abstract
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.
Related
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
A.R. Conn, Nick Gould, et al.
Mathematics of Computation