Richard Edwin Stearns (born July 5, 1936) is a prominent

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

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 establis ...

, 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 compu ...

"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 relating these classes to each other. A computational problem is a task solved by ...

". In 1994 he was inducted as a

Fellow of the Association for Computing Machinery A fellow is a concept whose exact meaning depends on context. In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements. Within the context of higher education ...

. Stearns graduated with a B.A. in

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

from

Carleton College Carleton College ( ) is a private liberal arts college in Northfield, Minnesota. Founded in 1866, it had 2,105 undergraduate students and 269 faculty members in fall 2016. The 200-acre main campus is between Northfield and the 800-acre Cowling ...

in 1958. He then received his

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is a ...

in mathematics from

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

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 cooperat ...

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 along with David Gale and Albert W. Tucker. A former Professor Emeritus of Mathematics ...

. Stearns is now

Distinguished Professor Distinguished Professor is an academic title given to some top tenured professors in a university, school, or department. Some distinguished professors may have endowed chairs. In the United States Often specific to one institution, titles such ...

Emeritus of Computer Science at the

University at Albany The State University of New York at Albany, commonly referred to as the University at Albany, UAlbany or SUNY Albany, is a public research university with campuses in Albany, Rensselaer, and Guilderland, New York. Founded in 1844, it is one ...

, which is part of the

State University of New York The State University of New York (SUNY, , ) is a system of public colleges and universities in the State of New York. It is one of the largest comprehensive system of universities, colleges, and community colleges in the United States. Led by c ...

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 an ...

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 that ...

References

External links

* * * 1936 births American computer scientists 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