Comparative schematology and pebbling with auxiliary pushdowns (Preliminary Version)
Nicholas J. Pippenger · 1980
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.