John Hopcroft

Last updated
John Edward Hopcroft
Hopcrofg (cropped2).jpg
Hopcroft in 2006 at ITMO University
Born (1939-10-07) October 7, 1939 (age 84)
Seattle, Washington
Alma mater Seattle University (BS)
Stanford University (MS, PhD)
Awards
Scientific career
Fields Computer science
Institutions
Thesis Synthesis of Threshold Logic Networks  (1964)
Doctoral advisor Richard Mattson
Doctoral students
Website cs.cornell.edu/jeh

John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is a professor emeritus at Cornell University, [1] [2] co-director of the Center on Frontiers of Computing Studies at Peking University, [3] and the director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. [4]

Contents

Early life and education

Hopcroft received a Bachelor of Science with a major in electrical engineering from Seattle University in 1961. He received a Master of Science in electrical engineering in 1962 and a Doctor of Philosophy in electrical engineering in 1964, both from Stanford University. [5]

Hopcroft is the grandson of Jacob Nist, who established the Seattle-Tacoma Box Company in 1889. [6]

Career and honor

He worked for three years at Princeton University and since then has been at Cornell University.

In addition to his research work, he is well known for his books on algorithms and formal languages coauthored with Jeffrey Ullman and Alfred Aho, regarded as classic texts in the field.

In 1986 he received the Turing Award (jointly with Robert Tarjan) "for fundamental achievements in the design and analysis of algorithms and data structures." Along with his work with Tarjan on planar graphs he is also known for the Hopcroft–Karp algorithm for finding matchings in bipartite graphs. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. In 2005 he received the Harry H. Goode Memorial Award "for fundamental contributions to the study of algorithms and their applications in information processing." [7]

In 2008 he received the Karl V. Karlstrom Outstanding Educator Award "for his vision of and impact on computer science, including co-authoring field-defining texts on theory and algorithms, which continue to influence students 40 years later, advising PhD students who themselves are now contributing greatly to computer science, and providing influential leadership in computer science research and education at the national and international level." [8]

Hopcroft was elected a member of the National Academy of Engineering in 1989 for fundamental contributions to computer algorithms and for authorship of outstanding computer science textbooks.

In 1992, Hopcroft was nominated to the National Science Board by George H. W. Bush.

In 2005, he was awarded an honorary doctorate by the University of Sydney in Sydney, Australia. In 2009, he received an honorary doctorate from Saint Petersburg State University of Information Technologies, Mechanics and Optics. [9] In 2017, Shanghai Jiao Tong University launched a John Hopcroft Center for Computer Science. [10] In 2020, the Chinese University of Hong Kong, Shenzhen opened a Hopcroft Institute for Advanced Information Sciences and designated him as an Einstein professor. [11]

Hopcroft is also the co-recipient (with Jeffrey Ullman) of the 2010 IEEE John von Neumann Medal for "laying the foundations for the fields of automata and language theory and many seminal contributions to theoretical computer science." [12]

Awards

Selected publications

Books

Related Research Articles

<span class="mw-page-title-main">Context-free grammar</span> Type of formal grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form

In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG).

<span class="mw-page-title-main">Finite-state machine</span> Mathematical model of computation

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.

<span class="mw-page-title-main">Theory of computation</span> Academic subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

<span class="mw-page-title-main">Alfred Aho</span> Canadian computer scientist

Alfred Vaino Aho is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.

<span class="mw-page-title-main">Leslie Lamport</span> American computer scientist and mathematician

Leslie B. Lamport is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and the author of its first manual.

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.

Jeffrey David Ullman is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers, theory of computation, data structures, and databases are regarded as standards in their fields. He and his long-time collaborator Alfred Aho are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science.

<span class="mw-page-title-main">Christos Papadimitriou</span> Greek computer scientist (b. 1949)

Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

<i>Introduction to Automata Theory, Languages, and Computation</i>

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions beginning in 2000.

In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.

Seymour Ginsburg was an American pioneer of automata theory, formal language theory, and database theory, in particular; and computer science, in general. His work was influential in distinguishing theoretical Computer Science from the disciplines of Mathematics and Electrical Engineering.

Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.

<span class="mw-page-title-main">IEEE John von Neumann Medal</span> Award

The IEEE John von Neumann Medal was established by the IEEE Board of Directors in 1990 and may be presented annually "for outstanding achievements in computer-related science and technology." The achievements may be theoretical, technological, or entrepreneurial, and need not have been made immediately prior to the date of the award.

<span class="mw-page-title-main">Rajeev Motwani</span> Indian computer scientist (1962–2009)

Rajeev Motwani was an Indian American professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in 2001.

<span class="mw-page-title-main">DFA minimization</span> Task of transforming a deterministic finite automaton

In automata theory, DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.

In computer science, the Method of Four Russians is a technique for speeding up algorithms involving Boolean matrices, or more generally algorithms involving matrices in which each cell may take on only a bounded number of possible values.

References

  1. ↑ John E. Hopcroft at DBLP Bibliography Server OOjs UI icon edit-ltr-progressive.svg
  2. ↑ John Hopcroft author profile page at the ACM Digital Library
  3. ↑ "People - Center on Frontiers of Computing Studies". Peking University.
  4. ↑ "Members - John Hopcroft Center". Shanghai Jiao Tong University. Retrieved 9 November 2021.
  5. ↑ "John E. Hopcroft". cs.cornell.edu. Cornell University, Computer Science Department. Retrieved 12 January 2021.
  6. ↑ "Seattle Tacoma Box Company". 2014. Retrieved June 14, 2014.
  7. ↑ "Harry H. Goode Memorial Award Past Recipients". IEEE. Archived from the original on 2009-02-19. Retrieved 2009-05-08.
  8. ↑ "Karl V. Karlstrom Outstanding Educator Award". ACM. Archived from the original on 2012-04-19. Retrieved 2009-10-28.
  9. ↑ "ITMO University". Archived from the original on 2015-01-21. Retrieved 2010-04-08.
  10. ↑ "Welcome to John Hopcroft Center". Shanghai Jiao Tong University.
  11. ↑ "Hopcroft Institute for Advanced Information Sciences, the Chinese University of Hong Kong, Shenzhen | CUHK-Shenzhen". www.cuhk.edu.cn. Retrieved 2021-03-20.
  12. ↑ "IEEE John von Neumann Medal Recipients". IEEE. Retrieved 2010-02-04.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.