On Simultaneous Resource Bounds
Document Type
Conference Proceeding
Department
Mathematics (HMC)
Publication Date
10-1979
Abstract
It is well known that time bounds for machines correspond closely to size bounds for networks, and that space bounds correspond to depth bounds. It is not known whether simultaneous time and space bounds correspond to simultaneous size and depth bounds. It is shown here that simultaneous time and "reversal" bounds correspond to simultaneous size and depth bounds, and that simultaneous time and space bounds correspond to simultaneous size and "width" bounds.
Rights Information
© 1979 IEEE
DOI
10.1109/SFCS.1979.29
Recommended Citation
Pippenger, Nicholas. "Simultaneous Resource Bounds", IEEE Symp. on Foundations of Comp. Sci., 20 (1979), 307-311.
