Richard E. Stearns

Richard Edwin Stearns (1936 to 2026) was an American computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award in recognition of the seminal paper that established the foundations of computational complexity theory. He earned a B.A. in mathematics from Carleton College in 1958 and a Ph.D. in mathematics from Princeton University in 1961, with a dissertation titled Three person cooperative games without side payments written under Harold W. Kuhn. He later became Distinguished Professor Emeritus of Computer Science at the University at Albany, part of the State University of New York, and was inducted as a Fellow of the Association for Computing Machinery in 1994. His 1965 paper with Hartmanis on the computational complexity of algorithms contains the time hierarchy theorem. His other notable work includes a 1963 study of operations that preserve regular languages, a 1967 regularity test for pushdown machines showing that it is decidable whether a deterministic pushdown automaton accepts a regular language, and a 1968 paper with P. M. Lewis II that introduced LL parsers, which matter in compiler design.