He is best known for his Turing-award-winning paper with Richard Stearns, in which he introduced time complexity classes TIME (f(n)) and proved the time hierarchy theorem.
Han er bedst kendt for den Turing-prisvindende afhandling han udfærdigede samen med Richard Stearns, i hvilken han indførte tidskompleksitetets klasser TIME (f(n)) og beviste tidshierarkiets teorem.