Jump to content

Richard E. Stearns

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 2601:5c0:c100:2384:f0ee:74c7:29f9:e7bd (talk) at 18:01, 6 October 2018. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Richard Edwin Stearns
Richard Stearns in 2009
Born (1936-07-05) July 5, 1936 (age 88)
Caldwell, New Jersey
Alma materPrinceton University
AwardsACM Turing Award (1993)
Frederick W. Lanchester Prize (1995)
Scientific career
InstitutionsUniversity at Albany
Doctoral advisorHarold W. Kuhn
Doctoral studentsMadhav V. Marathe (joint with Professor Harry B. Hunt III), Tom O'Connell

Richard Edwin Stearns (born July 5, 1936) is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory" (Hartmanis and Stearns, 1965). In 1994 he was inducted as a Fellow of the Association for Computing Machinery.

Stearns earned his PhD from Princeton University in 1961. His PhD thesis adviser was Harold W. Kuhn. Stearns is now Distinguished Professor Emeritus of Computer Science at the University at Albany, which is part of the State University of New York.

Bibliography

  • Stearns, R.E.; Hartmanis, J. (March 1963), "Regularity preserving modifications of regular expressions", Information and Control, 6 (1): 55–69, doi:10.1016/S0019-9958(63)90110-4. A first systematic study of language operations that preserve regular languages.
  • Hartmanis, J.; Stearns, R. E. (May 1965), "On the computational complexity of algorithms", Transactions of the American Mathematical Society, 117, American Mathematical Society: 285–306, doi:10.2307/1994208, JSTOR 1994208, MR 0170805. Contains the time hierarchy theorem, one of the theorems that shaped the field of computational complexity theory.
  • Stearns, R.E. (September 1967), "A Regularity Test for Pushdown Machines", Information and Control, 11 (3): 323–340, doi:10.1016/S0019-9958(67)90591-8. Answers a basic question about deterministic pushdown automata: it is decidable whether a given deterministic pushdown automaton accepts a regular language.
  • Lewis II, P.M.; Stearns, R.E. (1968), "Syntax-Directed Transduction", Journal of the ACM, 15 (3): 465–488, doi:10.1145/321466.321477. Introduces LL parsers, which play an important role in compiler design.
P ≟ NP 

This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Richard_E._Stearns&oldid=862786547"