Richard Edwin Stearns (born July 5, 1936) is an American

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

who, with

Juris Hartmanis Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established ...

, received the 1993 ACM

Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...

"in recognition of their seminal paper which established the foundations for the field of

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

". In 1994 he was inducted as a

Fellow of the Association for Computing Machinery A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned or professional societies, the term refers ...

. Stearns graduated with a B.A. in

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

from

Carleton College Carleton College ( ) is a Private college, private Liberal arts colleges in the United States, liberal arts college in Northfield, Minnesota, United States. Founded in 1866, the main campus is between Northfield and the approximately Carleton ...

in 1958. He then received his

Ph.D. A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of graduate study and original research. The name of the deg ...

in mathematics from

Princeton University Princeton University is a private university, private Ivy League research university in Princeton, New Jersey, United States. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial ...

in 1961 after completing a doctoral dissertation, titled ''Three person

cooperative games Cooperative game may refer to: * Cooperative board game, board games in which players work together to achieve a common goal * Cooperative game theory, in game theory, a game with competition between groups of players and the possibility of coopera ...

without side payments'', under the supervision of

Harold W. Kuhn Harold William Kuhn (July 29, 1925 – July 2, 2014) was an American mathematician who studied game theory. He won the 1980 John von Neumann Theory Prize jointly with David Gale and Albert W. Tucker. A former Professor Emeritus of Mathemat ...

. Stearns is now Distinguished Professor Emeritus of Computer Science at the

University at Albany The State University of New York at Albany (University at Albany, UAlbany, or SUNY Albany) is a Public university, public research university in Albany, New York, United States. Founded in 1844, it is one of four "university centers" of the St ...

, which is part of the

State University of New York The State University of New York (SUNY ) is a system of Public education, public colleges and universities in the New York (state), State of New York. It is one of the List of largest universities and university networks by enrollment, larges ...

Bibliography

*. A first systematic study of language operations that preserve

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

s. * . Contains the

time hierarchy theorem In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, ...

, one of the theorems that shaped the field of

. *. Answers a basic question about

deterministic pushdown automata In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages ...

: it is decidable whether a given

deterministic pushdown automaton In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages ...

accepts a

. *. Introduces

LL parser In computer science, an LL parser (left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called a ...

s, which play an important role in

compiler design In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...

References

External links

* * * 1936 births American computer scientists 1994 fellows of the Association for Computing Machinery Living people Turing Award laureates University at Albany, SUNY faculty People from Caldwell, New Jersey Princeton University alumni {{compu-scientist-stub