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.
Publication
STOC 1980
Conference paper
Comparative schematology and pebbling with auxiliary pushdowns
Abstract
This paper has three claims to interest. First, it combines comparative schematology with complexity theory. This combination is capable of distinguishing among Strong's "languages of maximal power," a distinction not possible when comparative schematology is based on computability considerations alone, and it is capable of establishing exponential disparities in running times, a capability not currently possessed by complexity theory alone. Secondly, this paper inaugurates the study of pebbling with auxiliary pushdowns, which bears to plain pebbling the same relationship as Cook's study of space-bounded machines with auxiliary pushdowns bears to plain space-bounded machines. This extension of pebbling serves as the key to the problems of comparative schematology mentioned above. Finally, this paper advantageously displays the virtues of recent work by Gabber and Galil giving explicit constructions for certain graphs, for the availability of such explicit constructions is essential to the results of this paper.