Jeffrey Ullman

Last updated

Jeffrey Ullman
Born (1942-11-22) November 22, 1942 (age 81)
NationalityAmerican
CitizenshipAmerican
Alma mater Columbia University (BS)
Princeton University (PhD)
Known for database theory, database systems, formal language theory
AwardsACM Fellow (1994)
Knuth Prize (2000)
IEEE John von Neumann Medal (2010)
Turing Award (2020)
Scientific career
Institutions Stanford University
Thesis Synchronization Error Correcting Codes [1]  (1966)
Doctoral advisor Arthur Bernstein, Archie McKellar
Doctoral students

Jeffrey David Ullman (born November 22, 1942) [2] is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dragon book), theory of computation (also known as the Cinderella book), 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. [3]

Contents

Career

Ullman received a Bachelor of Science degree in engineering mathematics from Columbia University in 1963 and his PhD in electrical engineering from Princeton University in 1966. He then worked for three years at Bell Labs. In 1969, he returned to Princeton as an associate professor, and was promoted to full professor in 1974. Ullman moved to Stanford University in 1979, and served as the department chair from 1990 to 1994. He was named the Stanford W. Ascherman Professor of Computer Science in 1994, [4] and became an Emeritus in 2003. [5]

In 1994 Ullman was inducted as a Fellow of the Association for Computing Machinery; in 2000 he was awarded the Knuth Prize. [4] Ullman is the co-recipient (with John Hopcroft) 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." [6] Ullman, Hopcroft, and Alfred Aho were co-recipients of the 2017 C&C Prize awarded by NEC Corporation. [7]

Ullman's research interests include database theory, data integration, data mining, and education using online infrastructure. He is one of the founders of the field of database theory: many of his Ph.D. students became influential in the field as well. He was the Ph.D. advisor of Sergey Brin, one of the co-founders of Google, and served on Google's technical advisory board. [8] [9] He is a founder of Gradiance Corporation, which provides homework grading support for college courses. [4] He teaches courses on automata and mining massive datasets on the Stanford Online learning platform. [10] [11]

Ullman was elected as a member of the National Academy of Sciences in 2020. [12] He also sits on the advisory board of TheOpenCode Foundation. [13] On March 31, 2021, he and Aho were named recipients of 2020 Turing Award. [3]

Controversies

In 2011, Ullman stated his opposition to assisting Iranians in becoming graduate students at Stanford, because of the anti-Israel position of the Iranian government. In response to a call by the National Iranian American Council for disciplinary action against Ullman for what they described as his "racially discriminatory and inflammatory" comments, a Stanford spokesperson stated that Ullman was expressing his own personal views and not the views of the university, and that he was uninvolved in admissions. [14]

In April 2021, an open letter [15] by CSForInclusion criticized the ACM and the ACM A.M. Turing Award Committee for nominating and selecting Ullman as recipient of the ACM A.M. Turing award. ACM reconfirmed its commitments to inclusion and diversity in a response [16] to the letter.

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

In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form if all of its production rules are of the form:

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

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?".

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.

<i>Compilers: Principles, Techniques, and Tools</i> Computer science compiler technology textbook

Compilers: Principles, Techniques, and Tools is a computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction for programming languages. First published in 1986, it is widely regarded as the classic definitive compiler technology text.

<span class="mw-page-title-main">John Hopcroft</span> American computer scientist (born 1939)

John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is a professor emeritus at Cornell University, co-director of the Center on Frontiers of Computing Studies at Peking University, and the director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.

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.

<i>Introduction to Automata Theory, Languages, and Computation</i> 1979 computer science textbook

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 automata theory, a deterministic pushdown automaton 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.

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">Nested stack automaton</span>

In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks. Like a stack automaton, a nested stack automaton may step up or down in the stack, and read the current symbol; in addition, it may at any place create a new stack, operate on that one, eventually destroy it, and continue operating on the old stack. This way, stacks can be nested recursively to an arbitrary depth; however, the automaton always operates on the innermost stack only.

<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. ↑ Jeffrey Ullman at the Mathematics Genealogy Project
  2. ↑ Ullman, Jeffrey D. "Vita". Stanford University. Retrieved April 2, 2021.
  3. 1 2 ACM Turing Award Honors Innovators Who Shaped the Foundations of Programming Language Compilers and Algorithms. Retrieved March 31, 2021.
  4. 1 2 3 "Prof. Jeffrey Ullman, Stanford University". ODBMS.org. Retrieved April 3, 2021.
  5. ↑ Ullman, Jeffrey D. "Advising Students For Success | March 2009 | Communications of the ACM". cacm.acm.org. Retrieved April 3, 2021.
  6. ↑ "IEEE John von Neumann Medal Recipients". IEEE. Archived from the original on November 24, 2010.
  7. ↑ "2017 C&C Prize Ceremony". NEC C&C Foundation. Retrieved April 3, 2021.
  8. ↑ Kahn, Jeremy (March 31, 2021). "Programming language pioneers win this year's Turing Award". Fortune. Retrieved April 3, 2021.
  9. ↑ "Distinguished Lecturer Series" (PDF). Ben Gurion University of the Negev. 2009.
  10. ↑ "Stanford – Automata". Stanford Online.
  11. ↑ "Stanford – Mining Massive Datasets". Stanford Online.
  12. ↑ "16 faculty members, 18 alumni elected to nation's historic academies". The Princetonian. Retrieved May 11, 2020.
  13. ↑ "TheOpenCode Foundation Team Page". TheOpenCode Foundation. Retrieved December 15, 2020.
  14. ↑ Keller, Josh (January 5, 2011). "Iranian-American Group Calls on Stanford to Censure Professor". The Chronicle of Higher Education .
  15. ↑ "CSForInclusion Letter" (PDF). Association for Computing Machinery.
  16. ↑ "ACM Response to the Selection of Jeffrey Ullman for a Turing Award". Association for Computing Machinery.
  17. ↑ Mining of massive datasets. OCLC   1047815914 . Retrieved April 3, 2021– via worldcat.org.
  18. ↑ Database systems : the complete book. OCLC   47915796 . Retrieved April 1, 2021– via worldcat.org.
  19. ↑ Introduction to automata theory, languages, and computation. OCLC   605936916 . Retrieved April 2, 2021– via worldcat.org.
  20. ↑ Foundations of computer science. OCLC   24669768 . Retrieved April 1, 2021– via worldcat.org.
  21. ↑ Foundations of computer science : C Edition. OCLC   883552468 . Retrieved April 1, 2021– via worldcat.org.
  22. ↑ Data structures and algorithms. OCLC   8626442 . Retrieved April 1, 2021– via worldcat.org.
  23. ↑ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN   978-0-201-00029-0. OCLC   1147299.
  24. ↑ Formal languages and their relation to automata. OCLC   5012 . Retrieved April 1, 2021– via worldcat.org.
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.