About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Depth-bounded computation
Abstract
A programming language designed for studies of parallelism and based on Wagner'suniformly reflexive structures is introduced. The measure of depth of computation in the language is studied. The partial recursive functions are shown to be computable in uniformly bounded depth. A comparison of the measure with other proposed measures of computational complexity leads to the suggestion of a list of properties to be checked in classifying such measures. © 1970 Academic Press, Inc.